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

Advanced Algorithms - Data Structures (Fall 2009)

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 (concatenable 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. Lille Auditorium (IT Huset). First lecture Wednesday September 26.

Course plan

Week Date Content Literature
35 26/8 Linear time selection, Binomial queues [CLRS01, Section 9.3],[V78]
36 2/9 Fibonacci heaps [FT87, Sections 1-2,4],[DGST88, Section 1]
37 9/9 Finger search trees, skip lists, treaps [B05, Sections 11.1-11.4]
38 16/9 Maintaining order in a list [DS87]
35 23/9 Nearest common ancestors, Discrete range searching, Cartesian trees [AGKR02, Sections 1-2]
40 30/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]
41 7/10 Implicit dictionaries and sorting [FG03],[FG05]
Fall break
45 4/11 Partial and Full Persistence, Fractional Cascading [ST86a], [DSST89, Sections 1-3], [CG86]
46 11/11 Functional Data Structures: Queues, Dequeues, Catanable Lists [O95],[KT99, Sections 1 + 7]
47 18/11 Retroactive Data Structures [DIL04]
48 25/11 Unified Property for Dictionaries [BCDI07]
49 2/12 Maxiphobic Heaps, Self Adjusting Data Structures: Heaps and Search Trees [O05, Section 3],[ST86b, Sections 1-3],[ST85, Sections 1-3]
50 9/12 Selection: X+Y and Binary Heaps [FJ82],[F93, Section 1]
51 16/12 Lower Bound for Dynamic Partial Sums
(slides from Patrascu's PhD defense)		 [P09]

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 archive, Volume 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), Volume 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 archive Volume 31, Issue 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), 1986, pages 669-679.
  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), 1989, pages 86-124.
  16. [CG86] Bernard Chazelle, Leonidas J. Guibas, Fractional Cascading: I. A Data Structuring Technique, Algorithmica, 1(2), 1986, pages 133-162.
  17. [O95] Chris Okasaki, Simple and efficient purely functional queues and deques, Journal of Functional Programming 5(4), 583-592, 1995
  18. [KT99] Haim Kaplan and Robert E. Tarjan, Purely functional, real-time deques with catenation, Journal of the ACM, 46(5), 577-603, September 1999.
  19. [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.
  20. [DIL04] Erik D. Demaine, John Iacono, and Stefan Langerman, Retroactive Data Structures, in Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), New Orleans, Louisiana, January 11.13, 2004, pages 274.283.
  21. [O05] Chris Okasaki, Alternatives to Two Classic Data Structures, Symposium on Computer Science Education (SIGCSE), February 2005, pages 162-165.
  22. [ST86b] Daniel Dominic Sleator and Robert Endre Tarjan, Self-Adjusting Heaps, SIAM Journal of Computing, 15(1), 52-69.
  23. [ST85] Daniel Dominic Sleator and Robert Endre Tarjan, Self-Adjusting Binary Search Trees, Journal of the ACM, 32(3), 652-686.
  24. [F93] Greg N. Frederickson, An Optimal Algorithm for Selection in a Min-Heap, Inf. Comput. 104(2): 197-214 (1993)
  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. [P09] Mihai Patrascu, Lower Bounds for Dynamic Partial Sums. Lecture note.

Projects

Normal Honours
Project 1 (due Wednesday October 7, 9.15, 2009)
Project 2 (due Wednesday November 11, 9.15, 2009)
Project 3 (due Friday December 18, 2009) 		Project 1 (due Wednesday October 7, 9.15, 2009)
Project 2 (due Wednesday November 11)
Project 3 (due Wednesday December 16)
Project 4 (due Tuesday January 5)

Quarter

1st and 2nd (Fall 2009).

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 4 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 6-8, 2010.