The analysis of QUICKSORT assumed that there are no duplicate values. In this problem we will study the case when the sequence of items we want to sort contains duplicate values. (a) What is the expected runtime of RANDOMIZED-QUICKsORT on a sequence of n identical items (i.e. all entries of the input array are the same)? How does it compare to the expected runtime of RANDOMIZED- QUICKSORT on an array of values picked uniformly at random which contains no duplicates. Justify vour answer To avoid the case above, we are going to design a new algorithm, 3WAYPARTitiOn, which partitions array into three parts, those that are strictly less than the pivot, equal to the pivot, and strictly greater than the pivot. Then we will use 3WAYPARTITION to sort arrays which contain duplicate values efficiently. (b) Design a new algorithm 3WAYPARTITIONA, p,r), which takes as input an array A and two indices p and r and returns a pair of indices (e, g). 3WaYPARTITION should partition the array A around the pivot q-Afr] such that every element of Alp.(e - 1)] is strictly smaller than q, every element of Ale.. (g 1) is equal to q and every element of Alg.r] is strictly greater than q. Write down the pseu- docode of your algorithm, and analyze the runtime of your algorithm. Show your work. Your algorithm should have the same runtime as the PARTITION(A, p, r) algorithm presented in the lecture notes/book. Hint: modify PARTITION(A, p,r), so that it adds the items that are greater than q from the right end of the array and all items that are equal to q to the right of all items that are smaller than q. You will need to keep additional pointers which will point to the locations in A where the nert item should be written (c) Design a new algorithm 3WAYQUICKSORT which uses 3WAYPARTITION to sort an array of n items and avoids the problems of part (a). Write down the pseudocode (d) What is the runtime of 3WaYQUiCKSORT on an array of n items whose values are picked uniformly at random? What is the runtime of 3WAYQUICKSORT on a sequence of n identical items? Justify your answers RANDOMIZED-QUICKSORT (A, p,r) 1 ifp