## Description

1. (10 points) For QUICKSORT, the PARTITION function is called n times to sort an

array of n elements. Prove that when the array is already sorted in ascending or

descending order, every call to the PARTITION (A, p ,r) function generates an

empty array and an array of size p – r .

2. (10 points) Is it correct to say that the worst-case running time of RANDOMIZEDQUICKSORT on textbook 7.3 (page 179) is O(nlgn)? If YES, please give your

reason. If NO, please explain under which situation the worst-case running time

can be triggered.

3. (27 points) See below for Triple-QUICKSORT(A, p, r), which partitions an array

into three subarrays A1, A2, and A3, such that all elements in A1 are less than

those in A2, and all elements in A2 are less than those in A3.

Triple-QUICKSORT(A, p, r)

{

if (p < r)

{

[q1, q2] = Triple-PARTITION(A, p, r);

Triple-QUICKSORT (A, p, q1-1);

Triple-QUICKSORT (A, q1+1, q2-1);

Triple-QUICKSORT (A, q2+1, r);

}

}

Answer the following questions:

(1) (7 points) Triple-PARTITION (A, p, r) returns two pivots q1 and q2. When this

function returns, all elements in A[p…q1-1] are less than or equal to the pivot

A[q1], all elements in A[q1+1…q2-1] are larger than A[q1] and less than or

equal to the pivot A[q2], and all elements in A[q2+1…r] are larger than the

pivot A[q2].

Complete the code of Triple-PARTITION (A, p, r).

Triple-PARTITION(A, p, r)

{ x = A[r]

i = p – 1

for j = p to r – 1

if A[j] ≤ x

i = i + 1

exchange A[i] ↔ A[j]

exchange A[i + 1] ↔ A[r]

q1 = ________

x = A[r]

i = q1

for j = ________ to ________

if A[j] ≤________

i = i + 1

exchange ________

exchange ________

q2 = ________

return [q1, q2]

}

(2) (10 points) Is it possible for Line 1 or line 9 of Triple-PARTITION choose the

same element as the pivots (In other words, q1 = q2)? Please explain your

reason.

(3) (10 points) Analyze the worst-case time complexity of Triple-QUICKSORT (A,

p, r).

4. (10 points) Use induction to prove that LSD Radix Sort works. Where does your

proof need the assumption that the intermediate sort is stable?

5. (10 points) Given n = 80,000,000 numbers and each number of 64 bits. We first

divide each number into d digits and then use LSD Radix Sort to sort these

numbers. What’s the running time if each digit is of 32 bits, 16 bits, 8 bits, ⌈lgn⌉,

and ⌊lgn⌋ bits? Please explain your answer.

6. (10 points) Each element of an array A of n elements falls in the range of [0… 𝑘 ∗

𝑛

100 − 1], where k is a constant that is less than n. Can we sort these numbers in

O(n) time? Why?

7. (10 points) Describe an algorithm that, given n integers in the rage 0 to k,

preprocess its input and then answers any query about how many of the n

integers fall into a range [a…b] in O(1) time. Your algorithm should use Θ(𝑛 + 𝑘)

preprocessing time.

8. (10 points) Suppose we use RANDOMIZED-SELECT to select the minimum

element of the array A = {3,2,9,0,7,5,4,8,6,1}. Describe a sequence of partitions

that results in a worst-case performance of RANDOMIZED-SELECT.

9. (10 points) Analyze SELECT to show that if n ≥ 140, then at least ⌈

𝑛

4

⌉ elements are

greater than the median-of-medians x, and at least ⌈

𝑛

4

⌉ elements are less than x

10. (10 points) Describe an O(n) algorithm (other than linear sorting algorithm) that,

given a set S of n distinct numbers and a positive integer k ≤ n, determines the k

numbers in S that are closest to the median of S.