CS 840 Assignment 2
Due November 2, 2020
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 (We are discussing the first couple of sections of this paper in class).
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.