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) (5 pts) 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 your 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 3 WAYPARTITION to sort arrays which contain duplicate values efficiently. (b) (10 pts) Design a new algorithm 3WAYPARTItion (A,p,r), which takes as input an array A and two indices p and r and returns a pair of indices (e,g). 3WAYPARtition (A,p,r) should partition the array A around the pivot q=A[r] such that every element of A[p..(e1)] is strictly smaller than q, every element of A[e..(g1)] is equal to q and every element of A[g..r] is strictly greater than q. Write down the pseudocode of your algorithm, and analyze its runtime. 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 next item should be written. (c) (15 pts) Using either loop invariants or induction prove that your 3 WAYPARtition (A,p,r) correctly partitions the array A around the pivot q=A[r]. (d) (10 pts) 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. (e) (5 pts) 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