Department of Computer Science | Institute of Theoretical Computer Science

CADMO - Center for Algorithms, Discrete Mathematics and Optimization

Advanced Data Structures

Short Course Description

Data structures play a central role in modern computer science and are essential building blocks in obtaining efficient algorithms. The course covers major results and research directions in data structures, that (mostly) have not yet made it into standard computer science curriculum.

Weekly Schedule


Weekly on Mondays, 10-12, in CAB G52 by

Problem Classes



Problem Classes

Weekly exercise assignments will be published on this web page (shortly after each lecture). The solutions will be discussed during the corresponding exercise class (usually 1 week after lecture).


There will be a written exam on 10th of August (Thursday), in room CAB G61. It will take from 9am to 11am. It will be an open-book examination.

Your final grade will be based solely on the exam.

Following the new D-INFK guidelines for doctoral studies, PhD students get credit points according to the same rules that apply for Bachelor or Master students. That is, with a final grade of at least 4 doctoral students will receive 5KE, and 0KE otherwise.

Frequently Asked Questions

Will there be lecture notes provided?

For some lectures we will provide handwritten notes. You are strongly encouraged to take your own notes. You might find large parts of material covered here: MIT 6.851: Advanced Data Structures.

Are exercise classes mandatory?

Exercises cover an extension of material and application of, so attendance is strongly advised.

Schedule and Weekly Exercises

Date Topic Lecture Notes Exercise Sheets
Feb 20 Hashing: universality, k-wise independence, tabulation hashing
Dictionaries: chaining, perfect hashing, linear probing, cuckoo hashing

L01 (Daniel T.)

Exercise Sheet 1 (Feb 21)

Exercise Sheet 2 (Feb 28/Mar 2)

Feb 27 Static tree preprocessing: Lowest Common Ancestry and Level Ancestry queries
Arrays: Range Minimum Queries
Indirection, Range Trees

L02 (Daniel G.)

L02 (Daniel T.)

Exercise Sheet 3 (Mar 7/Mar 9)

Mar 6 String indexing
Suffix trees, Suffix arrays

L03 (Daniel T.)

Exercise Sheet 4 (Mar 14/Mar 16)

Mar 13 Temporal data structures
Partial persistency, Full persistency, Functional persistency

L04 (Daniel G.)

L04 (Daniel T.)

Exercise Sheet 5 (Mar 21/Mar 23)

Mar 20 List order maintainance
Temporal data structures
Partial retroactivity, Full retroactivity

L05 (Daniel G.)

L05 (Daniel T.)

Exercise Sheet 6 (Mar 28/Mar 30)

Mar 27 Partial retroactivity (priority queue)
Geometry: range trees, layered range trees
Fractional cascading

L06 (Daniel G.)

L06 (Daniel T.)

Exercise Sheet 7 (Apr 04/Apr 06)

Apr 03 Dynamic graphs
Euler tour trees

L07 (Daniel G.)

L07 (Daniel T.)

Exercise Sheet 8 (Apr 11/Apr 13)

Apr 10 Lower bounds: dynamic partial sums, dynamic connectivity

L08 (Daniel G.)

L08 (Daniel T.)

Exercise Sheet 9 (Apr 25/Apr 27)

Apr 24 Integer predecessor: van Emde Boas, x-fast trees, y-fast trees

L09 (Daniel G.)

L09 (Daniel T.)


May 02 Integer predecessor: fusion trees

L10 (Daniel T.)

Exercise Sheet 11 (May 09/May 11)

Exercise Sheet 12 (May 16/May 18)

May 15 Succintness: rank, select


Exercise Sheet 13 (May 23)

May 22 Concurrency: locks, lock-free

L12 (Daniel G.)

Exercise Sheet 14 (May 30/Jun 02)

May 29 Concurrency: lists, priority queues

L13 (Daniel G.)