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