Problem Set #4, CS 255, due April 23, 2007

Final version

Trace the behavior of the approximation algorithm of Section 35.5, Cormen et al for the input set {55, 45, 36, 28, 21, 15}, target 95, and for ε =
1. 0.30
2. 0.18
Whether you do the trace by hand or by writing a program, you should show the final value of L_i for each i in each case, in addition to the final approximating sum.
Trace the behavior of the algorithm of Section 30.1.3, CLR, on the tree given below. Show the values at the beginning of each iteration, and at termination, of
1. each node's A, B, and C values, and
2. all three links for each node.
Recall that the loop that is being iterated corresponds to the while loop of lines 3-7 on p. 696.
```
                a
               / \
              b   c
             /   / \
            d   e   f
           /         \
          g           h
         / \
        i   j
```