Assignment 2 - JBP030 (Fall 2017)

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.

Exercise 1 [5 points]

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)
[1, 3, 7, 10, 22]

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

Exercise 2 [5 points]

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

Exercise 3 [5 points]

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

Exercise 4 [5 points]

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