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 suchthatm2 +s=k+p2 (10points)
(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 number (equal for all yi). Fortunately, you are also given a number S which is equal to the correct sum S = ni=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) = log (n); g(n) = √n; (6 points) 2
1
10
(b) f(n) = nn; g(n) = 2n log(n2); (6 points) (c) f(n) = n1+sin(πn); 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