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.