辅导3121-21T2编程、辅导C/C++，Java程序设计
辅导R语言编程|调试Matlab程序
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