CS502 Assignment 1 Solution Fall 2012
Tuesday, November 06, 2012 Edit This
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 satisfies 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.
First run merge sort on S to get the sorted array S
0 = s
0
1
, s
0
2
, ..., s
0
n
, where
s
0
i ≤ s
0
i+1
for all i. As proved in Cormen, this runs in Θ(n lg n)-time.
SUM-X(S, x)
1 MERGE − SORT(S)
2 i ← 1
3 j ← n
4 while i < j
5 do if S[i] + S[j] < x
6 then i ← i + 1
7 else if S[i] + S[j] > x
8 then j ← j − 1
9 else return S[i], S[j]
10 if i = j
11 then return nil
Proof of correctness: Assume that the set S is sorted, so that s1 < s2 < ... br/>sn. For 1 ≤ p < q ≤ n, call (p, q) an x pair if sp + sq = x. There may be many such x pairs. Initially i = 1 and j = n. SUM-X maintains a pair (i, j) and either increases i or decreases j until it finds an x pair, or i = j. If si + sj > x then j is decremented, and if si + sj < x then i is incremented.
If there are no x pairs in S then SUM-X terminates without finding such a pair. Assume there is at least one x pair. Let (i, j) be the first loop at which either the left index i or the right index j agrees with some x pair. Without loss of generality suppose that j = q and i ≤ p, thus si + sq ≤ x. This means that si + sq = x and i = p, or si + sq < x and i is increased until i = p. Hence, SUM-X finds an x pair.
The worst-case run time of SUM-X is O(n lg n). After the set is sorted, the procedure to find the two elements that sum to x has a worst-case time of O(n).
A second solution is to run merge sort to get the sorted array S
0
. Then for
each element in S
0
compute di = s
0
i − x and do a binary search for di
in S
0
. In
the worst-case we search for n elements using binary search. The worst-case run time analysis of binary search is O(lg n). Therefore, the algorithm is Θ(n lg n)
