CS 840 Assignment 2

Due November 3, 2016

Instructor:

This assignment deals with splay trees and developments regarding them. I realize that some members of the class have much more background on this topic than others, so I am hoping each of you can find the appropriate aspect upon which to concentrate.

Read/ review the original Sleator and Tarjan paper on the topic.

Have a look at a couple of the key follow-up papers:

Demaine et al
(the Tango tree paper)

Wang et al
(another lg lg n competitive approach)

Pick **one
**of the three and write a 2 to 3 page review of the paper. (You may choose
the original S&T paper only if you had not encountered splay trees before
this course)

Your review should:

a) Outline the main results of the paper

b) Outline the approaches of the proofs of the main results … and the difficult aspects of the proofs

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

d) Comment on any possible (nonobvious) extensions.