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)