Section: Topics and Lectures | WS23: Advanced Algorithms

Section outline

Overview of all lectures with slides (for some topics with videos from the course in 2020).


Date (+ long slides)	Topic (+ short slides)	Videos (old!)	Exercise	Literature
18.10.2023	Intro and Organizational	Intro
18.10.2023	Approximation Algorithms	Additive · Relative · PTAS	Link	[WS], [JM]
25.10.2023	Exact Algorithms for NP-hard Problems	Exact Algorithms · TSP · MIS	Link	[FK Ch 1], [Man '17]
25.10.2023	Computational Geometry	Sweep Line		[Klei '05]
08.11.2023	Parameterized Algorithms	Intro & Trees · Grids · Pathwidth	Link	[CFK+ '15]
15.11.2023	Push–Relabel Algorithm for Maximum Flow	Max-Flow · Push–Relabel · Analysis	Link	[CLRS Ch 24], [GT '88]
29.11.2023	QP-Relaxation for Approximating Max-Cut	Introduction & QP-Relaxation · Randomization & Analysis	Link	[Vaz Ch 26]
13.12.2023	Randomized Algorithms	Probability · Algorithms	Link	[Sto '17]
20.12.2023	Online Algorithms	Ski-Rental · Definition · Paging (Det.) · Paging (Rand.)	Link	[Sto '17]
10.01.2024	Succinct Data Structures	Intro · Rank & Select · Trees	Link	[Jac '89]
17.01.2024	Splay Trees	Optimality · Models · Splay Trees · Potential · Access Lemma · Properties	Link	[ST '85]
24.01.2024	Data Structures for String Matching	String Matching · Suffix Trees · Suffix Arrays	Link	[KS '03] [Far '97] [Gus '99]
31.01.2024	Randomized and Probabilistic Data Structures	no videos :(	Link	[Sto '17], [Pug '90], [SA '96], [Blo '70], [MU '05], [BGK+ '08]
07.02.2024	Algorithms in Practice	[Playlist] Theory and Practice · "Computers are fast" · Implementing the Knapsack DP · Sorting	no exercises