Nützliche Links

|

Topics and Lectures

Section outline

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


Date (+ short slides)	Topic (+ long slides)	Videos (old!)	Literature
19.10.2022	Intro and Organizational	Intro
19.10.2022	Push–Relabel Algorithm for Maximum Flow	Max-Flow · Push–Relabel · Analysis	[CLRS Ch 26], [GT '88]
26.10.2022	Exact Algorithms for NP-hard Problems	Exact Algorithms · TSP · MIS	[FK Ch 1], [Man '17]
02.11.2022	Approximation Algorithms	Additive · Relative · PTAS	[WS], [JM]
09.11.2022	QP-Relaxation for Approximating Max-Cut	Introduction & QP-Relaxation · Randomization & Analysis	[Vaz Ch 26]
16.11.2022	Parameterized Algorithms	Intro & Trees · Grids · Pathwidth	[CFK+ '15]
23.11.2022 [update 29.11.]	SPR-Distance of Phylogenetic Trees [update 29.11.]	SPR · MAF · FPT · Approx	[BS '05], [RSW '06]
30.11.2022	Randomized Algorithms	Probability · Algorithms	[Sto '17]
14.12.2022	Online Algorithms	Ski-Rental · Definition · Paging (Det.) · Paging (Rand.)	[Sto '17]
21.12.2022	Succinct Data Structures	Intro · Rank & Select · Trees	[Jac '89]
11.01.2023	Splay Trees	Optimality · Models · Splay Trees · Potential · Access Lemma · Properties	[ST '85]
18.01.2023	Data Structures for String Matching	String Matching · Suffix Trees · Suffix Arrays	(see last slide)
25.01.2023	Randomized and Probabilistic Data Structures	no videos :(	[Sto '17], [Pugh '90], [Bloom '70], [Mitzenmacher, Upfal '05], [Bose et al. '08]
25.01.2023	Computational Geometry	Sweep Line	[Klei '05]
01.02.2023	Algorithms in Practice	[Playlist] Theory and Practice · "Computers are fast" · Implementing the Knapsack DP · Sorting	[Dij '59] [Kar '72] [Mus '99]

Impressum | Datenschutzerklärung - WueCampus | Erklärung zur Barrierefreiheit | Bildnachweise

Navigationsleiste - WueStudy: University icons created by justicon - Flaticon
Navigationsleiste - Rechenzentrum: Data center icons created by Eucalyp - Flaticon
Navigationsleiste - Website Support: Consultant icons created by Vitaly Gorbachev - Flaticon
Navigationsleiste - Häufige Fragen: Files and folders icons created by Freepik - Flaticon
Navigationsleiste - Lehre Digital: Training icons created by vectorspoint - Flaticon
Navigationsleiste - Forschung Digital: Research icons created by Eucalyp - Flaticon
Navigationsleiste - Lecture: Video icons created by Freepik - Flaticon
Werbefeld 2 - WueLogin: Login icons created by Freepik - Flaticon
Werbefeld 3 - Upgrade WueCampus 4.4: Update icons created by Freepik - Flaticon