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.
Gerth Stølting Brodal.
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.
|35||30/8||Linear time selection, Binomial queues
|[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)
|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''|
1st and 2nd (Fall 2007).
10 ETCS points.
Algoritmer og Datastrukturer 1 + Algoritmer og Datastrukturer 2
Group project and oral exam
7-scale, internal examiner
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.