CS 840 Assignment 3

Due November 30, 2020

Instructor: I. Munro


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

Read the original on the topic Driscoll, Sarnak, Sleator and Tarjan paper.

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

Driscoll, Sleator and Tarjan

Dietz and Raman


Fiat and Kaplan (on confluential persistence)

Pick one of the three and write a 2 to 3 page review of the paper. Alternatively, you may choose the original DSST paper but only if you had not encountered persistence, as used in these papers, 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

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.