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, or the exercise number indicated below, for the problem that is not from the book.

• Do exercise 11.19 on page 373. You may want to test out your code in SLIME.

• Do exercise 11.27 on pages 375-376.

• Exercise 12.x1: Draw a tree, analogous to Figure 4.4 on page 92, showing how the value of C(5,3) is computed by choose. Your tree should have C(5,3) at the root and 1s 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.32, part a only, on pages 415-516. When testing your procedure, be sure to use inputs large enough that the original version takes at least a few seconds, and verify that your version returns immediately, with the same answer.