public int topKelement(int[] input, int k) { // Problem 2 -- you should write it as a recursive solution } }

Problem 2. Find top-k element (50 pt) The goal of this exercise is to find top k-element using a variation of quick sort we have seen in class. We will write a program (which is a modification of QuickSort) that runs in expected O(n)-time. Below is the rough outline of the algorithm 1. Pick a random pivot from the list, divide the list into two: one that is greater and one that is smaller 2. Compute the size of the smaller list. If the size is k 1, then return the pivot . If the size is > k - 1, then .. If the size is