CSSE 230
Data Structures and Algorithm Analysis

Written Assignment 9

To Be Turned In

Submit to the drop box on ANGEL.

1. (15 points) Problem 7.12[7.12]. This refers to the fib method defined in Figure 7.6. C(N) represents the number of calls to fib during the calculation of F_N. A recurrence relation for C(N) is given in lines 2-4 of paragraph 3 on Page 305[263]. Using this recurrence relation, you must show by (strong) induction that C(N) = F_N+2 + F_N-1 - 1 for all N ≥ 3. As stated in the text, this is fairly easy to do.
2. (12 points) Solve the recurrence relations below. Indicate which strategy you are using and show your work.
   1. T(1) = 1, T(N) = 2 T(N/4) + N^0.5
   2. T(1) = 1, T(N) = T(N - 2) + 2, assuming N is odd.
   3. T(1) = 1, T(N) = 3 T(N/2) + 2N
3. (10 points) Use a recurrence relation to show that the running time of the printPreorder method in Figure 18.22  is O(N). You may assume that the tree is perfect (i.e., full, balanced, and size 2^k - 1 for some integer k).
4. (10 points) Weiss Exercise 8.7[8.7].
5. (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.
6. (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?
7. (10 points) Weiss Exercise 19.8 (ingnore the "with proof" part).
8. (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.