Homework 5

Details

1. (8 pts) IDAA 9.1.7 (page 323).
   Prove that your algorithm is optimal.
   Correct (4), complexity (2), optimal proof (2)
2. (6 pts) IDAA 9.3.3 (page 338).
   Explain why the counterexample "breaks" the algorithm. Be specific. (2)
3. (6 pts) IDAA 9.3.6 (page 338)
   Hint: See the book's hint!