## Description

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.