Homework : Greedy Solution

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