Consider this Find k Smallest problem: Given any sequence A[1..n] of n numbers, & any integer 1 k n, nd the k smallest numbers in A. We can solve this readily and correctly by rst sorting the array nondecreasing by calling an asymptotically ecient algorithm such as Merge-Sort, and then returning the rst k items output in the now-sorted array; pseudocode for this might look like: Sort-Then-Select-k(A,n,k)

1 INPUT: array of n numbers A[1..n], and integer 1 k n

2 array B[1..k] Used to hold and return the output

3 Merge-Sort(A,1,n)

4 for i = 1 to k

5 do B[i] = A[i]

6 OUTPUT: B[1..k] now contains the k smallest items in A The asymptotic runtime of this algorithm can be expressed as a function of both n and k as follows: T(n) = (nlgn + k). Since k n, this simplies to T(n) = (nlgn). Now answer the following three questions: 1 (a) (10 points) Using a min-heap data structure, solve the Find k Smallest problem with an algorithm which is asymptotically strictly faster than Sort-Then-Select-k in a situation where we know that k = O(lg n). Give pseudocode for your algorithm. (Hint: feel free to call subroutines Build-Min-Heap(), Heap-Extract-Min(), etc.)

(b) (10 points) Show the asymptotic runtime of your algorithm as a function of both n and k and argue that it runs faster than Sort-Then-Select-k.

(c) (10 points) Suppose that k = 1: compare the asymptotic runtimes of these two algorithms with a Find-Minimum algorithm which simply searches the entire array in one pass.

NOTE: SIZE OF THE TREE IS NOT GIVEN