CSSE 230
Data Structures and Algorithm Analysis

Written Assignment 9

To Be Turned In

Submit to the drop box.

1. (10 points) Weiss Exercise 8.7[8.7].
2. (5 points) Weiss Exercise 8.16[8.14]. Explain your answer. Note that for brevity in the statement of this exercise the author uses < instead of compareTo, thus assuming that the items to be sorted are numbers. Do not consider that to be a change in behavior. Focus on the algorithm itself.
3. Removed.
4. (10 points) Weiss Exercise 19.8 (ignore the "with proof" part).
5. (20 points) In this problem, we consider completely full binary trees with N nodes and height H 
                     (so that N = 2^H+1 – 1 )
   (a) (5 points) Show that the sum of the heights of all of the nodes of such a tree can be expressed as   
   
   (b) (15 points) Prove by induction on H that the above sum of the heights of the nodes is N - H - 1.  You may base your proof on the summation from part (a) (so you don't need to refer to trees at all), or you may do our "standard" binary tree induction based on the heights of the trees, using the definition that a non-empty binary tree has a root plus left and right subtrees. I find the tree approach more straightforward, but you may use the summation if you prefer.