a) How to find the k th smallest number given each element of the input sequence a1 , a2 , . . . an is given one by one. Design an algorithm that again runs in O(n) expected time but this time uses O(k) space. You can assume that k is known ahead of time.

b) Give an O(n log n)-time algorithm to find the longest monotonically increasing sub- sequence of a sequence of n numbers. (Hint: Observe that the last element of a candidate subsequence of length i is at least as large as the last element of a can- didate subsequence of length i 1. Maintain candidate subsequences by linking them through the input sequence.)