There is a repetitorium on Wednesday 23.07 from 12:00-14:00 (Monday 28.07 2pm) instead of the tutorial. The repetitorium will take place in SR307.
The repetitorium is moved to Monday the 28th July at 2pm in room SR307, due to sickness.
Tue 10:15 - 12:00 in SR 11
Wed 12:15 - 14:00 in SR 307
Office hours: By appointment
Default is Wednesday 14:15 - 16:00 in SR 307, but upon mutual agreement we can try to find another slot.
Office hours: By appointment
We will issue problem sheets weekly on Tue; you have one week to complete the assignments and can hand them in before the next Tuesday 08:00 (a.m.) electronically. The solutions will then be discussed in the following tutorial. There are no (bonus) points for the exercises.
The lecture is held in English. By mutual agreement, the language of instruction can be changed to German, too.
You can solve the assignments in German or in English.
In the first part we will consider classic and new algorithms for memory hierarchies
In the second part we will deal with streaming algorithms and their connection to other models of computation (external-memory, parallelism, power-aware computing). Lower bounds. Initial references:
Lecture notes by Amit Chakrabarti at Dartmouth College from 2020. We will follow them rather closely for the first weeks of the second part.
M. Garofalakis, J. Gehrke, and R. Rastogi (eds) “Data Stream Management: Processing High-Speed Data Streams”, Springer, 2016.
The exam type is to be determined.
Date | Notes | Topics |
---|---|---|
22.04.25 | Notes | Models of computation |
23.04.25 | Notes | The I/O Model, Cache Oblivious |
13.05.25 | Notes | |
13.05.25 | Board | |
14.05.25 | Notes | Buffer Tree -> Priority Queues |
20.05.25 | Notes | Time Forward Processing, Bounded Degree Coloring |
21.05.25 | Notes | List Ranking |
27.05.25 | Notes | List Ranking, Euler Tours |
28.05.25 | Notes | Euler Tours, Minimum Spanning Tree |
03.06.25 | Notes | Minimum Spanning Tree |
03.06.25 | Board | |
04.06.25 | Notes | Minimum Spanning Tree, BFS |
10.06.25 | Notes | BFS |
11.06.25 | Notes | BFS |
17.06.25 | Notes | BFS |
17.06.25 | Notes | BFS Directed Graphs |
18.06.25 | Notes | BFS Directed Graphs |
24.06.25 | Notes | Tournament Trees |
01.07.25 | Notes | Streaming Algorithms |
02.07.25 | Board | 2-universelle Hashfamilien, Tidemark Algorithmus |
02.07.25 | Notes | Misra Gries (Freq. Schätzung) |
08.07.25 | Notes | Tidemark Algorithmus |
09.07.25 | Notes | Approx. Zählen |
15.07.25 | Notes | Median of Means, Chebyschev’s inequality, Spanner |
16.07.25 | Notes | t-Spanner |
tba
Download | Issued | Due | Comments |
---|---|---|---|
Sheet 1 | 29.04.2025 | 06.05.2025, 08:00 | |
Sheet 2 | 06.05.2025 | 13.05.2025, 08:00 | |
Sheet 3 | 13.05.2025 | 20.05.2025, 08:00 | |
Sheet 4 | 20.05.2025 | 27.05.2025, 08:00 | |
Sheet 5 | 27.05.2025 | 03.06.2025, 08:00 | |
Sheet 6 | 03.06.2025 | 10.06.2025, 08.00 | |
Sheet 7 | 10.06.2025 | 17.06.2025, 08.00 | |
Sheet 8 | 17.06.2025 | 24.06.2025, 08.00 | |
Sheet 9 | 24.06.2025 | 01.07.2025, 08.00 | |
Sheet 10 | 01.07.2025 | 08.07.2025, 08.00 | |
Sheet 11 | 08.07.2025 | 15.07.2025, 08.00 |