CSE 321 Winter 2010
Homework #7

Due Friday, February 26th at the start of lecture.  Bring to class to
turn in.

1 [5]. Rosen Chapter 5.1 Problem 6.

2 [10]. Rosen Chapter 5.1 Problem 20.

3 [10]. Rosen Chapter 5.1 Problem 28.

4 [10]. Count the number of satisfying assignments for each of the Boolean
   formulas below.  Here * means AND; that is, x1*x3 V x4 menas (x1
   AND x3) OR x4:

    (a) x1*x3*not(x4)*x6 V x1*x2*x5*x6

    (b) x1*x2*x3*x4 V x3*x4*x5*x6 V x4*x5*x6*x7*x8

5 [10]. Rosen Chapter 5.2 Problem 4.

6 [10]. Rosen Chapter 5.2 Problem 40.

7 [15]. Rosen Chapter 5.3 Problem 22 (a), (c), (e), (f)

8 [15]. Rosen Chapter 5.4 Problem 8.

9 [15]. Rosen Chapter 5.4 Problem 10.


EXTRA CREDIT [5 points] Let C(n) denote the number of bit strings of lenth n
    that do not have two consecutive 1s.  For example:

           C(0) = 1  (the empty string)
           C(1) = 2  (the strings 0 and 1)
           C(2) = 3  (the strings 00, 01, 10)
           C(3) = 5  (the strings 000, 001, 010, 101, 100)

    (a) Find a recurrence relation for C(n)

    (b) Give a closed formula for C(n)