MCS-178 Homework Assignment 2

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.