Advanced Data Structures (CS 650) is a specialization module (Vertiefungsmodul) covering advanced data structures and their applications in algorithm design. The focus will be on the asymptotically most efficient solutions, and the techniques for analyzing them, with the aim of equipping students for research in this area.

YouTube  ⋅  ILIAS  ⋅  Campuswire  ⋅  Units

Topics

  • amortized analsis, potential functions
  • randomisierte Datenstrukturen
  • hashing und filters
  • space-efficient data structures
  • integer data structures
  • external memory

Lectures

Lectures are live-streamed and recorded on a best-effort basis (YouTube Channel).
Live participation in the synchronous lectures is expected.

Lecture slots and rooms are found on Marvin.
Times on Marvin are c.t. (start is 15min past the full hour).

Units

The module will consist of the following units; each will have a unit subpage (linked in the table) with slides, lecture notes, and video recordings for that unit.

Week w/c (Mon) Lecture Topics Exercise Sheet
1 2025-04-13 Unit 0: Administrativa  
2 2025-04-20 Unit 1: Randomized Trees  
3 2025-04-27 Unit 2: Adaptive Trees  
4 2025-05-04 Unit 3: Efficient Priority Queues  
5 2025-05-11 Unit 4: Persistence  
6 2025-05-18 Unit 5: Integer Data Structures  
7 2025-05-25 Unit 6: Bitvectors  
    Whit Monday $\to$ no classes on 25 May  
8 2025-06-01 Unit 6: Bitvectors  
9 2025-06-08 Unit 7: Succinct Data Structures  
10 2025-06-15 Unit 8: Beyond Succinct  
11 2025-06-22 Unit 9: External Memory  
12 2025-06-29 Unit 10: Cache-oblivious  
13 2025-07-06 Unit 11: Modern hashing  
14 2025-07-13 Recap, Exam Q&A  

Tutorials (Übungen)

There will be exercises, required for admission to the exam. Details will be given in class.

Online Tools

We will use several tools and services to augment the lectures.

Campuswire

Campuswire is our main online communication channel.
Any questions relating to the module should be posted on Campuswire on the question & answer forum, the “class feed”.
You can post anonymously if you prefer, and you are strongly encouraged to answer each other’s questions, as well!

You can also use the platform for (social or topical) discussions in the chat rooms.

ILIAS

We will use the Marburg’s official learning management system ILIAS for announcements and examination-related information.

Slido

During live lectures, I will use Slido for interactive parts.

Exam & Assessment

The module mark is based on the final examination. To be admitted to the exam, you must achieve a passing grade in the tutorials.

More details will be given in class.

Other resources