MCS-178 Homework Assignment 2

The following are worth four problems which will be called 2-1a, 2-1b, 2-2a, 2-2b on your homework results e-mail.

  1. This problem is an extension of 12.32.

    1. Start by doing exercise 12.32 on pages 415-416. When testing your improved versions, try running them on a large enough inputs so that the original version takes a while (at least a few seconds), and verify that the improved version computes nearly instantaneously. Be sure the results returned are identical.

    2. You'll now have three versions of ps, the recursive version in the book, a dynamic programming version, and a memoized version. For each version, draw a diagram which shows every call to ps and and every or call to ps-subproblem (i.e., every table lookup in the memoized and dynamic programming versions) in the evaluation of (ps 5). You can test your work by placing display statement(s) in your code.

  2. Repeat the last exercise using Exercise 12.34. Again, you'll have three versions of best. For each version, make diagrams showing what calls to best get called in the evaluation of (best '(2 1 3 1 4 2)).