Description
1) Regarding the celebrity problem that we discussed in the class, implement the modified algorithm
with time complexity of Θ(𝑛) in your favorite language.
10 points
2) For the Maximum Consecutive Subsequence problem, improve the proposed Θ(𝑛) algorithm such
that it not only returns the maximum sum, but also returns the corresponding subsequence. No
implementation is needed.
10 points
3) Let 𝑓(𝑛) and 𝑔(𝑛) be asymptotically positive functions. Prove or disprove each of the following
conjectures:
a) 𝑓(𝑛) = 𝑂(𝑔(𝑛)) implies 𝑔(𝑛) = 𝑂(𝑓(𝑛))
b) 𝑓(𝑛) = Θ (𝑓 (
𝑛
2
))
c) 𝑓(𝑛) = 𝑂(𝑔(𝑛)) implies log 𝑓(𝑛) = 𝑂(log 𝑔(𝑛)) where log 𝑔(𝑛) ≥ 1 and 𝑓(𝑛) ≥ 1 for all
sufficiently large 𝑛.
[from CLRS 3.4]
30 points
