
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.
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. Unionsplitfind data structures. Unionfind data structures. Selection in heaps. Planar separators.
Relation to other courses: slide (pdf).
Wednesday 1416 and Friday 910 in Shannon 159
Week  Date  Content  Literature 

35  31/8  UnionFind  Overview  [GI91, Sect. 1] 
2/9  UnionFind  [K91, Lect. 10]  
36  7/9  UnionFind  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 12]  
38  21/9  Fibonacci heaps  [DGST88, Sections 2 + 45] 
23/9  Worstcase efficient heaps  [DGST88, Sections 13],[B96, Section 1]  
39  28/9  Maintaining order in a list  [DS87, Sections 12] 
30/9  Finger search trees  [B05, Sections 11.13, 11.5.1, 11.5.4]  
40  5/10  Cancelled  
7/10  Cancelled  
41  12/10  Topdown analysis of unionfind  [SS05] 
14/10  Interval stabbingmax data structures (guest lecture by Ke Yi)  [AAY05]  
Fall break  
44  2/11  Nearest common ancestors  [AGKR02, Section 12] 
4/11  Nearest common ancestors, labeling schemes  [AGKR02, Section 34]  
45  9/11  Planar separators  [LT79, Sections 13] 
11/11  Reachability queries in planar digraphs  [T04, Sections 12.1]  
46  16/11  Reachability queries in planar digraphs  [T04, Sections 2.22.7] 
18/11  Interpolation search  [MT93]  
47  23/11  Functional queues and deques  [O95] 
25/11  Functional catenable lists  [KT99, Sections 15 + 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'' 
1st and 2nd (Fall 2005).
10 ETCS points.
Projects and oral exam, 13scale
The oral exams will take place Friday January 27, 2006 in Turing024.
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 13scale.