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.
Przemysław Uznański, przemyslaw.uznanski [at] inf.ethz.ch
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 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.
|Feb 19|| Static tree preprocessing: Lowest Common Ancestry and Level Ancestry queries
Arrays: Range Minimum Queries
Indirection, Range Trees
Dictionaries: Chaining, FKS scheme
|Mar 05||Suffix Trees, Suffix Arrays|
|Mar 12||Succint bit-vectors: Rank, Select|
|Mar 19||Compressed data structures: RRR, Wavelet trees|
|Apr 16||Dynamic Graphs|
|Apr 23||Dynamic Graphs 2||
|Apr 30||Integers: van Emde Boas trees||
|May 07||Integers: Fusion Trees|
|May 14||Integers: Cache Oblivious|
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.
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.
There will be none.
Exam will consist of a series of challenging problems.