Advanced Algorithms - Data Structures (Fall 2005)

Messages

Aims

The aim of any advanced algorithmics course is to provide the student with thorough knowledge of new research within a selected subfield of algorithmics, in order that the student afterwards can write a Master's Thesis or do PhD work within the area of algorithmics.

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

Relation to other courses: slide (pdf).

Lecturers

Lectures

Wednesday 14-16 and Friday 9-10 in Shannon 159

Course plan

Week Date Content Literature
35 31/8 Union-Find - Overview [GI91, Sect. 1]
2/9 Union-Find [K91, Lect. 10]
36 7/9 Union-Find - analysis [K91, Lect. 11]
9/9 Selection in binary heaps [F93]
37 14/9 Linear time selection, Binomial queues [CLRS01, Section 9.3],[V78],[DGST88]
16/9 Fibonacci heaps [DGST88, Sections 1-2]
38 21/9 Fibonacci heaps [DGST88, Sections 2 + 4-5]
23/9 Worst-case efficient heaps [DGST88, Sections 1-3],[B96, Section 1]
39 28/9 Maintaining order in a list [DS87, Sections 1-2]
30/9 Finger search trees [B05, Sections 11.1-3, 11.5.1, 11.5.4]
40 5/10 Cancelled  
7/10 Cancelled  
41 12/10 Top-down analysis of union-find [SS05]
14/10 Interval stabbing-max data structures (guest lecture by Ke Yi) [AAY05]
Fall break
44 2/11 Nearest common ancestors [AGKR02, Section 1-2]
4/11 Nearest common ancestors, labeling schemes [AGKR02, Section 3-4]
45 9/11 Planar separators [LT79, Sections 1-3]
11/11 Reachability queries in planar digraphs [T04, Sections 1-2.1]
46 16/11 Reachability queries in planar digraphs [T04, Sections 2.2-2.7]
18/11 Interpolation search [MT93]
47 23/11 Functional queues and deques [O95]
25/11 Functional catenable lists [KT99, Sections 1-5 + 7]
48 30/11 Implicit dictionaries [FG03]
2/12 Implicit sorting with O(n) moves [FG05]
49 7/12 RAM data structures: van Emde Boas trees [BKZ77],[A95]
9/12 RAM data structures: RAM search tree [A95]
50 14/12 RAM data structures: RAM priority queue [T96],[AH92]
16/12 Summary and ``rundstykker''  

Literature

  1. [K91] Dexter Kozen, The Design and Analysis of Algorithms, Springer-Verlag, New-York, 1991.
  2. [GI91] Zvi Galil, Giuseppe F. Italiano, Data structures and algorithms for disjoint set union problems, ACM Computing Surveys, Volume 23(3), 319-344, 1991.
  3. [F93] Greg N. Frederickson, An optimal algorithm for selection in a min-heap, Information and Computation, Volume 104(2), 197-214 , 1993.
  4. [CLRS01] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, 2nd Edition, MIT Press, 2001.
  5. [V78] Jean Vuillemin, A data structure for manipulating priority queues, Communications of the ACM archive, Volume 21(4), 309-315, 1978.
  6. [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.
  7. [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.
  8. [B96] Gerth S. Brodal, Worst-case efficient priority queues, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, 52-58, 1996.
  9. [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 .
  10. [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.
  11. [SS05] Raimund Seidel, Micha Sharir, Top-Down Analysis of Path Compression, SIAM Journal on Computing Volume 34, Number 3, 515-525, 2005
  12. [AAY05] Pankaj Agarwal, Lars Arge, Ke Yi, An Optimal Dynamic Interval Stabbing-Max Data Structure?, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete Algorithms, 803-812, 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. [LT79] Richard J. Lipton, Robert Endre Tarjan, A Separator Theorem for Planar Graphs, SIAM Journal on Applied Mathematics, Vol. 36, No. 2. (Apr., 1979), pp. 177-189.
  15. [T04] Mikkel Thorup, Compact oracles for reachability and approximate distances in planar digraphs, Journal of the ACM, 51(6), 993-1024, November 2004.
  16. [MT93] Kurt Mehlhorn and Athanasios Tsakalidis. Dynamic interpolation search, Journal of the ACM, 40(3), 621-634, July 1993.
  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. [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.
  20. [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.
  21. [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
  22. [A95] Arne Andersson, Sublogarithmic Searching Without Multiplications, In Proc. 36th IEEE Symposium on Foundations of Computer Science (FOCS), 655-663.
  23. [T96] Mikkel Thorup, On RAM priority queues, In Proc. 11th Annual ACM-SIAM symposium on Discrete algorithms (SODA), 59-67, 1996.
  24. [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.

Projects

Quarter

1st and 2nd (Fall 2005).

Credits

10 ETCS points.

Prerequisites

Course language

Danish or English.

Evaluation

Projects and oral exam, 13-scale

Exam

The oral exams will take place Friday January 27, 2006 in Turing-024.

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 13-scale.

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