|
Topic |
Recordings |
Slides |
|
| Week 1 (17.10. – 21.10.):
|
| Chapter 1: Divide and
Conquer |
|
|
| Part I: Introduction & Time
Analysis |
|
|
| Part II: Comparing Orders &
Closest Pair of Points |
|
|
|
| Week 2 (24.10. – 28.10.): |
Part III:
Operations on Polynomials, Karatsuba Alg.
|
|
|
| Part IV: Fast Polynomial Multiplication 1 |
|
|
| Part V: Fast Polynomial Multiplication 2 |
|
|
|
| Week 3 (07.11. – 11.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 (14.11. – 18.11.): |
Chapter 3: Dynamic Programming |
|
|
Part I: Weighted Interval Scheduling
|
|
|
| Part II: Matrix Chain Multiplication |
|
|
| Part III: The Knapsack Problem |
|
|
|
| Week 5 (21.11. – 25.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 |
|
|
|
| Week 6 (28.11. – 02.12.): |
Part II: Union-Find: Disjoint-Set Forests |
|
|
| Part III: Priority Queues, Warm-Up |
|
|
| Part IV: Fibonacci Heaps, Algorithm Description |
|
|
|
| Week 7 (05.12. –
09.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 (12.12. – 16.12.): |
Part III: Fast Ford Fulkerson Implementations |
|
|
| Part IV: Simple Maximum Flow Applications |
|
|
| Part V: Baseball Elimination |
|
|
|
| Week 9 (19.12. – 23.12.): |
Part VI: Circulation |
|
|
| Part VII: Matrix Rounding |
|
|
| Part VIII: Bipartite Maximum Matching
|
|
|
|
| Week 10 (09.01. – 13.01.): |
Part IX: Maximum Matching in General Graphs |
|
|
| Chapter 7: Randomized Algorithms |
|
|
Part I: Contention Resolution |
|
|
| Part II: Primality Testing |
|
|
|
| Week 11 (16.01. – 20.01.): |
| Part III: Randomized Quicksort: Expected Time |
|
|
| Part IV: Rand. Quicksort: High Probability Bound |
|
|
|
| Week 12 (23.01. – 27.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 (30.01. – 3.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 (06.02. – 10.02.): |
Chapter 9: Online Algorithms |
|
|
Part I: Deterministic Paging |
|
|
| Part II: Randomized Paging |
|
|
|
