Problems
1. (15 pts) Exercise 16.2-3. Use induction to argue correctness.
2. (15 pts) Exercise 16.2-4.
3. (15 pts) Exercise 16.2-5.
4. (15 pts) Exercise 16.2-6.
5. (15 pts) Exercise 16.3-3.(Extra Credit). First prove by induction that
F (n + 1) 1
6. (20 pts) Problem 16-1, (a), (b) and (c).
Pn 1
i=0 F (i) =
7. (15 pts) Exercise 15.4-5. Hint: try to solve this problem using a greedy approach - it may not work; if it doesn’t work, it means you must use DP and you can leave it for HW5.
1
