89-520 - Data Structures
Test Info:
The test will be
closed book - i.e. without any external material (bring your pen with you).
There will be 4-5 questions.
Prepare by doing homework and reviewing the material.
Lecture Info
Lecturer: Moshe Lewenstein
Hours:
Group 1: Mon
12-2
Group 2: Thu: 12-2
Prerequisites: Basic courses in Data
Structures (89-120) and Algorithms (89-220)
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
Homework
Homework 1: (relevant
material - van Emde Boas, x-fast-tries, y-fast-tries, perfect hash
construction).
Homework
2.
Reading
Material
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.
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.
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.