COMP3121/9101 — Assignment 1 solution

$25.00

Category:

Description

5/5 - (3 votes)

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 determines 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(n
2
) 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) Show that your task can always be accomplished by asking no more than 3n − 3 such
questions, even in the worst case.
(b) 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 marks, each pair 4 marks] Read the review material from the class website on
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.
f(n) g(n)
(log2 n)
2
log2
(n
log2 n) + 2 log2 n
n
100 2
n/100

n 2

log2 n
n
1.001 n log2 n
n
(1+sin(πn/2))/2 √
n
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.
(a) T (n) = 2T (n/2) + n(2 + sin n)
(b) T (n) = 2T (n/2) + √
n + log n
(c) T (n) = 8T (n/2) + n
log n
(d) T (n) = T (n − 1) + n
1