CSSE 230
Data Structures and Algorithm Analysis

Written Assignment 9

To Be Turned In

Submit to the drop box on ANGEL.

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. (10 points)
   1. If we sort N elements, what is the maximum depth of the stack for the recursive calls to QuickSort (figure 8.22[8.21])?
   2. What if, after line 46, we test to see which subarray is smaller and do the recursive call on that side first? Now what is the maximum depth of the stack?
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.