VE477 Homework 7

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?