Lectures:  Monday 10:1512 and Thursday 10:1512:00, room 021 (ground floor of the MPIINF building E1.4) 

Lecturers:  Paweł Gawrychowski and Mayank Goswami and Patrick Nicholson 
Tutorials:  Monday 14:1516:00, room 023 (ground floor of the MPIINF building) 
Tutors:  TBD 
Exam dates:  July 25th 10:3013:30 room 24 (exam) August 25th 12:1515:00 room 21 (reexam) 
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 selfcontained, and only assumes a basic undergraduate data structures course (e.g., knowledge of redblack trees, Btrees, etc.).
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): 236250 (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): 8094 (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): 6674 (1986) [Ref. 4] H. Alt, K. Mehlhorn, J.I. Munro: Partial Match Retrieval in Implicit Data Structures. Inf. Process. Lett. 19(2): 6165 (1984) Possible starting points for projects: [Ref. 5] G. Franceschini et al.: Implicit Btrees: a new data structure for the dictionary problem. J. Comput. Syst. Sci. 68(4): 788807 (2004) [Ref. 6] G. Franceschini, R. Grossi: Optimal Implicit Dictionaries over Unbounded Universes. Theory Comput. Syst. 39(2): 321345 (2006) [Ref. 7] G. Franceschini, R. Grossi: Optimal WorstCase Operations for Implicit CacheOblivious Search Trees. WADS 2003: 114126 [Ref. 8] G. Brodal, C. KejlbergRasmussen, J. Truelsen: A CacheOblivious Implicit Dictionary with the Working Set Property. ISAAC (2) 2010: 3748 [Ref. 9] G. Brodal, C. KejlbergRasmussen: CacheOblivious Implicit Predecessor Dictionaries with the WorkingSet Property. STACS 2012: 112123 [Ref. 10] G. Brodal, J. Nielsen, J. Truelsen: Finger Search in the Implicit Model. ISAAC 2012: 527536 
Implicit DS Slides  
Apr 28  Multikey Search (continued) and The WordRAM Model [Ref. 11] J. Ian Munro: Searching a Two Key Table Under a Single Key. STOC 1987: 383387 [Ref. 12] Larry Carter, Mark N. Wegman: Universal Classes of Hash Functions. J. Comput. Syst. Sci. 18(2): 143154 (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): 538544 (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): 406424 (1991) 
Homework Sheet #2 Implicit DS Slides WordRAM & 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. 549554 [Ref. 16] R. Raman, V. Raman, S. Rao: Succinct indexable dictionaries with applications to encoding kary 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.

WordRAM & 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. 118126. 
Homework Sheet #3 WordRAM & Succinct DS 

May 12  Lower Bounds via the Reciprocal Property [Ref. 20] Alexander Golynski: Cell probe lower bounds for succinct data structures. SODA 2009: 625634 Possible starting points for projects:  If you are interested in this paper, please come see me to discuss possible projects

WordRAM & 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): 427462 (1988) [Ref. 22] Roberto Grossi, Ankur Gupta, Jeffrey Scott Vitter: Highorder entropycompressed text indexes. SODA 2003: 841850 [Ref. 23] Travis Gagie, Simon J. Puglisi, Andrew Turpin: Range Quantile Queries: Another Virtue of Wavelet Trees. SPIRE 2009: 16 
Homework Sheet #4 WordRAM & 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: 3748 [Ref. 25] Rajeev Raman, S. Srinivasa Rao: Succinct Dynamic Dictionaries and Trees. ICALP 2003: 357368 and [Ref. 3] (again) Possible starting points for projects: [Ref. 26] Stelios Joannou, Rajeev Raman: An Empirical Evaluation of Extendible Arrays. SEA 2011: 447458 [Ref. 27] Gonzalo Navarro, Yakov Nekrich: Optimal Dynamic Sequence Representations. SODA 2013: 865876 
WordRAM & Succinct DS 

May 22  Van Emde Boas, xfast and yfast 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^{0} instruction only [Ref. 33] M. Thorup On AC^{0} 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^{0} instruction only [Ref. 33] M. Thorup On AC^{0} 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:WordRAM, pointer
machine, orthogonal range reporting in pointer machine. [Ref. 35] Michael BenOr 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 complexitya 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, Btrees. [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 9creditpoints advanced lecture. There will be two 90 minutes lecture and one 90 minutes tutorial session per week. 