Please answer any of these questions

Exercise 2: quicksort (21 points). (Combination of exercises 7.1-2, 7.2-2 and problem 7.2 in the book.) Consider an array A with n elements, and refer to the pseudocode for the algorithms PARTITION (p. 171), QUICKsorT (p. 171) and RANDOMIZED-QUICKsoRT (p. 179) 1. (3 points) What value of q does PARTITION return when all elements in the array Ap..r] have the same value? Modify PARTITION so that q(p)/2 when all elements in the array Alp..r have the same value. Hint: this can be done by adding a short piece of pseudocode just before the return statement in PaRTITION. You may give just this piece of pseudocode as the solution (no need to write the rest) 2. (3 points) What is the running time of QUICKSORT when all elements of array A have the same value? Give the recurrence explicitly 3. (2 points) What is the running time of RANDOMIZED-QUICKsORT when all elements of array A have the same value? Explain 4. (7 points) The PARTITION (A, p, r) procedure returns an index q such that each element of AP-.4- 1 is less than or equal to Aq) and each element of Alg1..r is greater than A[g]. Modify the PartitIoN procedure to produce a procedure PARTITION'(A, p,r), which permutes the elements of Alp..r] and returns two indices q and t, where p