Algorithm Theory
Winter Term 2020 / 2021
Fabian Kuhn
Recordings and Slides
| Topic | Recordings | Slides | |
| Week 1 (02.11. – 06.11.): | Introduction |
|
|
| Chapter 1: Divide and Conquer | |||
| Part I: Introduction & Time Analysis |
|
|
|
| Part II: Comparing Orders & Closest Pair of Points |
|
|
|
| Week 2 (09.11. – 13.11.): | Part III: Operations on Polynomials, Karatsuba Alg. |
|
|
| Part IV: Fast Polynomial Multiplication 1 |
|
|
|
| Part V: Fast Polynomial Multiplication 2 |
|
|
|
| Week 3 (16.11. – 20.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 (23.11. – 27.11.): | Chapter 3: Dynamic Programming | Part I: Weighted Interval Scheduling |
|
|
| Part II: Matrix Chain Multiplication |
|
|
|
| Part III: The Knapsack Problem |
|
|
|
| Week 5 (30.11. – 04.12.): | 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 (07.12. – 11.12.): | Part III: Priority Queues, Warm-Up |
|
|
| Part IV: Fibonacci Heaps, Algorithm Description |
|
|
|
| Part V: Fibonacci Heaps, Amortized Analysis |
|
|
|
| Week 7 (14.12. – 18.12.): | 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 (21.12. –
08.01.): (holiday break 23.12.–6.1.) |
Part IV: Simple Maximum Flow Applications |
|
|
| Part V: Baseball Elimination |
|
|
|
| Part VI: Circulation |
|
|
|
| Part VII: Matrix Rounding |
|
|
|
| Week 9 (11.01. – 15.01.): | Part VIII: Bipartite Maximum Matching |
|
|
| Part IX: Maximum Matching in General Graphs |
|
|
|
| Chapter 7: Randomized Algorithms | |||
| Part I: Contention Resolution |
|
|
|
| Week 10 (18.01. – 22.01.): | Part II: Primality Testing |
|
|
| Part III: Randomized Quicksort: Expected Time |
|
|
|
| Part IV: Rand. Quicksort: High Probability Bound |
|
|
|
| Week 11 (25.01. – 29.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 (01.02. – 05.02.): | 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 (08.02. – 12.02.): | Chapter 9: Online Algorithms | Part I: Deterministic Paging |
|
|
| Part II: Randomized Paging |
|
|
|