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.

Tuesday Januar 14, 2014 (Censor: Kristoffer Arnsfelt, Language: Danish or English)

09:00  20073241 Bo Mortensen                            17
09:20  20071580 Mads Ravn                               17
09:40  20082340 Simon Bilskov Jespersen                 17
10:00  20092817 Roland Larsen Pedersen                   5
10:20  20092926 Jan Hessellund Knudsen                   5
10:40  20094539 Kris Vestergaard Ebbesen                 5
11:00  20102222 Nicklas Arenth Pingel                    1
11:20  20103616 Christian Budde Christensen              1
11:40  20107539 Lukas Walther                            1
12:30  20082178 Henrik Knakkegaard Christensen           4
12:50  20092935 Julian Simon Nielsen                     4
13:10  20096365 Frederik Lønstrup Hansen                 4
13:30  20105640 Jakob Peter Landbo                       9
13:50  20106348 Casper Bo Kærgaard Green                 9
14:10  20106624 Anders Høst Mikkelsen                    9
14:30  20071625 David Niklas Johannsen                  11
14:50  20102060 Malene Sjørslev Søholm                  11
15:10  20104319 Helene Flyvholm Haagh                   11

Wednesday Januar 15, 2014 (Censor: Kristoffer Arnsfelt, Language: Danish or English)

09:00  20033980 Anders Strand-Holm Vinther              16
09:20  20105951 Martin Bjerrum Henriksen                16
09:40  20117331 Jon Bjerrum Jacobsen                    16
10:00  20022362 Morten Krogh-Jespersen                   2
10:20  20095039 Troels Leth Jensen                       2
10:40  20103316 Kristoffer Just Andersen                 2
11:00  20051948 Michael Bisgaard Olesen                  3
11:20  20092138 Jacob Damgaard Jensen                    3
11:40  20093713 Torben Muldvang Andersen                 3

Thursday Januar 16, 2014 (Censor: Peyman Afshani, Language: English)

09:00  20093007 Lauge Mølgaard Hoyer                     7
09:20  20094584 Stig Rohde Døssing                       7
09:40  20096300 Bjarke Bondo Andersen                    7
10:00  20101838 Andreas Mathisen                         8
10:20  20112300 Kasper Martin Tvede                      8
10:40  20114270 Nick Bakkegaard                          8
11:00  20103940 Mathias Rav                             12
11:20  20104223 Michael Christian Søndergaard           12

Friday Januar 17, 2014 (Censor: Peyman Afshani, Language: English)

09:00  20022669 Jens Christian Christensen Jensen       13
09:20  20085473 Ulrik Sahl Lystbæk                      13
09:40  20091182 Kasper Nielsen                          15
10:00 201211454 Sarfraz Raza                            15
10:20 201301178 Mathieu Dehouck                         15
10:40 201301239 Benjamin Chalaux                        18
11:00  20081273 Jakob Koed Holm                         19
11:20  20081332 Emil Nauerby                            19
11:40  20112625 Mads Pørksen Buch                       19
12:30  20094082 Christoffer Quist Adamsen                6
12:50  20094311 Jesper Lindstrøm Nielsen                 6
13:10  20094924 Jens Olaf Svanholm Fogh                  6
13:30  20105217 Mathias Bak Bertelsen                   10
13:50  20105774 Andreas Troelsen                        10