Homework Assignment 2

Remember: You are encouraged to turn in individual problems as soon as possible, rather than turning in the whole assignment on the due date. Please mark each problem with the exercise number from the book.

• Do exercise 11.23 on pages 373-374. (Note that in order to solve exercise 11.23, you have to solve exercises 11.21 and 11.22 as well.)
• Exercise 12.x1: Draw a tree, in the style that we did in class, showing how the value of C(5,3) is computed by choose. Your tree should have C(5,3) at the root and 1's as its leaves. Also, mark which two subproblems (tree nodes) a memoized version would find already in the table, rather than needing to compute.
• Do exercise 12.28 on pages 412-413.
• Do exercise 12.32 on pages 415-416. When testing your procedure, be sure to use inputs large enough that the original version takes at least a few seconds, and verify that each of your version returns immediately, with the same answer.