CS 840 Assignment 3

Due November 30, 2020

Instructor:

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:

and

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.