Advanced Data Structures (Q1+Q2, 2013)

Messages

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 and Peyman Afshani.

Lectures

3 hours per week. Tuesdays 9.15-12.00. Q1 in iNANO auditorium (1593-012A), Q2 in Peter Bøgh Andersen Aud., Finlandsgade 21 (5335-016).

Course plan

Week Date Content Literature Slides
35 27/8 Binomial queues, Fibonacci heaps [V78], [FT87, Sections 1-2,4],[DGST88, Section 1] pptx|pdf
36 3/9 Lecture cancelled
37 10/9 Finger search trees, skip lists, treaps [B05, Sections 11.1-11.4],[LO88] pptx|pdf
38 17/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
39 24/9 Orthogonal Point Location on the Word RAM
Lecture by Peyman Afshani		 [C11]  
40 1/10 Implicit Dictionaries and Sorting [FG03, Section 1],[FG05, Section 1] pptx|pdf
41 8/10 Nearest Common Ancestors, Discrete Range Searching, Cartesian Trees [AGKR02, Sections 1-2] pptx|pdf
42-44 Fall break
45 5/11 Maintaining Order in a List [DS87] pptx|pdf
46 12/11 Partial and Full Persistence, Fractional Cascading [ST86a], [DSST89, Sections 1-3], [CG86] pptx|pdf
47 19/11 Functional Data Structures: Queues, Dequeues, Catenable Lists [O95],[KT99, Sections 1-2, 7] pptx|pdf
48 26/11 Retroactive Data Structures [DIL04] pptx|pdf
49 3/12 Unified Property for Dictionaries [BCDI07] pptx|pdf
50 10/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 17/12 Selection: X+Y and Binary Heaps [FJ82],[F93, Section 1] pptx|pdf

Literature (tentative)

  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. [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.
  15. [ST86a] Neil Sarnak, Robert E. Tarjan, Planar point location using persistent search trees, Communications of the ACM, 29(7): 669-679, 1986.
  16. [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.
  17. [CG86] Bernard Chazelle, Leonidas J. Guibas, Fractional Cascading: I. A Data Structuring Technique, Algorithmica, 1(2): 133-162, 1986.
  18. [O95] Chris Okasaki, Simple and efficient purely functional queues and deques, Journal of Functional Programming 5(4): 583-592, 1995
  19. [KT99] Haim Kaplan and Robert E. Tarjan, Purely functional, real-time deques with catenation, Journal of the ACM, 46(5): 577-603, September 1999.
  20. [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.
  21. [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.
  22. [O05] Chris Okasaki, Alternatives to Two Classic Data Structures, Symposium on Computer Science Education (SIGCSE), 162-165, 2005.
  23. [ST86b] Daniel Dominic Sleator and Robert Endre Tarjan, Self-Adjusting Heaps, SIAM Journal of Computing, 15(1): 52-69, 1986.
  24. [ST85] Daniel Dominic Sleator and Robert Endre Tarjan, Self-Adjusting Binary Search Trees, Journal of the ACM, 32(3): 652-686, 1985.
  25. [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.
  26. [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 2013).

Credits

10 ETCS points.

Prerequisites

Algoritmer og Datastrukturer 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.

The oral exams take place January 14-17, 2014 in Nygaard 298.