Homework Assignment 3
MCS-178: Introduction to Computer Science II
Max Hailperin, Fall 2001; Due: October 17th
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 for the one problem not from the
book, with the exercise number (12.x1) given below.
- 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
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.10 on page 396.
- Do exercise 12.28 on pages 412-413. Remember that the row and column numbers
table-set! can be as
small as 0.
- Do exercise 12.32, either (a) or (b), 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.