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.
- This problem is an extension of 12.32.
-
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.
-
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.
- 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)).