### **Homework 6, Randomized Algorithms**

Due date: April 8.

All references are to the course text.

Page 230, problem 8.5.

Hint. A "good event" in Game A is a selection that reduces by at
least 1/2 the number of items larger than the current largest selected
player.
By bounding the number of good events, show that with probability
1-1/n^k, for a given constant k, there is a constant c such that
the game has value no more than c log n.

Page 230, problem 8.6.

Hint. One approach is to do a direct analysis; i.e., write and solve
a recurrence for S_l(k), the expected number of elements in the left
subtree of the rank k item (and symmetrically for S_r(k),
the expected number of elements in the right
subtree of the rank k item).

Page 230, problem 8.7.

Hint.
Consider the length of the path from the least common ancestor
of x and y to each of x and y.

Page 231, problem 8.12.

Course Home Page

cole@cs.nyu.edu (Richard Cole)

Last modified: Mar 20, 1997