CS 840 Assignment 2

Due March 8, 2013

Instructor: I. Munro

Read the two papers given below:
Dynamic Optimality by Demaine et al

and

Thresholds and optimal binary comparison search trees by Anderson et al

Both deal with competitiveness of search trees.

Pick one of the two and write a 2 to 3 page review of the paper. Your review should:

a) Outline the main results of the paper

b) Outline the approaches of the proofs of the main results

c) Note the key ideas in the proofs and indicate your level of understanding/clarity of paper.

d) Comment on any possible extensions.