3121-21T2-HW1-SOLUTION
1. Question 1
You are given an array A of n distinct positive integers.
(1) Design an algorithm which decides in time O(n2 log n) (in the worst case) if there exist four
distinct pairs of integers {m, s} and {k, p} in A such that m2 + s = k + p2 (10 points)
(2) Solve the same problem but with an algorithm which runs in the expected time of O(n2).
(10 points)
Solution for Question 1(a):
(1) Square all numbers in A, storing in an array S.
(2) Find all combinations of sum ai + sj, i, j ∈ [0, n− 1], i 6= j storing in an array C with i, j.
(3) Sort C based on sum using merge sort, guarantee worst case O(nlogn).
(4) Loop through C and find two adjacent elements with the same sum and distinct is, js values,
and these 4 integers are the indexes of answers.
(5) Time complexity = O(n) +O(n2) +O(n2logn) = O(n2logn).
Solution for Question 1(b):
(1) Square all numbers in A, storing in an array S.
(2) Find all combinations of sum ai + sj, i, j ∈ [0, n − 1], i 6= j storing in a hash table M ,
M [sum] = [(A[i], A[j]), ...].
(3) Loop through M and in each slot find if there is more than one pair of (A[i], A[j]) that
produces the same value of (A[i])2 + A[j].
(4) Time complexity = O(n) +O(n2) +O(n2) = O(n2).
2. Question 2
You are given a set of n fractions of the form xi/yi (1 ≤ i ≤ n), where xi and yi are positive inte-
gers. Unfortunately, all values yi are incorrect; they are all of the form yi = ci + E where numbers
ci ≥ 1 are the correct values and E is a positive integer (equal for all yi). Fortunately, you are also
given a number S which is equal to the correct sum S =
∑n
i=1 xi/ci. Design an algorithm which
finds all the correct values of fractions xi/ci and which runs in time O(n log min{yi : 1 ≤ i ≤ n}).
(20 points)
Solution for Question 2: In order to find all the correct values of the fractions, we need to find
the value of E that all denominators were increased by. Since for all i, yi > ci > 0 and E = yi − ci
is positive, we know that
0 < E < min{yi : 1 ≤ i ≤ n}
Then, define
P (k) =
n∑
i=1
xi
yi − k =
n∑
i=1
xi
ci + E − k
which is strictly increasing for 0 < k < min{yi : 1 ≤ i ≤ n}, with P (k) = S precisely when k = E.
This means that we can binary search over this range using P (k) to find E in O(log min{yi : 1 ≤
1
2 3121-21T2-HW1-SOLUTION
i ≤ n}) steps. Each step involves evaluating P once, which takes O(n) time. As such, the overall
runtime of our algorithm is O(n log min{yi : 1 ≤ i ≤ n})
3. Question 3
You are given an array A consisting of n positive integers, not necessarily all distinct. You are
also given n pairs of integers (Li, Ui) and have to determine for all 1 ≤ i ≤ n the number of elements
of A which satisfy Li ≤ A[m] ≤ Ui by an algorithm which runs in time O(n log n). (20 points)
Solution for Question 3:
We first sort the array A in O(n log n) time using merge sort. For the ith query (Li, Ui), we do
binary search twice to find the index of:
(1) the first element with value less than Li; and
(2) the last element with value greater or equal to Ui.
The difference between these indices is the answer to the ith query.
We can do a binary search in O(log n) time. There are n queries and we need to do 2 × n binary
searches. Therefore, the total time complexity is O(n log n).
4. Question 4
You are given an array containing a sequence of 2n−1 consecutive positive integers starting with 1
except that one number was skipped; thus the sequence is of the form 1, 2, 3, . . . , k− 1, k+ 1, . . . , 2n.
You have to determine the missing term accessing at most O(n) many elements of A. (20 points)
Solution for Question 4:
Let’s denote the array as A. It can be inferred that:
(1) for all i = 1, 2, ..., k − 1, we have A[i] = i.
(2) for all i = k, k + 1, ..., 2n − 1, we have A[i] = i+ 1.
Clearly, if A[j] = j then also for all i < j we have A[i] = i and if A[j] > j then for all i > j we have
A[i] > i. Thus the task is to find the smallest index i such that A[i] > i and we can do this with a
binary search in O(log (2n − 1)) = O(n) time.
5. Question 5
Read about the asymptotic notation in the review material and determine if f(n) = O(g(n)) or
g(n) = O(f(n) or both (i.e., f(n) = Θ(g(n))) or neither of the two, for the following pairs of functions
(1) f(n) = log2(n); g(n) =
10
√
n; (6 points)
(2) f(n) = nn; g(n) = 2n log2(n
2); (6 points)
(3) f(n) = n1+cos(pin); g(n) = n. (8 points)
You might find useful L’Hoˆpital’s rule: if f(x), g(x)→∞ and they are differentiable, then limx→∞ f(x)/g(x) =
limx→∞ f ′(x)/g′(x)
Solution for Question 5:
(a) To show that f(n) = O(g(n)) it is enough to show that limn→∞ f(n)/g(n) = 0 because this
clearly implies that f(n) < g(n) whenever n is large enough. Note that f(x), g(x) → ∞
when x→∞ and they are both differentiable, so we can apply L’Hopital’s rule to this limit
3121-21T2-HW1-SOLUTION 3
formula. In the equations below lnn denotes the log with the natural basis e; we also use the
formula for change of basis: log2 n = lnn ln2 e
lim
n→∞
f(n)/g(n)
= lim
n→∞
f ′(n)/g′(n)
= lim
n→∞
(log2 n)
′
(n
1
10 )′
= lim
n→∞
(lnn log2 e)
′
(n
1
10 )′
= lim
n→∞
1
n
log2 e
1
10
n−
9
10
= lim
n→∞
10 log2 e
n1/10
=0
Hence, since we have established that g(n) grows much faster than f(n), we have f(n) =
O(g(n)) but g(n) is not O(f(n)).
(b) First, we rewrite both f(n) and g(n) into an exponent of 2:
f(n) = 2n log2 n
g(n) = 22n log2 n
Hence we have
lim
n→∞
g(n)/f(n)
= lim
n→∞
22n log2 n−n log2 n
= lim
n→∞
2n log2 n
=∞
Therefore, f(n) = O(g(n)) but g(n) is not O(f(n))
(c) Aleks has messed up this one; he meant to write n1+cos(pin) in which case the following reasoning
applies:
For n odd, we have f(n) = n1−1 = 1 and hence f(n) = O(g(n)) but g(n) 6= O(f(n)).
For n even, we have f(n) = n1+1 = n2 and hence g(n) = O(f(n)) but f(n) 6= O(g(n)).
Thus, for arbitrary n, we have neither f(n) = O(g(n)) nor g(n) = O(f(n)) (2 points).
However, for n1+sin(pin) we have sin(pin) = 0 for all integers n. Thus, n1+sin(pin) = n and
consequently f(n) = Θ(g(n)).
Marking note for Question 5: for (c) part full credit is given for both “solutions” despite the
fact that only one is correct as the problem is stated.

欢迎咨询51作业君