Draw the recursion tree of this algorithm for inputs A-10, 3, 9, 4, 8, 5, 7, 6], p-1, r 8, k 2. At each non- base case node show all of the following: (1) values of all parameters: input array A, p, r & k; (2) A after Partition. At each base case node show values of all parameters: input array A, p, r & k. Beside each downward arrow connecting a parent execution to a child recursive execution, show the value returned upwards by the child execution

2. (22 points) Quicksort (a) (6 points) Quicksort can be modified to obtain an elegant and efficient linear (O(n)) algorithm QuickSelect for the selection problem. Quick select (A, p, r, k) {p & r starting and ending indexes; to find k-th smallest number in non-empty array A; 1sks(r-p+1)) 1 if p r then return Alp] else Partition (A,p,r) 3 pivot Distance q-p+1 4 f k pivot Distance then return A[q] 6 else if k pivotDistance then return Quickselect(A,p,q-1,k) else return Quickselect (A,q+1,r, k-pivotDistance) Draw the recursion tree of this algorithm for inputs A-10, 3, 9, 4, 8, 5, 7, 6], p-1, r 8, k 2. At each non- base case node show all of the following: (1) values of all parameters: input array A, p, r & k; (2) A after Partition. At each base case node show values of all parameters: input array A, p, r & k. Beside each downward arrow connecting a parent execution to a child recursive execution, show the value returned upwards by the child execution