Cpt S 450 Homework #3
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(n log n) 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 the
minimal number of 5com operations that one need to sort n distinct numbers.
1
