Ämne: Topics and Lectures | SS26: Advanced Algorithms

Avsnittsöversikt

Overview of all lectures with slides (for some topics with videos from the course held in 2020).
Date (+ short slides)	Topic (+ long slides)	Videos (old!)	Literature
14.04.2026	Intro and Organizational	Intro
14.04.2026	Approximation Algorithms	Additive · Relative · PTAS	[WS], [Jansen & Margraf '08]
21.04.2026	Exact Algorithms for NP-hard Problems	Exact Algorithms · TSP · MIS	[FK Ch 1], [Mann '17]
21.04.2026	Computational Geometry	Sweep Line	[Klein '05]
28.04.2026	Parameterized Algorithms	Intro & Trees · Grids · Pathwidth	[CFK+ '15]
04.05.2026	Push–Relabel Algorithm for Maximum Flow	Max-Flow · Push–Relabel · Analysis	[CLRS Ch 26], [Goldberg & Tarjan '88]
12.05.2026	QP-Relaxation for Approximating Max-Cut	Introduction & QP-Relaxation · Randomization & Analysis	[Vazirani Ch 26]
19.05.2026	Randomized Algorithms	Probability · Algorithms	[Storandt '17]
02.06.2026	Online Algorithms	Ski-Rental · Definition · Paging (Det.) · Paging (Rand.)	[Storandt '17]
09.06.2026	Succinct Data Structures	Intro · Rank & Select · Trees	[Jacobson '89]
16.06.2026	Splay Trees	Optimality · Models · Splay Trees · Potential · Access Lemma · Properties	[ST '85]
30.06.2026	Data Structures for String Matching	String Matching · Suffix Trees · Suffix Arrays	(see last slide)
07.07.2026	Randomized and Probabilistic Data Structures	no videos :(	[Storandt '17], [Pugh '90], [Bloom '70], [Mitzenmacher, Upfal '05], [Bose et al. '08]
14.07.2026	Algorithms in Practice	[Playlist] Theory and Practice · "Computers are fast" · Implementing the Knapsack DP · Sorting	[Dijkstra '59] [Karp '72] [Musser '99]