(a) You are given two inputs: an integer k, and an array A containing n integers. Give an algorithm to find any one of the k smallest elements of A, using at most n - k comparisons. (In other words, your algorithm must return one of the k smallest elements of A, but it doesn't matter which one.) Explain why your algorithm is guaranteed to find a correct answer and why it satisfies the bound on the running time. (Hint: there is a very easy way to solve this problem).
(b) Show that your algorithm from (a) is optimal by proving a lower bound of n - k on the number of comparisons required to solve the problem.