Algorithm Theory
Winter Term 2021 / 2022
Fabian Kuhn
Recordings and Slides
| Topic | Recordings | Slides | |
| Week 1 (18.10. – 22.10.): | |||
| Chapter 1: Divide and Conquer | |||
| Part I: Introduction & Time Analysis |
|
|
|
| Part II: Comparing Orders & Closest Pair of Points |
|
|
|
| Week 2 (25.10. – 29.10.): | Part III: Operations on Polynomials, Karatsuba Alg. |
|
|
| Part IV: Fast Polynomial Multiplication 1 |
|
|
|
| Part V: Fast Polynomial Multiplication 2 |
|
|
|
| Week 3 (01.11. – 05.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 (08.11. – 12.11.): | Chapter 3: Dynamic Programming | Part I: Weighted Interval Scheduling |
|
|
| Part II: Matrix Chain Multiplication |
|
|
|
| Part III: The Knapsack Problem |
|
|
|
| Week 5 (15.11. – 19.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 |
|
|
|
| Week 6 (22.11. – 26.11.): | Part III: Priority Queues, Warm-Up |
|
|
| Part IV: Fibonacci Heaps, Algorithm Description |
|
|
|
| Part V: Fibonacci Heaps, Amortized Analysis |
|
|
|
| Week 7 (29.11. – 03.11.): | Chapter 6: Graph Algorithms | Part I: Maximum Flow: Ford Fulkerson Algorithm |
|
|
| Part II: Basic Ford Fulkerson Analysis |
|
|
|
| Part III: Fast Ford Fulkerson Implementations |
|
|
|
| Week 8 (06.12. – 10.12.): | Part IV: Simple Maximum Flow Applications |
|
|
| Part V: Baseball Elimination |
|
|
|
| Part VI: Circulation |
|
|
|
| Part VII: Matrix Rounding |
|
|
|
| Week 9 (13.12. – 17.12.): | Part VIII: Bipartite Maximum Matching |
|
|
| Part IX: Maximum Matching in General Graphs |
|
|
|
| Chapter 7: Randomized Algorithms | |||
| Part I: Contention Resolution |
|
|
|
| Week 10 (20.12. – 07.01.): (holiday break 23.12.–6.1.) |
Part II: Primality Testing |
|
|
| Part III: Randomized Quicksort: Expected Time |
|
|
|
| Part IV: Rand. Quicksort: High Probability Bound |
|
|
|
| Week 11 (10.01. – 14.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 12 (17.01. – 21.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 (24.01. – 28.01.): | Chapter 9: Online Algorithms | Part I: Deterministic Paging |
|
|
| Part II: Randomized Paging |
|
|
|
| Week 14 (31.01. – 04.02.): (recording of live lecture in February 2020, will not be part of the exam) |
Chapter 10: Parallel Algorithms | Part I: Parallel Algorithms 1 |
|
|
| Part II: Parallel Algorithms 2 |
|
|
|