Homework Assignment 2
MCS-178: Introduction to Computer Science II
Max Hailperin, Spring 2003; Due: March 5
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
- 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
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.