Question. Describe an algorithm that takes a list of n different numbers and an integer k. It yields a list of the k smallest members of the list. It must take O(n) time.
Answer. Use the selection algorithm to find the k-th smallest number, x. Then compare each number in the list to x, keeping only those that are ≤ x.