Literature

The literature for the course consists of articles and excerpts from textbooks. Material will be announced here on a weekly basis and will be distributed in class.
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.
Not distributed - 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.

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.

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.

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.

Universal and Perfect Hashing [CLRS09]
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.
Introduction to Algorithms, 3rd ed.
The MIT Press, 2009, 265-269, 277-282.
ISBN 978-0-262-53305-8.
Not distributed - you should own this book.

Disjoint Sets [K90]
Jeffrey H. Kingston.
Algorithms and Data Structures - Design, Correctness, Analysis.
Addison Wesley, 1990, 202-218.
ISBN 0-201-41705-7.

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.

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.

Rootish Arrays [M??]
Pat Morin.
Open Data Structures (in Java), edition 0.1F.
http://opendatastructures.org/.
49-61.

Dynamization [W93]
Derick Wood.
Data Structures, Algorithms, and Performance.
Addison-Wesley, 1993, 540-546, 558-563.
ISBN 0-201-52148-2.

Cuckoo Hashing [P06]
Rasmus Pagh.
Cuckoo Hashing for Undergraduates.
IT University, Copenhagen, 2006, 1-6.

Properties of Hashing by Chaining [LN-Hash]
Lectures Notes, 1-6.

Van Emde Boas Trees [F03]
Gudmund Frandsen.
Van Emde Boas Trees.
Aarhus, 2003, 1-5.

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.
We will base the lecture on the notation used on the corresponding Wikipedia pages.

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.

Level Ancestors [BF03]
Michael A. Bender, Martín Farach-Colton.
The Level Ancestor Problem simplified.
Theoretical Computer Science 321.
Elsevier, 2003, 5-12.

Relaxed Balance [L98]
Kim S. Larsen.
Amortized Constant Relaxed Rebalancing using Standard Rotations.
Acta Informatica 35(10).
Springer, 1998, 859-874.

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.
Not distributed - you should own this book.


Last modified: Mon Dec 5 20:02:11 CET 2016
Kim Skak Larsen (kslarsen@imada.sdu.dk)