## Description

1. Demonstrate the operation of HOARE-PARTITION on the array A =< 14, 12, 14, 19, 5, 3, 4, 14, 7, 22, 16 >.

Show the array after each iteration of the while loop in the lines of 4 to 11 in the code of lecture notes.

2. For the following array: A =< 3, 9, 5, 8, 15, 7, 4, 10, 6, 12, 16 >,

(a) Create a max heap using the algorithm BUILD-MAX-HEAP.

(b) Remove the largest item from the max heap you created in 2(a), using the HEAP-EXTRACT-MAX

function. Show the array after you have removed the largest item.

(c) Using the algorithm MAX-HEAP-INSERT, insert 11 into the heap that resulted from question 2(b).

Show the array after insertion.

3. For an disordered array with n elements, design an algorithm for finding the median of this array. Your

algorithm should traverse the array only once.

Notes: You can imagine the array as a flow which means you can get the data one by one, and you need

to do some cheap operation at the time you see each element. The size of this array, n, is big and you

know n from the start. Please do not sort the array, or you cannot get full mark. A hint to solve this

problem is to use heap.

4. Finding the median of an unordered array in O(n) (Part II). In last homework, we looked at an algorithm

that tried to find the median in O(n), but it is not correct. This time we are going to fix it.

Let’s consider a more general problem: given an unsorted array L of n elements (L[1, . . . , n]), how to

find the k

th smallest element in it (and when k = ⌈

n

2

⌉, this turns out to find the median).

We can also

do divide-and-conquer to solve it, by the algorithm called QUICKSELECT, as follows.

QUICKSELECT(L, p, r, k)

q ← PARTITION(L, p, r)

t ← q − p + 1

if k == t then

return L[q]

else if k < t then

QUICKSELECT(L, p, q − 1, k) {Only look at the left part}

else

QUICKSELECT(L, q + 1, r, k − t) {Only look at the right part}

end if

(a) The pivot selection in PARTITION plays a key role in optimizing the performance of teh QUICKSORT algorithm. If we use HOARE-PARTITION as the PARTITION function, please solve for

the worst-case running time. And, what is the average running time (just give the answer)?

(b) The b

∗

found in the algorithm in last homework may not be the true median, yet it could serve as a

good pivot. Let’s look at the BFPRT algorithm (a.k.a. median-of-medians), which uses this pivot

to do the partition, as follows.

BFPRT(L, p, r)

Divide L[p, . . . , r] into r−p+1

5

lists of size 5 each

Sort each list, let i

th list be ai ≤ a

′

i ≤ bi ≤ ci ≤ c

′

i

, i = 1, 2, . . . ,

r−p+1

5

Recursively find median of b1, b2, . . . , b r−p+1

5

, call it b

∗

Use b

∗ as the pivot and reorder the list (do swapping like in HOARE-PARTITION after pivot

selection)

Suppose after reordering, b

∗

is at L[q], return q

Solve for the worst-time running time of the QUICKSELECT algorithm, if we utilize BFPRT as

PARTITION.

(Hints: In QUICKSORT, the worst-time running time occurs when every partition is extremely

unbalanced, so does in QUICKSELECT. Therefore, we need to consider how unbalanced this partition could be. Remember that there is a median finding step in BFPRT algorithm. And in this

question we only require the solution in big-O notation.)