CS502 Fundamental of Algorithm VU Current Assignment No. 1 Fall 2012
• Input: A sequence of n numbers A = a1, a2, . . . , an and a value v.
• Output: An index i such that v = A[i] or the special value NIL if v does not appear in A.
Observe that if the sequence A is sorted, we can check the midpoint of the sequence against v and eliminate half of the sequence from further consideration. Binary search is an algorithm that repeats this procedure, halving the size of the remaining portion of the sequence each time. Write Pseudo code, either iterative or recursive, for binary search. Argue that the worst-case running time of binary search is Θ (lg n).
Describe a Θ (n lg n)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x.
There is more than one algorithm that satisﬁes this problem. You should
have described an algorithm and done the necessary proof for correctness, as
well as proved the asymptotic running time. If your algorithm utilizes an algorithm covered in the text, you may assume it is correct and use the results of its run-time analysis