Homework 8, Randomized Algorithms

Due date: April 29.

All references are to the course text.

Page 275, problem 9.1 (prove parts 1 and 2 of Theorem 8.8).
Hint. For Part 2, the concern is to determine how many times the immediate predecessor of pred(x), in the set of undeleted items, is deleted before x itself is deleted. Note that there are three cases according to the ancestor relationships among x, its predecessor and successor.

Page 275, problem 9.3.
Hint. The issue is to bound the expected number of cuts incurred by segment v. So express this as a Mulmuley Game.

Page 275, problem 9.4.
Hint. What is the probability that X_j(p)=1?

Course Home Page

cole@cs.nyu.edu (Richard Cole)
Last modified: Apr 3, 1997