Advanced Algorithms - Data Structures (Fall 2007)

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 (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.

Lecturers

Gerth Stølting Brodal.

Lectures

1st quarter (August 30-October 11): Thursday 14-17 in IT-huset Lille Auditorium (except August 30 and October 11 which take place in IT-huset 112)

2nd quarter (November 1-December 19): Wednesday 9-12 in Shannon 157.

Course plan

Week Date Content Literature
35 30/8 Linear time selection, Binomial queues
(lectures 14.15-16.00)		 [CLRS01, Section 9.3],[V78]
36 6/9 Fibonacci heaps [FT87, Sections 1-2,4],[DGST88, Section 1]
37 13/9 Finger search trees, skip lists, treaps [B05, Sections 11.1-11.4]
38 20/9 Maintaining order in a list [DS87]
39 27/9 Nearest common ancestors [AGKR02, Sections 1-2]
40 4/10 Succinct data structures
(Lectures by S. Srinivasa Rao)		 [MR05]
41 11/10 Implicit dictionaries and sorting
(Lectures in IT-huset 112)		 [FG03],[FG05]
Fall break
45 7/11 Maxiphobic Heaps, Self Adjusting Data Structures: Heaps and Search Trees [O05, Section 3],[ST86a],[ST85, Sections 1-3]
46 14/11 Selection: X+Y and Binary Heaps [FJ82],[F93]
47 21/11 Functional Data Structures: Queues, Dequeues, Catanable Lists [O95],[KT99, Sections 1 + 7]
48 28/11 RAM data structures: van Emde Boas Trees, Search Trees, Priority Queues [BKZ77],[A95, Sections 1-4.2],[T96,Sections 1-2],[AH92, Sections 2-3]
49 5/12 Partial and Full Persistence, Fractional Cascading [ST86b], [DSST89, Sections 1-3], [CG86]
50 12/12 Unified Property for Dictionaries, Retroactive Data Structures [BCDI07],[DIL04]
51 19/12 Summary/exam discussion and ``rundstykker''  

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. [T85] Robert E. Tarjan. Amortized computational complexity. SIAM Journal of Algebraic and Discrete Methods, 6:306-318, 1985.
  6. [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.
  7. [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 .
  8. [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.
  9. [MR05] Succinct representation of data structures. J. Ian Munro and S. Srinivasa Rao. Chapter 37 in Handbook of Data Structures and Applications, Chapman & Hall/CRC Computer and Information Science Series, 2005.
  10. [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.
  11. [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.
  12. [O05] Chris Okasaki, Alternatives to Two Classic Data Structures, Symposium on Computer Science Education (SIGCSE), February 2005, pages 162-165.
  13. [ST86a] Daniel Dominic Sleator and Robert Endre Tarjan, Self-Adjusting Heaps, SIAM Journal of Computing, 15(1), 52-69.
  14. [ST85] Daniel Dominic Sleator and Robert Endre Tarjan, Self-Adjusting Binary Search Trees, Journal of the ACM, 32(3), 652-686.
  15. [F93] Greg N. Frederickson, An Optimal Algorithm for Selection in a Min-Heap, Inf. Comput. 104(2): 197-214 (1993)
  16. [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)
  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. [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
  20. [A95] Arne Andersson, Sublogarithmic Searching Without Multiplications, In Proc. 36th IEEE Symposium on Foundations of Computer Science (FOCS), 655-663.
  21. [T96] Mikkel Thorup, On RAM priority queues, In Proc. 11th Annual ACM-SIAM symposium on Discrete algorithms (SODA), 59-67, 1996.
  22. [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.
  23. [ST86b] Neil Sarnak, Robert E. Tarjan, Planar point location using persistent search trees, Communications of the ACM, 29(7), 1986, pages 669-679.
  24. [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.
  25. [CG86] Bernard Chazelle, Leonidas J. Guibas, Fractional Cascading: I. A Data Structuring Technique, Algorithmica, 1(2), 1986, pages 133-162.
  26. [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.
  27. [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.

Projects

Quarter

1st and 2nd (Fall 2007).

Credits

10 ETCS points.

Prerequisites

Algoritmer og Datastrukturer 1 + Algoritmer og Datastrukturer 2

Types of teaching

Lectures (3 h/week)

Compulsory programme

3 projects

Teaching materials/Text-books

Research papers

Course language

Danish or English.

Evaluation

Group project and oral exam
7-scale, internal examiner

Exam

The oral exams are planned to take place Thursday-Friday January 3-4, 2008 in Turing-014.

The exam takes 20 minutes, including evaluation. The exam will be a discussion of the reports on the three 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. A grad will be given on the 7-scale.

This page is maintained by Gerth Stølting Brodal <gerth@cs.au.dk>