CSSE 230
Data Structures and Algorithm Analysis

Written Assignment 9

To Be Turned In

Except where noted, these are to be turned in as hard copy. You can write solutions out by hand, or write them on your computer and print them.

Papers must not have ragged, spiral-notebook edges. Multiple page solutions must be stapled. Solutions not following these guidelines will be returned ungraded. I regret this rigidity, but it is necessary given the number of students in CSSE 230 this term.

Late days may not be used for written assignments.

1. Don’t forget: You should be keeping an individual log about your team project work so that you can write a performance evaluation for each of your teammates. You do not need to turn in this log, but I wanted to remind you while I had your attention.
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(0) = 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 (Weiss, p. 612) 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. (15 points) In class we drew a diagram of the sort decision tree for selection sort on three elements. For this problem, you’ll do the same thing for insertion sort on 4 elements.

   Because the tree is so large, just show the root, its left child, and the left subtree of the left child. For consistency, when comparing a_i and a_j where i < j, always write a_i : a_j (instead of a_j : a_i) so that going left in the tree will always be the no-additional-movement-of-data direction for insertion sort. Thus (for example) a₁ < a₂ < a₃ < a₄ should be the label on the leftmost leaf of the tree.

   The resulting tree is quite wide. You will probably want to work sideways on the page.

5. (10 points) Weiss Exercise 8.15. (Pseudocode or Java code is sufficient.)

For Your Consideration

These problems are for you to think about and convince yourself that you could do them. It would be good practice to actually do them, but you are not required to turn them in.

• QuickSort analysis:
  1. If we sort n elements, what is the maximum depth of the stack for the recursive calls to QuickSort (see Figure 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 at is the maximum depth of the stack?