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
|
|
|
|