CS 840 Assignment 2
Due November 2, 2020
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:
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.