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

• computation models and memory models
• string indexing (suffix trees, suffix arrays)
• search trees
• static tree processing (Lowest Common Ancestor queries, Level Ancestry queries)
• range queries on arrays (queries for minimal element in a given range)
• integers-only data structures: how to sort integers in linear time, faster predecessor structures (van Emde Boas trees)
• hashing
• dynamic connectivity
• succintness
• geometric data structures

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

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.