COMP3121/9101 18T1 — Assignment 1 (UNSW)
Five questions, each question 20 marks for a total of 100 marks. Due: on March 12, before 2:00 PM. Note: no extensions can be given because we will go through the solutions in class on that date.
1. [20 marks] You’re given an array A of n integers, and must answer a series of n queries, each of the form: “How many elements a of the array A satisfy Lk ≤ a ≤ Rk?”, where Lk and Rk (1 ≤ k ≤ n) are some integers such that Lk ≤ Rk . Design an O(n log n) algorithm that answers all of these queries.
2. [20 marks, both (a) and (b) 10 marks each] You are given an array S of n integers and another integer x.
(a) Describe an O(n log n) algorithm (in the sense of the worst case performance) that de- termines whether or not there exist two elements in S whose sum is exactly x.
(b) Describe an algorithm that accomplishes the same task, but runs in O(n) expected (i.e., average) time.
Note that brute force does not work here, because it runs in O(n2) time.
3. [20 marks, both (a) and (b) 10 marks each; if you solve (b) you do not have to solve (a)] You are at a party attended by n people (not including yourself), and you suspect that there might be a celebrity present. A celebrity is someone known by everyone, but does not know anyone except themselves. You may assume everyone knows themselves.
Your task is to work out if there is a celebrity present, and if so, which of the n people present is a celebrity. To do so, you can ask a person X if they know another person Y (where you choose X and Y when asking the question).
(a) (b)
Show that your task can always be accomplished by asking no more than 3n − 3 such questions, even in the worst case.
Show that your task can always be accomplished by asking no more than 3n−⌊log2 n⌋−2 such questions, even in the worst case.
4. [20
asymptotic notation and basic properties of logarithms, pages 38-44 and then determine if f(n) = Ω(g(n)), f(n) = O(g(n)) or f(n) = Θ(g(n)) for the following pairs. Justify your answers.
You might find the following inequality useful: if f(n),g(n),c > 0 then f (n) < c g(n) if and only if log f (n) < log c + log g(n).
5. [20 marks, each recurrence 5 marks) Determine the asymptotic growth rate of the solutions to the following recurrences. If possible, you can use the Master Theorem, if not, find another way of solving it.
marks, each pair 4 marks] Read the review material from the class website on
f (n)
g(n)
(log2 n)2
log2(nlog2 n) + 2 log2 n
n100
2n/100 2√log2 n
√n
n1.001
n log2 n √
n
n(1+sin(πn/2))/2
(a) T(n)=2T(n/2)+n(2+sinn)
n+logn (b) T(n)=2T(n/2)+√
(c) T(n)=8T(n/2)+nlogn (d) T(n)=T(n−1)+n
1