Homework #1 Introduction to Algorithms

Homework #1
Introduction to Algorithms
601.433/633

Format: Please start each problem on a new page.
Where to submit: On Gradescope, please mark the pages for each question

1 Problem 1 (20 points)
1.1 (5 points)
Prove that, if limn→∞
f(n)
g(n) = k, where k is a positive constant, then f(n) =
Θ(g(n)).
1.2 (10 points)
For each statement below explain if it is true or false and prove your answer. Be as
precise as you can. The base of log is 2 unless stated otherwise.
1. n
2
log n = Θ(n)
2. 2
n = O(3n
)
3. √
n = Θ(2 log n
2
)
4. 3n log n + n = O(
n
2−n
2
)
5. Let f and g be positive functions. If f(n) + g(n) = Ω(f(n)) then g(n) =
O((f(n))2
).
1
1.3 (5 points)
1. Prove that
Xn
i=1
log i = Θ(n log n).
2 Problem 2 (20 Points)
2.1 (10 points)
1. Prove by induction that Pn
i=1
1
i(i+1) =
n
n+1 for all n ≥ 1.
2. Alice wants to distribute three identical movie tickets to ten friends. If each
friend could get up to one ticket, how many ways can Alice distribute these
tickets?
3. We have n distinct books. Each book, independently and randomly, is placed
into one of n shelves. What is the probability that there are no empty shelves
at the end of our experiment?
2.2 (10 points)
You are given n = 2k
compact discs, all of which look identical. However, there
is one defective disc among all discs — it weighs different than the rest. You are
also given an equivalence tester, which has two compartments. You could place
any set of objects in each compartment, and the tester tells you whether or not the
two sets weigh the same. Note that the tester doesn’t tell you which side is heavier
and which one lighter.
Your goal is to use the tester at most k times to determine which of the discs is
defective. You may assume that k 1. Can you describe your method and briefly
explain why it works? (Note that you are allowed to use the tester only k times,
not O(k). You will receive partial credit for slightly worse solutions.)
2