4 Problem 4 (30 points) Let A be some array of n integers (possibly negative), with no duplicated elements, and recall that Rank(x) = k if r is the kth smallest element of A. Now define InverseRank(2) = n + 1 - Rank(x). It is easy to see that if InverseRank(I) = k, then x is the kth largest element of A. Now, let us define a number r in A to be special if I = Inverse Rank(x). For example, if A = -9,8,1,-1,2, then 2 is special because 2 is the 2nd largest number in the array, so InverseRank(2) = 2. Consider the following problem: Input: unsorted array A of length n Output: return a special number x in A, or return "no solution" if none exists. Questions: Part 2 (25 points): Give pseudocode for a O(n) algorithm for the above problem. Give a brief justification for why the algorithm is cor- rect (see Hint 2 below). Make sure to analyze the running time of the algorithm. HINT 1: the algorithm I have in mind is recursive, and the recurrence formula is one we have seen before. Recall that if we've seen a recur- rence formula before then you don't have to solve it again, you can just say what T(n) ends up being. HINT 2: use the high-level approach of Median Recursion described in class. You will want to show that by looking at the median, you can figure out one side to recurse because the other cannot have special numbers The only justification of correctness you need to include for this problem is justification of why you know for certain that there can't be special numbers on the side you don't recurse to. You don't need any other justification. A couple sentences is enough. HINT 3: write pseudocode for an algorithm FindSpecial(A, offset), which looks for a number x such that x = Inverse Rank(x) + offset. In the initial call you just have offset = 0, but as you recurse, you will want to change the offset value. This is similar to how in Selec(A,k), when we recurse we sometimes need to change the rank k that we are searching for 4 Problem 4 (30 points) Let A be some array of n integers (possibly negative), with no duplicated elements, and recall that Rank(x) = k if r is the kth smallest element of A. Now define InverseRank(2) = n + 1 - Rank(x). It is easy to see that if InverseRank(I) = k, then x is the kth largest element of A. Now, let us define a number r in A to be special if I = Inverse Rank(x). For example, if A = -9,8,1,-1,2, then 2 is special because 2 is the 2nd largest number in the array, so InverseRank(2) = 2. Consider the following problem: Input: unsorted array A of length n Output: return a special number x in A, or return "no solution" if none exists. Questions: Part 2 (25 points): Give pseudocode for a O(n) algorithm for the above problem. Give a brief justification for why the algorithm is cor- rect (see Hint 2 below). Make sure to analyze the running time of the algorithm. HINT 1: the algorithm I have in mind is recursive, and the recurrence formula is one we have seen before. Recall that if we've seen a recur- rence formula before then you don't have to solve it again, you can just say what T(n) ends up being. HINT 2: use the high-level approach of Median Recursion described in class. You will want to show that by looking at the median, you can figure out one side to recurse because the other cannot have special numbers The only justification of correctness you need to include for this problem is justification of why you know for certain that there can't be special numbers on the side you don't recurse to. You don't need any other justification. A couple sentences is enough. HINT 3: write pseudocode for an algorithm FindSpecial(A, offset), which looks for a number x such that x = Inverse Rank(x) + offset. In the initial call you just have offset = 0, but as you recurse, you will want to change the offset value. This is similar to how in Selec(A,k), when we recurse we sometimes need to change the rank k that we are searching for