### **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