P1

We might try to improve on the "merge" algorithm presented in class and in the class notes (not the unit 2 notes) by creating a copy of the first sorted range, but keeping the second sorted range in-place in the array A. Here's how we might write that:

Algorithm: merge(A,i,m,j)
Inputs : array A, and indices i ≤ m ≤ j such that
         A[i..m] and A[(m+1)..j] are idividually in sorted order
Outputs: array A is modified so that  A[i..j] contains its original
         elements in sorted order

A1 = new array copy of A[i..m]

k = i, i1 = 0, j1 = m - i, i2 = m+1, j2 = j

while i1 ≤ j1 and i2 ≤ j2 do            ← keep adding the smaller of the initial elements of A1 & A[i2..j2]
  if A[i2] < A1[i1]
    A[k] = A[i2], i2 = i2 + 1, k = k + 1
  else
    A[k] = A1[i1], i1 = i1 + 1, k = k + 1

while i1 ≤ j1 do                        ← add any remaining elements of A1
  A[k] = A1[i1], i1 = i1 + 1, k = k + 1

free A1
      

The advantages are twofold: first, we save half of the copy costs both in time and memory, second, we get to drop the original version's third while loop altogether. On the other hand, it's not clear that we won't run into trouble by writing something into A in the first loop that overwrites an unplaced value from the left-half of the original range, thereby losing or corrupting data. Your job is to a) Prove that

$k + (j_1 - i_1 + 1) = i_2$

is an invariant for both loops in the above algorithm, and b) use it to prove that we never overwrite a value in the range A[i2..j2], so the fear of losing or corrupting data is unfounded.

P2

Analogous to the tree we drew in class for insertion sort on three elements, draw the tree for selection sort on three elements. Please follow the same conventions!

P3

Based on the tree you just drew and the tree for insertion sort, how do the best and worst case number of comparisons for selection sort on three elements compare to the best and worst case number of comparisons for insertion sort on three elements? Describe another insteresting differences between these trees.

P4

Using the description of heapsort from Problem Set 1, what is the best-case running time of heapsort? Note that we already know it is $\Omega(n)$, simply from the observation that any sorting algorithm must look at every input element. So I'm really asking for an upper bound. I'd like the tightest possible upper bound, though, and I'd like a good argument for why the upper bound you give is valid.

P5

Write two neat 5x5 tables, with rows labeled 0..4 and columns labeled 0..4. In table 1, the element at row i column j should be $(i + j) \mod 5$. In table 2, the element at row i column j should be $(i \times j) \mod 5$.