Problem 1. Suppose we have an array A[1 : n] of n distinct numbers. For any element A[i], we define the rank of A[i], denoted by rank(A[i]), as the number of elements in A that are strictly smaller than A[i] plus one; so rank(A[i]) is also the correct position of A[i] in the sorted order of A. Suppose we have an algorithm magic-pivot that given any array B[1 : m] (for any m > 0), returns an element B[i] such that m/3 rank(B[i]) 2m/3 and has worst-case runtime O(n) 1 .Example: if B = [1, 7, 6, 2, 13, 3, 5, 11, 8], then magic-pivot(B) will return one arbitrary number among {3, 5, 6, 7} (since sorted order of B is [1, 2, 3, 5, 6, 7, 8, 11, 13]) (a) Use magic-pivot as a black-box to obtain a deterministic quick-sort algorithm with worst-case running time of O(n log n). (10 points) (b) Use magic-pivot as a black-box to design an algorithm that given the array A and any integer 1 r n, finds the element in A that has rank r in O(n) time2 . (15 points) Hint: Suppose we run partition subroutine in quick sort with pivot p and it places it in position q. Then, if r q, we need to look for it in the subarray A[q + 1 : n] (although, what is the new rank we should look for now?).

Problem 1. Suppose we have an array A[1:n) of n distinct numbers. For any element A[i], we define the rank of A[i], denoted by rank(A[i]), as the number of elements in A that are strictly smaller than A[i] plus one; so rank(A[i]) is also the correct position of A[i] in the sorted order of A. Suppose we have an algorithm magic-pivot that given any array B1: m] (for any m > 0), returns an element B[i] such that m/3 q, we need to look for it in the subarray A[q+1:n] (although, what is the new rank we should look for now?). Problem 1. Suppose we have an array A[1:n) of n distinct numbers. For any element A[i], we define the rank of A[i], denoted by rank(A[i]), as the number of elements in A that are strictly smaller than A[i] plus one; so rank(A[i]) is also the correct position of A[i] in the sorted order of A. Suppose we have an algorithm magic-pivot that given any array B1: m] (for any m > 0), returns an element B[i] such that m/3 q, we need to look for it in the subarray A[q+1:n] (although, what is the new rank we should look for now?)