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.
The participants must at the end of the course be able to:
Selected topics in data structures. Possible topics: Fractional cascading. Persistence: Partial persistence, Full persistence, Purely functional data structures (catenable 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.
3 hours per week. Wednesdays 11.15-14.00, Nygaard 184.
|35||26/8||Binomial queues, Fibonacci heaps||[V78], [FT87, Sections 1-2,4],[DGST88, Section 1]||pptx|pdf|
|36||2/9||Finger search trees, skip lists, treaps||[B05, Sections 11.1-11.4],[LO88]||pptx|pdf|
|37||9/9||RAM data structures: van Emde Boas Trees, Search Trees, Priority Queues||[BKZ77, Sections 1-5],[A95, Sections 1-4.2],[T96, Sections 1-2],[AH92, Sections 2-3]||pptx|pdf|
|38||16/9||Implicit Dictionaries and Sorting
|[FG03, Section 1],[FG05, Section 1]||pptx|pdf
|39||24/9||Nearest Common Ancestors, Discrete Range Searching, Cartesian Trees||[AGKR02, Sections 1-2]||pptx|pdf|
|40||30/9||Invertible Bloom Filters
Lecture by Kasper Green Larsen
|41||7/10||Unified Property for Dictionaries||[BCDI07]||pptx|pdf|
|42-44||Fall break||45||4/11||Maintaining Order in a List||[DS87]||pptx|pdf|
|46||11/11||Partial and Full Persistence, Fractional Cascading||[ST86a], [DSST89, Sections 1-3], [CG86]||pptx|pdf|
|47||18/11||Functional Data Structures: Queues, Dequeues, Catenable Lists||[O95],[KT99, Sections 1-2, 7]||pptx|pdf|
|48||25/11||Orthogonal Point Location on the Word RAM
Lecture by Peyman Afshani
|49||2/12||Retroactive Data Structures||[DIL04]||pptx|pdf|
|50||9/12||Maxiphobic Heaps, Self Adjusting Data Structures: Heaps and Search Trees||[O05, Section 3],[ST86b, Sections 1-3],[ST85, Sections 1-3]||pptx|pdf|
|51||16/12||Selection: X+Y and Binary Heaps||[FJ82],[F93, Section 1]||pptx|pdf|
Many of the below references link to the official versions of the papers at the publishers websites. Some of the publications require paid subscription for achieving access. AU has paid subscriptions to these publications, which are available when you are on a AU network, e.g. using VPN.
1st and 2nd (Fall 2015).
10 ETCS points.
Algorithms and Data Structures 1+2.
Danish or English.
3 group projects (2-3 persons per group) and individual oral exam, 7-scale, internal examiner.
The exam takes 20 minutes, including evaluation. The exam will be a discussion of the reports on the 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.