CS 840 Assignment 3

Due November 22, 2016

Instructor: I. Munro


This assignment deals with persistence and developments regarding it. 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 on the topic Driscoll, Sarnak, Sleator and Tarjan paper.

Have a look two or three of the key follow-up papers:

Driscoll, Sleator and Tarjan

Dietz and Raman


Fiat and Kaplan (on confluential persistence)

These will give a general feel for some of the basic work on persistence.

Pick one of the four and write a 2 to 3 page review of the paper. (Note the original DSST paper is very long and the others give a better opportunity to focus)


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

And especially your own comments

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

d)     Comment on any possible (nonobvious) extensions.