The literature for the course consists of articles and excerpts from textbooks. Except for the book by Cormen et al., all material will be available electronically, in the form of (doi) links or scans (in which case, they will only be accessible via Itslearning due to copyright issues).

Material will be announced here on a weekly basis, but I'm listing (a little more than) the material that I think I will use, roughly in the right order.

Some typos for articles are registered in the errata.

Amortized Analysis [CLRS09]

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.
Introduction to Algorithms, 3rd ed.
The MIT Press, 2009, 451-478.
ISBN 978-0-262-53305-8.
You should own this book.

Leftists Heaps [T83]

Robert Endre Tarjan.
Data Structures and Network Algorithms.
Society for Industrial and Applied Mathematics, 1983, 38-43.
ISBN 0-89871-187-8.
Available via Itslearning.

Skew Heaps [W95]

Mark Allen Weiss.
Data Structures and Algorithm Analysis, 2nd ed.
The Benjamin/Cummings Publishing Company, Inc., 1995, 195-197, 425-427.
ISBN 0-8053-9057-X.
Available via Itslearning.

Skip Lists [P89]

William Pugh.
Skip Lists: A Probabilistic Alternative to Balanced Trees.
Lecture Notes in Computer Science 382.
Springer-Verlag, 1989, 437-449.
ISBN 3-540-51542-9.
Link (you may have to be logged in at SDU) - also available via Itslearning.

Persistent Data Structures [DSST89]

James R. Driscoll, Neil Sarnak, Daniel D. Sleator, Robert E. Tarjan.
Making Data Structures Persistent.
Journal of Computer and System Sciences 38.
Academic Press, Inc., 1989, 86-97.
ISBN 022-0000.
Link (you may have to be logged in at SDU) - also available via Itslearning.

Scapegoat Trees [GR93]

Igal Galperin, Ronald L. Rivest.
Scapegoat Trees.
Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms.
ACM Press, 1993, 165-174.
ISBN 0-89871-313-7.
Link (you may have to be logged in at SDU) - also available via Itslearning.

Disjoint Sets [K90]

Jeffrey H. Kingston.
Algorithms and Data Structures - Design, Correctness, Analysis.
Addison Wesley, 1990, 202-218.
ISBN 0-201-41705-7.
Available via Itslearning.

Disjoint Sets with Backtracking [WT89]

Jeffrey Westbrook, Robert E. Tarjan.
Amortized Analysis of Algorithms for Set Union with Backtracking.
SIAM Journal on Computing 18(1).
Society for Industrial and Applied Mathematics, 1989, 1-11.
ISBN 0097-5397.
Link (you may have to be logged in at SDU) - also available via Itslearning.

Cuckoo Hashing [P06]

Rasmus Pagh.
Cuckoo Hashing for Undergraduates.
IT University, Copenhagen, 2006, 1-6.
Available via Itslearning.

On Doubling Techniques and Global Rebuilding [L20a]

Kim S. Larsen.

Lectures Notes, 1-5, 2020.
Available via Itslearning.
Summary of exercises.

Fibonacci Heaps [CLRS09]

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.
Introduction to Algorithms, 3rd ed.
The MIT Press, 2009, 505-530.
ISBN 978-0-262-53305-8.
You should own this book.

Fibonacci Heaps [L20c]

Kim S. Larsen.

Slides, 1-3, 2020.
Available via Itslearning.

Splay Trees [K90]

Jeffrey H. Kingston.
Algorithms and Data Structures - design, correctness, analysis.
Addison-Wesley, 1990, 98-102, 110-116.
ISBN 0-201-41705-7.
Available via Itslearning.

Splay Trees [L20d]

Kim S. Larsen.

Slides, 1-6, 2020.
Available via Itslearning.

Amortized Analysis of Red-Black Trees [L20b]

Kim S. Larsen.

Slides, 1-19, 2020.
Available via Itslearning.

Van Emde Boas Trees [GF03]

Gudmund Frandsen.
Van Emde Boas Trees.
Course lecture notes, 1-4, 2003.
Available via Itslearning.
A much more detailed account that could be helpful can be found in [CLRS, 531-556].

X- and Y-Fast Tries [W83]

Dan E. Willard.
Log-Logarithmic Worst-Case Range Queries are Possible in Space Θ(N).
Information Processing Letters 17.
North-Holland, 1983, 81-84.
Link (you may have to be logged in at SDU) - also available via Itslearning.
We will base the lecture on the notation used on the corresponding Wikipedia pages: X-fast trie, Y-fast trie.

Expected Maximal Chain Length

Kim S. Larsen.

Lectures Notes, 1-6.
Available via Itslearning.

Level Ancestors [BF03]

Michael A. Bender, Martín Farach-Colton.
The Level Ancestor Problem simplified.
Theoretical Computer Science 321.
Elsevier, 2003, 5-12.
Link (you may have to be logged in at SDU) - also available via Itslearning.

Relaxed Balance [L98]

Kim S. Larsen.
Amortized Constant Relaxed Rebalancing using Standard Rotations.
Acta Informatica 35(10).
Springer, 1998, 859-874.
Link (you may have to be logged in at SDU) - also available via Itslearning.

 

---