**Note:** You should always justify your answers. Whenever you are asked to describe an algorithm, you should present three things: the algorithm, a proof of its correctness, and a derivation of its running time.

Consider the following sorting algorithm (slow_sort).

In [1]:

```
def swap(A, i, j):
A[i], A[j] = A[j], A[i]
def slow_sort(A):
for i in range(len(A)): # In pseudo-code: for i=0,...,length(A)-1
for j in reversed(range(i+1, len(A))) : # In pseudo-code: for j=length(A)-1,..., i+1
if A[j] < A[j-1]: swap(A, j-1, j)
A = [10, 3, 7, 22, 1]
slow_sort(A)
print(A)
```

(a) Give a loop invariant for the **for** loop in lines 8--9, and prove that it holds.

(b) Give a loop invariant for the **for** loop in lines 7--9 that will allow you to prove that the algorithm sorts correctly. Use the termination condition of the loop invariant from part (a) for this.

Use the master method to give tight asymptotic bounds for the following recurrences (a-c).

(a) $T(n) = 3T(n/4) + n \log n$

(b) $T(n) = 4T(n/2) + n^{3/2}$

(c) $T(n) = 3T(n/9) + \sqrt n$

(d) Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n) = 3T(n/2) + n$.

(e) Use the substitution method to verify your answer to (d).

(a) [1 point] How does the asymptotic running time of mergesort change if we recursively split into three equal parts, and in the merge step merge three lists?

(b) [1 point] When executing counting sort on $A = [4, 3, 7, 4, 6, 1, 4, 3]$ and with $k=7$, what is the content of array $C$ after lines 1, 2, 4 and 7 (line numbers from slides) of the algorithm?

(c) [1 point] Using the example from the slides as a model, illustrate the operations of RadixSort on the following list of English words: TEA, EAT, SAT, CAT, TOP, TIP, SIP, TAP.

(d) [2 point] Show how to sort n integers in the range 0 to $n^7 - 1$ in $O(n)$ time.

(a) [3 points] Suppose you have an array of records whose keys to be sorted consist only of 0's and 1's. Give a simple, linear-time algorithm to sort the array in place (using storage of no more than constant size in addition to that of the array). *Note: Since you have records linked to the keys, you cannot simply count 0's and 1's.*

(b) [2 point] Can you generalize your method to keys that consists of 0's, 1's, and 2's?
*Note: don't write pseudo-code, just describe the general idea.*