Advanced Data Structures (Q1+Q2, 2015)

Aims

The participants will after the course have detailed knowledge of many advanced data structures and general design techniques for the construction of data structures and practical experience with implementation, evalutation, and comparison of complex data structures. The working method of the course will also train the participants to read and understand research papers.

Goals

The participants must at the end of the course be able to:

Contents

Selected topics in data structures. Possible topics: Fractional cascading. Persistence: Partial persistence, Full persistence, Purely functional data structures (catenable lists). Deamortization techniques. Dynamization techniques. Sorting vs. Priority queues. RAM data structures. Dictionaries. Priority queues. List order maintenance. Interpolation search. Least common ancestor data structures. Finger search trees. Succint data structures. Implicit data structures. Deterministic hashing. Priority queues: Binomial heaps, Fibonacci heaps, Skew heaps. van Emde Boas data structures. Union-split-find data structures. Union-find data structures. Selection in heaps. Planar separators.

Lecturers

Gerth Stølting Brodal.

Lectures

3 hours per week. Wednesdays 11.15-14.00, Nygaard 184.

Course plan (tentative)

Week Date Content Literature Slides
35 26/8 Binomial queues, Fibonacci heaps [V78], [FT87, Sections 1-2,4],[DGST88, Section 1] pptx|pdf
36 2/9 Finger search trees, skip lists, treaps [B05, Sections 11.1-11.4],[LO88] pptx|pdf
37 9/9 RAM data structures: van Emde Boas Trees, Search Trees, Priority Queues [BKZ77, Sections 1-5],[A95, Sections 1-4.2],[T96, Sections 1-2],[AH92, Sections 2-3] pptx|pdf
38 16/9 Implicit Dictionaries and Sorting
(Selection)		 [FG03, Section 1],[FG05, Section 1] pptx|pdf
(pptx|pdf)
39 24/9 Nearest Common Ancestors, Discrete Range Searching, Cartesian Trees [AGKR02, Sections 1-2] pptx|pdf
40 30/9 Invertible Bloom Filters
Lecture by Kasper Green Larsen		 [GM11]  
41 7/10 Unified Property for Dictionaries [BCDI07] pptx|pdf
42-44 Fall break
45 4/11 Maintaining Order in a List [DS87] pptx|pdf
46 11/11 Partial and Full Persistence, Fractional Cascading [ST86a], [DSST89, Sections 1-3], [CG86] pptx|pdf
47 18/11 Functional Data Structures: Queues, Dequeues, Catenable Lists [O95],[KT99, Sections 1-2, 7] pptx|pdf
48 25/11 Orthogonal Point Location on the Word RAM
Lecture by Peyman Afshani		 [C11]  
49 2/12 Retroactive Data Structures [DIL04] pptx|pdf
50 9/12 Maxiphobic Heaps, Self Adjusting Data Structures: Heaps and Search Trees [O05, Section 3],[ST86b, Sections 1-3],[ST85, Sections 1-3] pptx|pdf
51 16/12 Selection: X+Y and Binary Heaps [FJ82],[F93, Section 1] pptx|pdf

Literature (tentative)

Many of the below references link to the official versions of the papers at the publishers websites. Some of the publications require paid subscription for achieving access. AU has paid subscriptions to these publications, which are available when you are on a AU network, e.g. using VPN.

  1. [V78] Jean Vuillemin, A data structure for manipulating priority queues, Communications of the ACM, 21(4): 309-315, 1978.
  2. [FT87] Michael L. Fredman, Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), 34(3): 596-615, 1987.
  3. [DGST88] James R. Driscoll, Harold N. Gabow, Ruth Shrairman, Robert E. Tarjan Relaxed heaps: an alternative to Fibonacci heaps with applications to parallel computation, Communications of the ACM, 31(11): 1343-1354, 1988.
  4. [B05] Finger Search Trees, Gerth Stølting Brodal, In Handbook of Data Structures and Applications, Dinesh Mehta and Sartaj Sahni (Edt.), 11 pages. CRC Press, 2005.
  5. [LO88] A balanced search tree with O(1) worst-case update time, Christos Levcopoulos, Mark H. Overmars, Acta Informatica, November 1988, Volume 26, Issue 3, pp 269-277.
  6. [BKZ77] P. van Emde Boas, R. Kaas, and E. Zijlstra, Design and Implementation of an Efficient Priority Queue, Mathematical Systems Theory 10, 99-127, 1977
  7. [A95] Arne Andersson, Sublogarithmic Searching Without Multiplications, In Proc. 36th IEEE Symposium on Foundations of Computer Science (FOCS), 655-663.
  8. [T96] Mikkel Thorup, On RAM priority queues, In Proc. 11th Annual ACM-SIAM symposium on Discrete algorithms (SODA), 59-67, 1996.
  9. [AH92] Susanne Albers and Torben Hagerup, Improved Parallel Integer Sorting without Concurrent Writing, In Proc. 7th Annual ACM-SIAM symposium on Discrete algorithms (SODA), 463-472, 1992.
  10. [C11] Timothy Chan, Persistent predecessor search and orthogonal point location on the word RAM, In Proc. 22nd Annual ACM-SIAM symposium on Discrete algorithms (SODA), 1131-1145, 2011.
  11. [FG03] Gianni Franceschini and Roberto Grossi, Optimal Cache-Oblivious Implicit Dictionaries, Proc. 30th International Colloquium on Automata, Languages, and Programming, volume 2719 of Lecture Notes in Computer Science, 316-331, Springer-Verlag, 2003.
  12. [FG05] Gianni Franceschini and Viliam Geffert, An in-place sorting with O(n log n) comparisons and O(n) moves, Journal of the ACM, 52(4): 515-537, July 2005.
  13. [AGKR02] Stephen Alstrup, Cyril Gavoille, Haim Kaplan, Theis Rauhe, Nearest common ancestors: a survey and a new distributed algorithm, Proceedings of the Fourteenth Annual ACM Symposium on Parallel Algorithms and Architectures, 258-264, 2002.
  14. [GM11] Michael T. Goodrich, Michael Mitzenmacher. Invertible Bloom Lookup Tables, arXiv:1101.2245v2, 2011.
  15. [BCDI07] Mihai Badoiu, Richard Cole, Erik D. Demaine, and John Iacono, A unified access bound on comparison-based dynamic dictionaries, Theoretical Computer Science, 382(2): 86-96, 2007.
  16. [DS87] P. Dietz, D. Sleator, Two algorithms for maintaining order in a list, Proceedings of the Nineteenth Annual ACM Conference on Theory of Computing, 365-372, 1987.
  17. [ST86a] Neil Sarnak, Robert E. Tarjan, Planar point location using persistent search trees, Communications of the ACM, 29(7): 669-679, 1986.
  18. [DSST89] James R. Driscoll, Neil Sarnak, Daniel D. Sleator, Robert E. Tarjan, Making Data Structures Persistent, Journal of Computer and System Sciences, 38(1): 86-124, 1989.
  19. [CG86] Bernard Chazelle, Leonidas J. Guibas, Fractional Cascading: I. A Data Structuring Technique, Algorithmica, 1(2): 133-162, 1986.
  20. [O95] Chris Okasaki, Simple and efficient purely functional queues and deques, Journal of Functional Programming 5(4): 583-592, 1995
  21. [KT99] Haim Kaplan and Robert E. Tarjan, Purely functional, real-time deques with catenation, Journal of the ACM, 46(5): 577-603, September 1999.
  22. [DIL04] Erik D. Demaine, John Iacono, and Stefan Langerman, Retroactive Data Structures, Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, 274-283, 2004.
  23. [O05] Chris Okasaki, Alternatives to Two Classic Data Structures, Symposium on Computer Science Education (SIGCSE), 162-165, 2005.
  24. [ST86b] Daniel Dominic Sleator and Robert Endre Tarjan, Self-Adjusting Heaps, SIAM Journal of Computing, 15(1): 52-69, 1986.
  25. [ST85] Daniel Dominic Sleator and Robert Endre Tarjan, Self-Adjusting Binary Search Trees, Journal of the ACM, 32(3): 652-686, 1985.
  26. [FJ82] Greg N. Frederickson, Donald B. Johnson, The Complexity of Selection and Ranking in X+Y and Matrices with Sorted Columns, Journal of Computer and System Sciences 24(2): 197-208, 1982.
  27. [F93] Greg N. Frederickson, An Optimal Algorithm for Selection in a Min-Heap, Inf. Comput. 104(2): 197-214, 1993.

Projects

Quarter

1st and 2nd (Fall 2015).

Credits

10 ETCS points.

Prerequisites

Algorithms and Data Structures 1+2.

Course language

Danish or English.

Evaluation

3 group projects (2-3 persons per group) and individual oral exam, 7-scale, internal examiner.

Exam

The exam takes 20 minutes, including evaluation. The exam will be a discussion of the reports on the projects and the material covered in class (see "course plan" above). The final grade will be based on the project reports and the oral examination.