Algorithm Theory
Winter Term 2022 / 2023
Fabian Kuhn
Recordings and Slides
| Topic | Recordings | Slides | |
| Week 1 (16.10. – 20.10.): | Introduction |
|
|
| Chapter 1: Divide and Conquer | |||
| Part I: Introduction & Time Analysis |
|
|
|
| Part II: Comparing Orders & Closest Pair of Points |
|
|
|
| Week 2 (23.10. – 27.10.): | Part III: Operations on Polynomials, Karatsuba Alg. |
|
|
| Part IV: Fast Polynomial Multiplication 1 |
|
|
|
| Part V: Fast Polynomial Multiplication 2 |
|
|
|
| Week 3 (30.10. – 03.11.): | Chapter 2: Greedy Algorithms | Part I: Interval Scheduling & Partitioning |
|
|
| Part II: Traveling Salesperson Problem (TSP) |
|
|
|
| Part III: Exchange Arguments |
|
|
|
| Part IV: The Greedy Algorithm for Matroids |
|
|
|
| Week 4 (06.11. – 10.11.): | Chapter 3: Dynamic Programming | Part I: Weighted Interval Scheduling |
|
|
| Part II: Matrix Chain Multiplication |
|
|
|
| Part III: The Knapsack Problem |
|
|
|
| Week 5 (13.11. – 17.11.): | Chapter 4: Amortized Analysis | Part I: Basics & Accounting Method |
|
|
| Part II: Potential Function Method |
|
|
|
| Chapter 5: Data Structures | |||
| Part I: Union-Find: Basic Implementation |
|
|
|
| Part II: Union-Find: Disjoint-Set
Forests (last part on path compression will be covered in the lecture on 21.11.) |
|
|
|
| Week 6 (20.11. – 24.11.): | Part III: Priority Queues, Warm-Up |
|
|
| Part IV: Fibonacci Heaps, Algorithm Description |
|
|
|
| Week 7 (27.11. – 01.12.): | Part V: Fibonacci Heaps, Amortized Analysis |
|
|
| Chapter 6: Graph Algorithms | Part I: Maximum Flow: Ford Fulkerson Algorithm |
|
|
| Part II: Basic Ford Fulkerson Analysis |
|
|
|
| Week 8 (04.12. – 08.12.): | Part III: Fast Ford Fulkerson Implementations |
|
|
| Part IV: Simple Maximum Flow Applications |
|
|
|
| Part V: Baseball Elimination |
|
|
|
| Week 9 (11.12. – 15.12.): | Part VI: Circulation |
|
|
| Part VII: Matrix Rounding |
|
|
|
| Part VIII: Bipartite Maximum Matching |
|
|
|
| Week 10 (18.12. – 22.12.): | Part IX: Maximum Matching in General Graphs |
|
|
| Chapter 7: Randomized Algorithms | Part I: Contention Resolution |
|
|
| Week 11 (08.01. – 12.01.): | Part II: Primality Testing |
|
|
| Part III: Randomized Quicksort: Expected Time |
|
|
|
| Part IV: Rand. Quicksort: High Probability Bound |
|
|
|
| Week 12 (15.01. – 19.01.): | Part V: Basic Randomized Minimum Cut Algorithm |
|
|
| Part VI: Implementing Edge Contractions |
|
|
|
| Part VII: Fast Randomized Minimum Cut Algorithm |
|
|
|
| Part VIII: Cut Counting and Edge Sampling |
|
|
|
| Week 13 (22.01. – 26.01.): | Chapter 8: Approximation Algorithms | Part I: Greedy Load Balancing |
|
|
| Part II: The Metric TSP Problem |
|
|
|
| Part III: Minimum Set Cover |
|
|
|
| Part IV: Knapsack Approximation Scheme |
|
|
|
| Week 13 (29.01. – 02.02.): | Chapter 9: Online Algorithms | Part I: Deterministic Paging |
|
|
| Part II: Randomized Paging |
|
|
|
| Week 14 (05.02. – 09.02.): | Chapter 10: Parallel Algorithms |
|
|