
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.
1st quarter (August 30October 11): Thursday 1417 in IThuset Lille Auditorium (except August 30 and October 11 which take place in IThuset 112)
2nd quarter (November 1December 19): Wednesday 912 in Shannon 157.
Week  Date  Content  Literature 

35  30/8  Linear time selection, Binomial queues (lectures 14.1516.00) 
[CLRS01, Section 9.3],[V78] 
36  6/9  Fibonacci heaps  [FT87, Sections 12,4],[DGST88, Section 1] 
37  13/9  Finger search trees, skip lists, treaps  [B05, Sections 11.111.4] 
38  20/9  Maintaining order in a list  [DS87] 
39  27/9  Nearest common ancestors  [AGKR02, Sections 12] 
40  4/10  Succinct data structures (Lectures by S. Srinivasa Rao) 
[MR05] 
41  11/10  Implicit dictionaries and sorting (Lectures in IThuset 112) 
[FG03],[FG05] 
Fall break  
45  7/11  Maxiphobic Heaps, Self Adjusting Data Structures: Heaps and Search Trees  [O05, Section 3],[ST86a],[ST85, Sections 13] 
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 14.2],[T96,Sections 12],[AH92, Sections 23] 
49  5/12  Partial and Full Persistence, Fractional Cascading  [ST86b], [DSST89, Sections 13], [CG86] 
50  12/12  Unified Property for Dictionaries, Retroactive Data Structures  [BCDI07],[DIL04] 
51  19/12  Summary/exam discussion and ``rundstykker'' 
1st and 2nd (Fall 2007).
10 ETCS points.
Algoritmer og Datastrukturer 1 + Algoritmer og Datastrukturer 2
Group project and oral exam
7scale, internal examiner
The oral exams are planned to take place ThursdayFriday January 34, 2008 in Turing014.
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 7scale.