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
firstname.lastname@example.org (Richard Cole)
Last modified: Mar 20, 1997