Advanced Data Structures


Lecture Info

Lecturer:  Moshe Lewenstein

Prerequisites: Basic courses in Data Structures and Algorithms



Homework 1.           (on amortized analysis)
Homework 2.           (on hash function constructions)
Homework 3.           (on predecessor queries and word packing)
Homework 4.           (on self-adjusting data structures)


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.
SIAM Journal on Computing 23(4): 738-761, 1994.
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.
SIAM J. on Computing, 8(1):82-110, 1979.
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.
SIAM J. on Computing , 10(3):613-637, 1981.

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, Eugene W. Myers. Suffix Arrays: A New Method for On-Line String Searches. SIAM J. on Computing 22(5): 935-948 (1993).
Richard M. Karp, Raymond E. Miller,
Arnold L. Rosenberg. Rapid Identification of Repeated Patterns in Strings, Trees and Arrays. In Proc. of Symposium on Theory of Computing (STOC) 1972: 125-136.
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

Algoritmer og Datastrukturer 1, Gerth Brodal, Aarhus U.    (For those of you who read Danish)
Algoritmer og Datastrukturer 2, Gerth Brodal, Aarhus U.   (For those of you who read Danish)