Description

Where to submit: On Gradescope, please mark the pages for each question
1 Problem 1 (20 points)
1.1 (5 points)
Prove that, if , 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.
2.
3. 4.
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
.
2 Problem 2 (20 Points)
2.1 (10 points)
1. Prove by induction that 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.
2