The problem numbers refer to the textbook on Jeff Erickson's algorithms page. Note that here an expectation for the solution is a correct algorithm with running time optimized (to a reasonable extent). All problems are from Chapter 3 (Dynamic Programming).
  1. Exercise 6 (b). (10 points)
  2. Exercise 9 (a). (10 points)
  3. Exercise 12 (a,b). (15 points)
  4. Exercise 13. (15 points)

The homework is due in class on Thursday, February 27. Please pay attention to the policy on collaboration outlined in the syllabus. In particular, you will get the most out of home work if either you work on your own or collaborate with a fellow student or two in a reasonable way. We will evaluate the originality of your writing while reviewing your work.