## MCS-178 Homework Assignment 2

The first two problems are worth two problems each.

1. Finish writing vector-sort! by first writing the code for index-of-largest-before and then testing and debugging the whole thing.
2. 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 every  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.

3. 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))`.
4. 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.