CS502 Fundamental of Algorithm VU Current Assignment No. 1 Fall 2012
Question 1:
• 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).
Question 2:
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.
Solution:
Will be upload as soon as possible
Question 1:
Consider the searching problem:
• 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).
Question 2:
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.
Solution:
Will be upload as soon as possible
