Efficient Data Structures

The course starts on the 17th of April.

Basic Information

Lectures:	Monday 10:15-12 and Thursday 10:15-12:00, room 021 (ground floor of the MPI-INF building E1.4)
Lecturers:	Paweł Gawrychowski and Mayank Goswami and Patrick Nicholson
Tutorials:	Monday 14:15-16:00, room 023 (ground floor of the MPI-INF building)
Tutors:	TBD
Exam dates:	July 25th 10:30-13:30 room 24 (exam) August 25th 12:15-15:00 room 21 (re-exam)

Description

Efficient data structures are an indispensable tool for the algorithm designer. Such structures are used as building blocks in widely deployed solutions for every day problems, such as text search (e.g., Google), and have revolutionized our ability to process information. Though many textbooks offer a thorough treatment of basic data structures, many important results and techniques are not covered in typical undergraduate courses. In contrast, this course will cover more advanced techniques, both classical and recent, from the area. Though we will cover state of the art techniques, the presentation is relatively self-contained, and only assumes a basic undergraduate data structures course (e.g., knowledge of red-black trees, B-trees, etc.).

Lectures (Topics marked with a * may change slightly depending on time)

Date	Topics	Lecture notes
Apr 17	Introduction, Implicit Data Structure Model, and Dynamic Dictionaries [Ref. 1] J.I. Munro, H. Suwanda: Implicit Data Structures for Fast Search and Update. J. Comput. Syst. Sci. 21(2): 236-250 (1980)	Implicit DS Slides Homework Sheet #1
Apr 21	No lecture (Easter Monday)
Apr 24	Dynamic Dictionaries (continued) and Multikey Search [Ref. 2] G. Frederickson: Implicit Data Structures for the Dictionary Problem. J. ACM 30(1): 80-94 (1983) [Ref. 3] J.I. Munro: An Implicit Data Structure Supporting Insertion, Deletion, and Search in O(log² n) Time. J. Comput. Syst. Sci. 33(1): 66-74 (1986) [Ref. 4] H. Alt, K. Mehlhorn, J.I. Munro: Partial Match Retrieval in Implicit Data Structures. Inf. Process. Lett. 19(2): 61-65 (1984) Possible starting points for projects: [Ref. 5] G. Franceschini et al.: Implicit B-trees: a new data structure for the dictionary problem. J. Comput. Syst. Sci. 68(4): 788-807 (2004) [Ref. 6] G. Franceschini, R. Grossi: Optimal Implicit Dictionaries over Unbounded Universes. Theory Comput. Syst. 39(2): 321-345 (2006) [Ref. 7] G. Franceschini, R. Grossi: Optimal Worst-Case Operations for Implicit Cache-Oblivious Search Trees. WADS 2003: 114-126 [Ref. 8] G. Brodal, C. Kejlberg-Rasmussen, J. Truelsen: A Cache-Oblivious Implicit Dictionary with the Working Set Property. ISAAC (2) 2010: 37-48 [Ref. 9] G. Brodal, C. Kejlberg-Rasmussen: Cache-Oblivious Implicit Predecessor Dictionaries with the Working-Set Property. STACS 2012: 112-123 [Ref. 10] G. Brodal, J. Nielsen, J. Truelsen: Finger Search in the Implicit Model. ISAAC 2012: 527-536	Implicit DS Slides
Apr 28	Multikey Search (continued) and The Word-RAM Model [Ref. 11] J. Ian Munro: Searching a Two Key Table Under a Single Key. STOC 1987: 383-387 [Ref. 12] Larry Carter, Mark N. Wegman: Universal Classes of Hash Functions. J. Comput. Syst. Sci. 18(2): 143-154 (1979) [Ref. 13] Michael L. Fredman, János Komlós, Endre Szemerédi: Storing a Sparse Table with 0(1) Worst Case Access Time. J. ACM 31(3): 538-544 (1984) Possible starting points for projects: [Ref. 14] A. Fiat et al. An Implicit Data Structure for Searching a Multikey Table in Logarithmic Time. J. Comput. Syst. Sci. 43(3): 406-424 (1991)	Homework Sheet #2 Implicit DS Slides Word-RAM & Succinct DS
May 1	No lecture (Labour Day)
May 5	Rank and Select and Tree Representations [Ref. 15] Guy Jacobson: Space Efficient Static Trees and Graphs. In Proc. FOCS 1989. pp. 549-554 [Ref. 16] R. Raman, V. Raman, S. Rao: Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Transactions on Algorithms (TALG), 3:4, No 43, 2007. [Ref. 17] Arash Farzan: Succinct Representations of Trees and Graphs. In particular Chapter 4. PhD Dissertation, University of Waterloo, 2009. Possible starting points for projects: [Ref. 18] M. Patrascu: Succincter In Proc. FOCS 2008. --- Explicit Idea: I would also like see a write up about the Indexable Dictionary (ID) structure Ref. 16. In particular, a list and description of all the hashing techniques used in the structure and related improvements to FKS hashing.	Word-RAM & Succinct DS
May 8	Representations of Graphs [Ref. 15], [Ref. 17] In particular Chapter 5 [Ref. 19] J. Ian Munro, V. Raman: Succinct Representation of Balanced Parentheses, Static Trees, and Planar Graphs In Proc. FOCS 1997. pp. 118-126.	Homework Sheet #3 Word-RAM & Succinct DS
May 12	Lower Bounds via the Reciprocal Property [Ref. 20] Alexander Golynski: Cell probe lower bounds for succinct data structures. SODA 2009: 625-634 Possible starting points for projects: --- If you are interested in this paper, please come see me to discuss possible projects	Word-RAM & Succinct DS
May 15	Wavelet Trees and Orthogonal Range Search [Ref. 21] Bernard Chazelle: A Functional Approach to Data Structures and Its Use in Multidimensional Searching. SIAM J. Comput. 17(3): 427-462 (1988) [Ref. 22] Roberto Grossi, Ankur Gupta, Jeffrey Scott Vitter: High-order entropy-compressed text indexes. SODA 2003: 841-850 [Ref. 23] Travis Gagie, Simon J. Puglisi, Andrew Turpin: Range Quantile Queries: Another Virtue of Wavelet Trees . SPIRE 2009: 1-6	Homework Sheet #4 Word-RAM & Succinct DS
May 19	Dynamic Data Structure Models/Memory Management [Ref. 24] Andrej Brodnik, Svante Carlsson, Erik D. Demaine, J. Ian Munro, Robert Sedgewick: Resizable Arrays in Optimal Time and Space. WADS 1999: 37-48 [Ref. 25] Rajeev Raman, S. Srinivasa Rao: Succinct Dynamic Dictionaries and Trees. ICALP 2003: 357-368 and [Ref. 3] (again) Possible starting points for projects: [Ref. 26] Stelios Joannou, Rajeev Raman: An Empirical Evaluation of Extendible Arrays. SEA 2011: 447-458 [Ref. 27] Gonzalo Navarro, Yakov Nekrich: Optimal Dynamic Sequence Representations. SODA 2013: 865-876	Word-RAM & Succinct DS
May 22	Van Emde Boas, x-fast and y-fast trees. Possible starting points for projects: [Ref. 28] C. W. Mortensen et al. On dynamic range reporting in one dimension	Homework Sheet #5 slides
May 26	The static structure of Beame and Fich. Possible starting points for projects: [Ref. 29] M. Karpinski and Y. Nekrich Predecessor queries in constant time?	Homework Sheet #6 slides
May 29	No lecture (Ascension)
June 2	The static structure continued. I'm really interested n understanding these two papers: [Ref. 30] M. Ruzic Making deterministic signatures quickly [Ref. 31] M. Ruzic Constructing Efficient Dictionaries in Close to Sorting Time	slides
June 5	Fusion trees. [Ref. 32] A. Andersson et al. Fusion trees can be implemented with AC⁰ instruction only [Ref. 33] M. Thorup On AC⁰ implementations of fusion trees and atomic heaps	Homework Sheet #7 slides
June 9	No lecture (Whit Monday)
June 12	Exponential search trees and introduction to persistence.	slides
June 5	Fusion trees. [Ref. 32] A. Andersson et al. Fusion trees can be implemented with AC⁰ instruction only [Ref. 33] M. Thorup On AC⁰ implementations of fusion trees and atomic heaps	Homework Sheet #7 slides
June 16	Introduction to lower bounds: Decision trees and comparison model, algebraic decision trees. [Ref. 34] Jeff Erickson's notes on algebraic decision trees	Slides
June 19	No lecture (Corpus Christi)
June 23	Algebraic decision trees. Models of Computation 1:Word-RAM, pointer machine, orthogonal range reporting in pointer machine. [Ref. 35] Michael Ben-Or Lower bounds for algebraic computation trees. [Ref. 36] Kasper Green Larsen Ph.D. Thesis [Ref. 37] Bernard Chazelle Lower bounds for orthogonal range searching: the reporting case	Slides Assignment 8
June 26	Indexability model, orthogonal range reporting. Cell probe model membership lower bounds. [Ref. 38] V.Samoladas, D.P.MirankerA lower bound theorem for indexing schemes and its application to multidimensional range queries [Ref. 39] A.C.Yao Should tables be sorted?	Slides
June 30	The order maintenance problem. [Ref. 40] M. Bender et al. Two Simplified Algorithms for Maintaining Order in a List	Slides
July 3	Making arrays fully persistent. [Ref. 41] P. Dietz Fully persistent arrays	Slides
July 7	Cell probe membership. Communication complexity lower bounds. [Ref. 42] P.B.MiltersenCell ProBe complexity-a survey [Ref. 43] Mihai Patrascu's thesis	Slides
July 10	Chronogram technique of Fredman and Saks, Bloom filter lower bounds, External memory introduction, searching lower bounds, B-trees. [Ref. 44] Fredman and Saks The cell probe complexity of dynamic data structures [Ref. 45] Carter et. al Exact and approximate membership testers	Slides Practice set Practice set solutions
July 14	No lecture (Mayank is away)
July 17(Moved to July 18)	Lower bounds on sorting and permuting, external algebraic decision trees, Buffer trees, the dictionary problem in external memory and lower bounds. [Ref. 46] Aggarwal and Vitter The Input/Output complexityof sorting and related problems [Ref. 47] Jeff Erickson's notes on external memory.	Slides
July 21	Project discussion.
July 24	Recap.

Prerequisites:	An undergraduate course in algorithms is a must. Additionally, some basic familiarity with programming (in any reasonable language) would be welcome.
Class Info:	This is a 9-credit-points advanced lecture. There will be two 90 minutes lecture and one 90 minutes tutorial session per week.

More Courses of the Algorithms and Complexity Group