Uni-Logo
Algorithms and Complexity
 


Algorithm Theory
Winter Term 2024 / 2025
Fabian Kuhn

 


Live Recordings and Annotated Slides


Date Topic Recordings Slides

Week 1 (15.10.): Introduction / Organization of the Lecture
Chapter 1: Divide and Conquer
Introduction, Time Analysis, & Closest Pair of Points

Week 2 (22.10.): Multiplication of Polynomials I

Week 3 (29.10.): Multiplication of Polynomials II
Chapter 2: Greedy Algorithms
Greedy Interval Scheduling, Nearest-Neighbor TSP, Exchange Arguments

Week 4 (05.11.): Exchange Arguments, Minimum Spanning Trees, Matroids
Chapter 3: Dynamic Programming
Greedy Interval Scheduling, Nearest-Neighbor TSP, Exchange Arguments

Week 5 (12.11.): Knapsack
Chapter 4: Amortized Analysis
Accounting Method, Potential Function Method, Binary Counter and Dynamic Arrays

Week 6 (19.11.): The following three recordings are prerecorded lecture videos. There is no physical lecture on Tuesday, 19.11.2024.
Chapter 5: Data Structures
Union-Find: Basic Implementation
Union-Find: Disjoint-Set Forests
Priority Queues, Warm-Up

Week 7 (26.11.): Fibonacci Heaps

Week 8 (03.12.): Chapter 6: Graph Algorithms
Maximum Flow: Ford Fulkerson Algorithm

Week 9 (10.12.): Applications of Maximum Flow