| 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
|
|
|
|
| Week 10 (17.12.): |
Maximum Matching
|
|
|
|
| Week 11 (07.01.): |
Chapter 7: Randomized Algorithms |
|
|
| Introduction / Primality Test
/ Randomized Quicksort |
|
|
|
| Week 12 (14.01.): |
Randomized Quicksort / Randomized Min Cut
|
|
|
|
| Week 13 (21.01.): |
The following three recordings are prerecorded lecture
videos. There is no physical lecture on Tuesday, 21.01.2025.
|
Implementing Edge Contractions |
|
|
| Fast Randomized Minimum Cut Algorithm |
|
|
| Cut Counting and Edge Sampling |
|
|
|
| Week 14 (28.01.): |
Chapter 8: Approximation Algorithms |
|
|
| Load Balancing, TSP, Set Cover, Knapsack |
|
|
|
| Week 14 (04.02.): |
Chapter 9: Online Algorithms |
|
|
| Online Paging Algorithms |
|
|
|
