VE477 Homework 7

Description

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

* b) Show that for all k ≥ 0, k < z_k < 59 + 2k.

√

4. Recalling that t = n/ 2 and noting that the depth of the recursion is 2 log₂ 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?