2. [20 marks, both (a) and (b) 10 marks each] You are given an array S of n integers and another integer a. (a) Describe an O(n log n) algorithm (in the sense of the worst case performance) that de- termines whether or not there exist two elements in S whose sum is exactly r. (b) Describe an algorithm that accomplishes the same task, but runs in O(n) expected (i.e., average) time. Note that brute force does not work here, because it runs in O(n2) time