Questions preceded by a * are optional. Although they can be skipped without any deduction, it is important to know and understand the results they contain.
Ex. 1 — Karger-Stein’s Algorithm
In the lectures, although Karger-Stein’s Algorithm was presented (5.28|5.243), only a sketch of proof was provided (5.29|5.244). In this exercise we want to prove the missing part, i.e. solve the recurrence relation
1
t
2
− (1
(
)) .
P(t) = 1
−
P
√
2
2
1. Prove that the probability of a cut to survive when n < 6, at least 1/15.
2. Using an appropriate change of variable, show that
3. Let zk = 4/pk − 1.
a) Prove that
pk+1
p0
zk+1
z0
• pk − 14 pk2,
• 1/15.
1
= zk + 1 + ,
zk
* b) Show that for all k ≥ 0, k < zk < 59 + 2k.
√
4. Recalling that t = n/ 2 and noting that the depth of the recursion is 2 log2 n + O(1), conclude that P(n) = Ω(1/ log n).
Ex. 2 — Critical thinking
1. Is it possible to design a stack supporting push, pop, and retrieving the minimum element in constant time? Explain.
2. A total of n ants are walking at speed 1 m/s on a thin 1 m long cable; if they collide they instantly reverse direction, and if an ant reaches the end of the cable it falls. How long will it take before all the ants have fallen?
