3. Sorting is a fundamental and heavily used routine and can be done in O(nlogn) time for a list of n numbers. In the comparison tree model there is a lower bound of S(n log n) for sorting. Selection can be done in O(n) time. Although a faster Selection algorithm may not be as directly useful in practice as Sorting, the ideas behind a linear time algorithm for it are theoretically interesting and related ideas play an important role in other problems. For each of the problems below use Selection as a black box algorithm to derive an O(n) time algorithm. It is common these days to hear statistics about wealth inequality in the United States. A typical statement is that the the top 1% of earners together make more than ten times the total income of the bottom 70% of earners. You want to verify these statements on some data sets. Suppose you are given the income of people as an n element unsorted array A, where A[i] gives the income of person Describe an algorithm that given A checks whether the top 1% of earners together make more than ten times the bottom 70% together. Assume for simplicity that n is a multiple of 100 and that all numbers in A are distinct. Describe an algorithm to determine whether an arbitrary array A[1..n] contains more than n/6 copies of any value. The square distance between a pair of integers x, y is defined as the quantity (x - y)2. The input is an an array A of n integers and an integer k such that 1 sk sn. Describe an algorithm to find k elements in A with the smallest square distance to the median (i.e. the element of rank [n/2] in A). For instance, if A= [9,5,-3,1,-2) and k = 2, then the median element is 1, and the 2 elements in A with the smallest square distance to the median are {1, 2}. If k= 3, then you can output either {1,-2, -3} or {1, -2,5). You do not need to formally prove the correctness of the algorithms but they should be clear and high-level. You need to justify the running time of your algorithms. 3. Sorting is a fundamental and heavily used routine and can be done in O(nlogn) time for a list of n numbers. In the comparison tree model there is a lower bound of S(n log n) for sorting. Selection can be done in O(n) time. Although a faster Selection algorithm may not be as directly useful in practice as Sorting, the ideas behind a linear time algorithm for it are theoretically interesting and related ideas play an important role in other problems. For each of the problems below use Selection as a black box algorithm to derive an O(n) time algorithm. It is common these days to hear statistics about wealth inequality in the United States. A typical statement is that the the top 1% of earners together make more than ten times the total income of the bottom 70% of earners. You want to verify these statements on some data sets. Suppose you are given the income of people as an n element unsorted array A, where A[i] gives the income of person Describe an algorithm that given A checks whether the top 1% of earners together make more than ten times the bottom 70% together. Assume for simplicity that n is a multiple of 100 and that all numbers in A are distinct. Describe an algorithm to determine whether an arbitrary array A[1..n] contains more than n/6 copies of any value. The square distance between a pair of integers x, y is defined as the quantity (x - y)2. The input is an an array A of n integers and an integer k such that 1 sk sn. Describe an algorithm to find k elements in A with the smallest square distance to the median (i.e. the element of rank [n/2] in A). For instance, if A= [9,5,-3,1,-2) and k = 2, then the median element is 1, and the 2 elements in A with the smallest square distance to the median are {1, 2}. If k= 3, then you can output either {1,-2, -3} or {1, -2,5). You do not need to formally prove the correctness of the algorithms but they should be clear and high-level. You need to justify the running time of your algorithms