Department of Computer Science Aarhus University Department of Comptuer Science Faculty of Science

Advanced Algorithms - Data Structures (Fall 2011)

Messages

Aims

Normal Honours
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. The participants will after the course have detailed knowledge of advanced data structures and general design techniques for the construction of data structures and experience with applying the techniques to design new data structures for algorithmic problems. The working method of the course will train the participants to read and understand research papers.

Goals

Normal Honours
The participants must at the end of the course be able to:
  • implement and evaluate advanced data structures,
  • describe and analyze advanced data structures,
  • compare advanced data structures in different computational models.
The participants must at the end of the course be able to:
  • design data structures using algorithmic design techniques
  • select and combine techniques to design data structures
  • survey selected areas within data structures
  • compare and relate models for data structure design and analysis

Contents

Normal Honours
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.
During the course there will be experimental projects were data structures covered in the lectures should be implemented and experimentally evaluated and compared. During the course there will be theoretical projects were data structures should be designed using the techniques covered in the lectures.

Lecturers

Gerth Stølting Brodal.

Lectures

3 hours per week. Wednesdays 9.15-12.00. DI-Nygaard-184, Finlandsgade 21.

Course plan

Week Date Content Literature Slides
34 24/8 Linear time selection [CLRS01, Section 9.3] pptx|pdf
35 31/9 Binomial queues, Fibonacci heaps [V78], [FT87, Sections 1-2,4],[DGST88, Section 1] pptx|pdf
36 7/9 Finger search trees, skip lists, treaps [B05, Sections 11.1-11.4] pptx|pdf
37 14/9 Maintaining order in a list [DS87] pptx|pdf
38 21/9 Nearest common ancestors, Discrete range searching, Cartesian trees [AGKR02, Sections 1-2] pptx|pdf
39 28/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
40 5/10 Implicit dictionaries and sorting [FG03, Section 1],[FG05, Section 1] pptx|pdf
41-43 Fall break
44 2/11 Partial and Full Persistence [ST86a], [DSST89, Sections 1-3] pptx|pdf
45 9/11 Functional Data Structures: Queues, Dequeues, Catenable Lists [O95],[KT99, Sections 1-2, 7] pptx|pdf
46 16/11 Retroactive Data Structures [DIL04] pptx|pdf
47 23/11 Unified Property for Dictionaries [BCDI07] pptx|pdf
48 30/11 Maxiphobic Heaps, Self Adjusting Data Structures: Heaps and Search Trees [O05, Section 3],[ST86b, Sections 1-3],[ST85, Sections 1-3] pptx|pdf
49 7/12 Selection: X+Y and Binary Heaps [FJ82],[F93, Section 1] pptx|pdf
50 14/12 Coffee and breakfast rolls    

Literature

  1. [CLRS01] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, 2nd Edition, MIT Press, 2001.
  2. [V78] Jean Vuillemin, A data structure for manipulating priority queues, Communications of the ACM, 21(4): 309-315, 1978.
  3. [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.
  4. [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.
  5. [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.
  6. [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 .
  7. [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.
  8. [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
  9. [A95] Arne Andersson, Sublogarithmic Searching Without Multiplications, In Proc. 36th IEEE Symposium on Foundations of Computer Science (FOCS), 655-663.
  10. [T96] Mikkel Thorup, On RAM priority queues, In Proc. 11th Annual ACM-SIAM symposium on Discrete algorithms (SODA), 59-67, 1996.
  11. [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.
  12. [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.
  13. [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.
  14. [ST86a] Neil Sarnak, Robert E. Tarjan, Planar point location using persistent search trees, Communications of the ACM, 29(7): 669-679, 1986.
  15. [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.
  16. [O95] Chris Okasaki, Simple and efficient purely functional queues and deques, Journal of Functional Programming 5(4): 583-592, 1995
  17. [KT99] Haim Kaplan and Robert E. Tarjan, Purely functional, real-time deques with catenation, Journal of the ACM, 46(5): 577-603, September 1999.
  18. [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.
  19. [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.
  20. [O05] Chris Okasaki, Alternatives to Two Classic Data Structures, Symposium on Computer Science Education (SIGCSE), 162-165, 2005.
  21. [ST86b] Daniel Dominic Sleator and Robert Endre Tarjan, Self-Adjusting Heaps, SIAM Journal of Computing, 15(1): 52-69, 1986.
  22. [ST85] Daniel Dominic Sleator and Robert Endre Tarjan, Self-Adjusting Binary Search Trees, Journal of the ACM, 32(3): 652-686, 1985.
  23. [F93] Greg N. Frederickson, An Optimal Algorithm for Selection in a Min-Heap, Inf. Comput. 104(2): 197-214, 1993.
  24. [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.

Projects

Normal Honours
Project 1 (due Tuesday September 27, 23.59, 2011)
Project 2 (due Tuesday November 8, 23.59, 2011)
Project 3 (due Friday December 16, 23.59, 2011) 		Project 1 (due Tuesday September 27, 23.59, 2011)
Project 2 (due November 8, 23.59, 2011)
Project 3 (due Friday December 16, 23.59, 2011)

Quarter

1st and 2nd (Fall 2011).

Credits

10 ETCS points.

Prerequisites

Algoritmer og Datastrukturer 1 + Algoritmer og Datastrukturer 2

Course language

Danish or English

Evaluation

Normal Honours
3 group projects (2-3 persons per group) and individual oral exam, 7-scale, internal examiner 3 individual projects and 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 3-4, 2012. For details see the examination list.