Please print your name!
No late homework!
1. (easy) Write an algorithm that selects both the maximal element and the minimal element from an array A of n elements, using only 1.5·n comparisons.
2. (not so easy) The algorithm S(A,n,i) selects all the j-th smallest elements (with j ≤ i) from an array A of n elements, by using linearselect to select each of the j-th smallest elements (with j ≤ i). Clearly, one could also implement S alternatively as T(A,n,i), which first sort A (on average-case and on worstcase, the sorting takes time O(nlogn) using mergesort) and then select the first i elements. Please compare the average-case complexities of the two algorithms; i.e., For the average-case complexities, under what conditions (on the choices for i), S is better than T or vice versa.
3. (hard) In class, we have demonstrated the worst case complexity analysis for linearselect where each group has k = 5 numbers. Please show the worst case complexities for k = 3 and k = 7.
4. (hard) Let ilselect(A,n,i) be an algorithm that selects the i-smallest from an array A with n integers. It works as follows: ilselect(A,n,i){ r=partition(A,1,n);
//test if A[r] is the element to be selected if i == r, return A[r];
//test if quickselect from the low-part if i < r, return quickselect(A,1,r − 1,i);
//test if linearselect from the high-part if i > r, return linearselect(A,r + 1,n,i − r);
}
That is, the algorithm runs quickselect on the low-part or runs linear select on the high-part. Show the worst-case complexity and the average complexity of the algorithm.
5. We use 5com to denote an operation that sorts 5 numbers. Show theminimal number of 5com operations that one need to sort n distinct numbers.
1
