Exercise $1$ Suppose that you have a $$black$-$box$$ worst$-$case linear$-$time median subrou$-$ tine, FindMedian. Give a simple, linear$-$time algorithm that find the k$-$th order statistics for an array A of integers

Exercise $2$ Give an O$($n$)$ algorithm that, given a array A of n distinct integers and a positive integer k $<=$ n$,$ determines the k numbers in S that are closest to the median of A

Exercise $3$ Argue the correctness of $$Build$-$Max$-$Heap$$

Build$-$Max$-$Heap$($A$,$ n$)$

$1$: A$.$heap$-$size $=$ n

$2$: fori$=$n$2$downto$1$do $3$: Max$-$Heapify$($A$,$ i$)$

by proving the following loop invariant: $$At the start of each iteration of the for loop of lines $2-3,$ each node i$+1,$i$+2,...,$n is the root of a max$-$heap$$

Exercise $4$ Give an O$($n lg k$)-$time algorithm to merge k sorted lists into one sorted list, where n is the total number of elements in all the input lists $($Hint: use a min$-$heap for k$-$way merging$)$

Exercise $5$ Suppose in the algorithm SELECT $($median of medians$),$ the input elements are divided into groups of $7($instead of $5),$ to find the ith smallest element in a array A of size n$.$ Show that the worst case running time of this modified algorithm is defined by:

T$($n$)<=$ T$($n$/7)+$ T$(5$n$/7)+$ n then use induction to show that T$($n$)$ is O$($n$)$