COMP3121/9101: Assignment 1
Due date: Tuesday 15 of June at Noon
In this assignment we review basic algorithms and data structures. You have
five problems, marked out of a total of 100 marks.
NOTE: Your solutions must be typed, machine readable .pdf files. All
submissions will be checked for plagiarism!
1. You are given an array A of n distinct positive integers.
(a) Design an algorithm which decides in time O(n2 log n) (in the
worst case) if there exist four distinct integers m, s, k, p in A
such that m2 + s = k + p2 (10 points)
(b) Solve the same problem but with an algorithm which runs in the
expected time of O(n2). (10 points)
2. You are given a set of n fractions of the form xi/yi (1 ≤ i ≤ n), where xi
and yi are positive integers. 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)
3. You are given an array A consisting of n positive integers, not neces-
sarily 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)
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)
5. Read about the asymptotic notation in the review material and deter-
mine 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
(a) f(n) = log2(n); g(n) =
10
√
n; (6 points)
1
(b) f(n) = nn; g(n) = 2n log2(n
2); (6 points)
(c) f(n) = n1+sin(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)
2

欢迎咨询51作业君