1. Consider a sorted list L of n integers, each of which must be distinct (that is, the list contains no duplicates). L may contain negative elements. Give an algorithm (describe in English, and then give pseudo-code) that finds all indicies i such that L[i] = i. Your algorithm should run in O(lg n + k) time, where k is the number of elements i such that L[i] = i.

2. In Randomized-Quicksort of a list of length n, what is the largest number of times that RANDOM will be called? What is the smallest possible number of times that RANDOM will be called? Be as exact as possible.

3. Consider the following sorting algorithm:

TripleSort(A, low, high)
if (high > low)
if (high == low + 1)
if (A[low] > A[high])
swap A[low] ↔ A[high]
else
mid1 ← d(low + high) / 3e
mid2 ← b 2 * (low + high) / 3 c
TripleSort(A, low, mid2)
TripleSort(A, mid1, high)
TripleSort(A, low, mid2)

(a) Does this sorting algorithm correctly sort all lists? Explain why, or give a counter-example.

(b) Is this sorting algorithm stable? Explain your answer for full credit

(c) Give a recurrence relation for the running time of TripleSort, solve it to provide a tight (Θ()) bound.

4. The quicksort PARTITION procedure divides returns an index q such that each element of A[p..q - 1] is less than or equal to q, and each element of A[q + 1..r] is greater than A[q]. Modify the partition procedure to produce a procedure PARITION'(A,p,r) which returns two indices q and t. where p ≤ q ≤ t ≤ r, such that:

• All elements of A[q..t] are equal
• All elements of A[p..q - 1] are less than A[q]
• All elements of A[t + 1..r] are greater than A[q]

Give pesudo-code for PARTITION'. You can assume that a function can return two values a and b with return (a,b). For full credit, your algorithm must take time Θ(n) and extra space (beyond the actual array) Θ(1).

5. Which of the following sorting algorithms are stable: insertion, merge, heap, quick. Give a simple scheme that makes any sorting algorithm stable. How much additional time does your sorting algorithm require?