CSSE 230
Data Structures and Algorithm Analysis

Written Assignment 10

To Be Turned In

Nothing!

For Your Consideration While Studying for the Final Exam

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.

1. Weiss Exercise 8.9. This should be fairly easy if you followed the derivation of the quicksort average case runtime that we did in class.
2. Weiss Exercise 8.11[8.11]

3. 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.

4. Show the steps used by the radix sort algorithm to sort the array:
   [526, 34, 865, 435, 153, 897, 23, 432, 943, 255, 560, 103, 397]
5. State the runtime of radix sort. If the runtime isn't constrained by the n log n bound, why don't we use it for sorting all kinds of data?
6. Study skip lists.