1. (Basic) We're given a sorted array A[1...n]. We want to find the kth smallest element of 2. (Basic) We're given an array A.-n], which is not necessarily sorted. We want to find 3. (Basic) We're given a sorted array A1n] and a target number z. We want to find i 4. (Basic) We're given an array A[1-.-n], which is not necessarily sorted, and a target number A. How much time do you need? the kth smallest element of A. How much time do you need? such that Ali if such i exists. How much time do you need? x. We want to find i such that Ai if such i exists. How much time do you need? 5. (Basic/Intermediate) Show that T(n) - T(n/5)+O(n) implies T(n) -O(n). 6. (Basic) Let A[1-9(3,2,9,0,7,5,4,8,6). Illustrate the execution of Randomized- Select(A, 1, 9, 4) with Randomized-Partition replaced with Partition; see pg 216. More precisely, list all calls to Randomized-Select(A,p,r, i) with p,r, i specified. Continue to to (A, 1, 9, 8). How ahout illistrate the execution of Randomized-Select(A, 1, 9, 8). How about Randomized-Select(A, 7. (Intermediate) Show how quicksort can be made to run in O(n logn) time in the worst 8. (Advanced*) Let X[1.--nl] and Y[1...n] be two arrays, each containing n numbers already 1, 9, 7)? case; assume that all elements are distinct. in sorted order. Give an (log2n) time algorithm to find the median of all 2n elements in arrays X and Y