Advanced Data Structures
Lecture Info
Lecturer: Moshe Lewenstein
Prerequisites: Basic courses in Data
Structures and Algorithms
Homework
Homework 1. (on amortized analysis)
Reading
Material
amortized analysis
Cormen, Leiserson, Rivest, Stein – Introduction to Algorithms
Perfect hash constructions
Michael L. Fredman,
János Komlós, Endre Szemerédi: Storing a Sparse
Table with 0(1) Worst Case Access Time. Journal of the ACM 31(3):
538-544, 1984.
Martin Dietzfelbinger, Anna R. Karlin,
Kurt Mehlhorn, Friedhelm
Meyer auf der Heide, Hans
Rohnert, Robert Endre Tarjan:
Dynamic Perfect Hashing: Upper and Lower Bounds.
Rasmus Pagh and Flemming F. Rodler: Cukoo Hashing. J. of Algorithms
51:122-144, 2004.
van Emde Boas trees
P. van Emde Boas.
Preserving order in a forest in less than logarithmic time
and linear space. Information Processing Letters, 6(3):80-82,
1977.
P. van Emde Boas, R. Kaas, and E. Zijlstra.
Design and implementation of an efficient priority queue. Math.
Systems Theory, 10:99-127, 1977.
x-fast-tries and y-fast-tries
Dan E. Willard. Log-logarithmic
worst case range queries are possible in space Θ(n).
Information Processing Letters, 17(2):81-84, 1983.
Dan E. Willard. New trie data
structures which support very fast search operations. Journal of
Computer and System Sciences, 28(3):379-394, 1984.
Exponential search trees
A. Andersson. Faster
deterministic sorting and searching in linear space. Proc. 37th IEEE Symposium on
Foundations of Computer Science (FOCS), 1996.
Fusion trees
Michael L. Fredman and Dan E. Willard. Surpassing the information
theoretic bound with fusion trees. Journal of Computer and System Sciences, 47:424-436,
1993
Self Adjusting Linked Lists
Ronald Rivest. On self-organizing sequential search
heuristics. Communications of the ACM, 19(2):63-67, 1976.
J.L.
Bentley and C.C. Mcgeoch. Amortized
analysis of self-organizing sequential search heuristics. Communications
of the ACM, 28:404-411, 1985.
J.R. Bitner. Heuristics that dynamically
organize data structures.
F.R.K. Chung, D.J. Hayela, P.D. Seymour. Self-organizing
sequential search and Hilbert's inequalities. J. of Computer and
System Sciences, 47(3):424-436, 1993.
G.H. Gonnet, J.I. Munro, and H. Suwanda. Exegesis
of self-organizing linear search.
Splay Trees
Danny Sleator and Robert E. Tarjan. Self adjusting binary search trees. Journal of the ACM, 32(3):652-686, 1985.
Suffix Arrays
Udi Manber,
Richard M. Karp, Raymond E. Miller,
Juha Kärkkäinen, Peter
Sanders. Simple Linear Work Suffix Array Construction.
In Proc. of ICALP 2003: 943-955.
M. Muthukrishnan, Efficient algorithms for document
retrieval problems. In Proc. of SODA 2002.
Other Advanced Data Structure Courses
Static Data Structures, Faith Fich, U. of Toronto (2000)
Dynamic Data Structures, Faith Fich, U. of Toronto (2003)
Erik Demaine, MIT (2003)
Data Structures and Data
Management, Ian Munro, U. of Waterloo (2004)
Advanced Data Structures
and Algorithms, Rajeev Motwani, U. of Stanford, (2003/4)
Advanced
Topics in Data Structures, Haim Kaplan, Tel Aviv U.
(2003)
Data
Structures and Graph Algorithms, Robert Tarjan,
Princeton U.
External Memory Algorithms and Data
Structures, Gerth Brodal,
U. of Aarhus, 2001