Advanced Data Structures

Organizational matters Link to heading

Lectures:

• In English
• Monday 14:00 - 15:30
• Building 50.34, room 236

Grade:

• 80% oral exam, 20 minutes
• 20% programming project
  • Details coming a few weeks
  • Requires registration

Materials Link to heading

This year’s materials:

• The course page: ae.iti.kit.edu/english/5028.php
• Ragnar’s blog: curiouscoding.nl/teaching
  • Lecture notes and/or slides available shortly before the lecture

Previously taught by Florian Kurpicz:

• SS 2024 course materials & slides (in English)
• Recorded lectures on YouTube (@kurpicz, in German):
  • SS 2022
  • SS 2023

Related MIT Advanced Data Structures course by Erik Demaine:

• Course overview
• 2012 recordings

Tentative course overview Link to heading

Ragnar (5 weeks):

• Today: Models of computation
• Rank & Select
• Applications of Rank & Select:
  • Elias Fano
  • Succinct trees
  • Succinct planar graphs
• Range minimum queries
  • Topic of practicum
• Segment Trees & Fenwick Trees

Stefan Walzer & Stefan Hermann (6 [TODO] weeks):

• Sorted sequences / predecessor structures
  • Van Emde Boas tree
  • x-Fast trie
  • y-Fast trie
• External memory model
  • Cache-oblivious B-trees
• Learned indexes
• Streaming and Sketching algorithms
• Splay trees
• Modern hash tables

Social time! Link to heading