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)