1. QuickSort Algorithm (20 points) Using the PARTITION and QUICKSORT routines in textbook 171, what value of q does each PARTITION return for the following cases? Justify your answer for each case. (1) when all elements in A[p..r) are distinct and sorted in ascending order? (2) when all elements in A[p..r] are distinct and sorted in descending order? 2. QuickSort Algorithm Running Time (20 points) Provide tight upper and lower bounds on the running time of the QUICKSORT algorithm (p171) for above two cases? Show your answer (the running time) in recurrence and solve the recurrence. Justify your answer. 3. QuickSort and Substitution (20 points) Use the substitution method to prove your answer in 2. QUICKSORT(A, p,r) 1 if p