CS 410 Summer 2000
Clarifications for Homework Assignment 3

Read this carefully to learn how to present your answers for full credit.

• Question 1:
  • "Step" needs to be defined.
    • For insertionsort and heapsort, you should show the initial array and the array after each change is made. For heapsort, you may show the array in heap format, if you prefer. Note which elements are compared in each configuration (e.g. "while the array order is 51342, 5 is compared with 1 and 3 is compared with 2"; though you don't need to write all these words).
    • For mergesort, you should show each recursive call to mergesort (along with the contents of the subarray it's called with), as well as each call to merge (along with the contents of both subarrays it's called with). These calls should be shown in the order they are processed. If you prefer, you may use a tree to show these calls; we will assume the entire subtree rooted at a left child will be processed before the right child. For the calls to merge, you should also show the resulting merged array and which elements are compared during the merge.
    
    
  • You should use the pseudocode given for insertionsort on page 3 of CLR, and for mergesort on page 13 (with a merge routine as discussed in class). Briefly, the merge we discussed in class takes two sorted arrays, sets a pointer to the beginning of each (so the smallest value of each), chooses the smaller of these two values to place in the sorted (output) array, and increments the pointer of the array it copied from, continuing until one of the 2 arrays is empty, then copying the remainder of the elements from the non-empty array.
  • Each of the 3 sorting algorithms needs to be shown for each of the three data sets; thus there are 9 sorts you need to perform
  • Show the number of comparisons made in each of the 9 cases in a 3-by-3 table at the end.
  
  
• Question 5:
  • Use "depth" as defined in CLR section 5.5.2 (p 94).
  • Answer should be a function of n.
  • Be sure to justify your answer.


• Question 6:
  • Hint: How would you prove something about all comparison sorts?


• Question 7:
  • In part (c), also indicate the range associated with each bucket.


• Question 8:
  • As many have already noted, a decision tree for sorting 5 elements would have 120 leaves. You do not need to draw 120 leaves. Read on.
  • You do not need to use a decision tree. However, you will probably want to use one for part of your algorithm. For example, if you find yourself saying "compare element x with element y, then if element x is smaller do one thing, but..." you will save having to write many words (and be clearer) by using a decision tree format for that portion.
  • Also, it will make it a little easier (for you *and* the TA who grades this, it's always to your advantage to be nice to the grader) if we all start as follows:
    Let the 5 elements be called A1, A2, B1, B2, and c. First compare A1 with A2, then compare B1 with B2. Now give the name a1 to the smaller of A1 and A2, and the name a2 to the other. Similarly, b1 is the smaller of B1 and B2; b2 is the larger. Now work with the 5 elements called a1, a2, b1, b2, and c.
    (There, I've used up 2 of your comparisons, so I've reduced your tree depth by 2)
  • Here's another way to reduce the decision tree portion of your solution:

    If you look at the diagram on p. 173 for a 3-input decision tree, you'll notice that after the first comparison, the left and right of the tree are symmetrical, with a_1 replaced by a_2 in the right half. This should be true in the larger case as well.

    So, instead of drawing 120 leaves, we're down to 60. That's still not very good. But at the next comparison, we again have a left and right half, and it should remain the case that the left and right are permutations of each other. So you can draw 30 leaves and be done. That's a much more reasonable amount of work, I think. If you're very careful, you can do this for part of a 3rd level, I believe.

    Just be sure you're very clear about which subtree is permuted to where, and what the permutation is.



• Question 9:
  • Be sure to justify your run time analysis (for all algorithms given, but in particular ones which must satisfy a given time requirement).


• Question 10:
  • Each integer between 1 and n appears exactly once in exactly one of the "m" arrays.
  • No distribution is imposed on the values (or arrays), the algorithm should work for any distribution (random, ordered, etc.)
  • Counting sort does not work here; it is O(n) for each of the m arrays, a total time of O(mn).
  • The output is m sorted arrays, just as though each of the m arrays were sorted independently.
  • Hint: Do not sort the arrays independently. That is, don't completely sort array A1 before considering array A2, etc.
  • Be sure to justify your answer.