Recall the Selection problem. Given an array A of n unsorted values and an integer k n return the k-smallest item in A.

Algorithmically, suppose you are given an arrayA[1 . . . n], p

In class you learned a simple O(n) randomized algorithm for solving Selection. There also exists a (much more complicated) O(n) worst-case time Selection algorithm.

A special case of the Selection problem is the Median-Problem which finds the middle ordered item in the subarray. Formally, MEDIAN(A,p,r) should return Select (A,p,r, ceiling( (r-p+1)/2))

A special case of the Selection problem is the Quartile-Problem which finds the 1/4 ordered item in the subarray. Formally, Quart(A, p, r) should return Select ( A,p,r,ceiling(( rp+1)/4)))

In this problem assume you are given a linear time procedure Quart(A, p, r), i.e., it solves the Quartile problem in O(r p + 1) time.

Also assume that you are also given the linear time code to implement the Partition procedure taught in class and can call it as a subroutine in your algorithm.

1. Show how, using Quart() as a subroutine, you can solve the median problem in linear, i.e., O(r p + 1), time.

   Justify the running time of your algorithm.

   Further restriction: Your solution must be performed in-place (no new array can be created). In particular, one alternative solution would be to extend the array to size m so that all the entries in A[n+1,...,m] = and m > 2n. After this, you would be able to solve the median problem in the original array with just one call to the quartile problem in the extended array. With the further restriction, this is not possible.

25 pts Recall the Selection problem. Given an array A of n unsorted values and an integer k