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

Lectures

Weekly on Mondays, 10-12, in CHN E42

Lecturer

Przemysław Uznański, przemyslaw.uznanski [at] inf.ethz.ch

Problem Classes

Weekly on Tuesdays 15-17 in LFW E13

Topics

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).

Exam/Grades

There will be a written exam during summer. It will be an open-book examination.

Your final grade will be based on the exam + bonus points from exercise classes.

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.

Schedule and Weekly Exercises

Date Topic Exercise Sheets
Feb 19 Static tree preprocessing: Lowest Common Ancestry and Level Ancestry queries
Arrays: Range Minimum Queries
Indirection, Range Trees

Exercise Sheet 1 (Feb 20)

Feb 26
Hashing: Independence
Dictionaries: Chaining, FKS scheme

Exercise Sheet 2 (Feb 27)

Mar 05 Suffix Trees, Suffix Arrays

Exercise Sheet 3 (Mar 06)

Mar 12 Succint bit-vectors: Rank, Select

Exercise Sheet 4 (Mar 13)

Mar 19 Compressed data structures: RRR, Wavelet trees

Exercise Sheet 5 (Mar 20)

Mar 26 Persistency

Exercise Sheet 6 (Mar 27)

Apr 09 Geometry

Exercise Sheet 7 (Apr 10)

Apr 16 Dynamic Graphs

Exercise Sheet 8 (Apr 17)

Apr 23 Dynamic Graphs 2

NONE

Apr 30 Integers: van Emde Boas trees

NONE

May 07 Integers: Fusion Trees

Exercise Sheet 9 (May 08)

May 14 Integers: Cache Oblivious

Exercise Sheet 10 (May 22)

Frequently Asked Questions

Will there be lecture notes provided?

Short answer: no.

Longer: if any student decides to share their own notes, yes. There are however some notes from previous year (but the material covered might not be identical). 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?

No. However attendance is advised.

Bonus points?

You can score bonus points, that will count towards the final grade. Bonus points are awarded from presenting correct solutions to the problems from exercise sheets, at the blackboard, during the exercise classes. You will also get 1 point just from attending the class.

Graded homeworks?

There will be none.

Exam?

Exam will consist of a series of challenging problems.