| Topic |
Recordings |
Slides |
|
| Chapter 1: Divide and
Conquer |
|
|
| Part I: Introduction & Time
Analysis |
|
|
| Part II: Comparing Orders &
Closest Pair of Points |
|
|
| Part III:
Operations on Polynomials, Karatsuba Alg.
|
|
|
| Part IV: Fast Polynomial Multiplication 1 |
|
|
| Part V: Fast Polynomial Multiplication 2 |
|
|
|
| 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 |
|
|
|
| Chapter 3: Dynamic Programming |
|
|
Part I: Weighted Interval Scheduling
|
|
|
| Part II: Matrix Chain Multiplication |
|
|
| Part III: The Knapsack Problem |
|
|
|
| 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
|
|
|
| Part III: Priority Queues, Warm-Up |
|
|
| Part IV: Fibonacci Heaps, Algorithm Description |
|
|
| Part V: Fibonacci Heaps, Amortized Analysis |
|
|
|
| Chapter 6: Graph Algorithms |
|
|
Part I: Maximum Flow: Ford Fulkerson Algorithm
|
|
|
| Part II: Basic Ford Fulkerson Analysis |
|
|
| Part III: Fast Ford Fulkerson Implementations |
|
|
| Part IV: Simple Maximum Flow Applications |
|
|
| Part V: Baseball Elimination |
|
|
| Part VI: Circulation |
|
|
| Part VII: Matrix Rounding |
|
|
| Part VIII: Bipartite Maximum Matching
|
|
|
| Part IX: Maximum Matching in General Graphs |
|
|
|
| Chapter 7: Randomized Algorithms |
|
|
Part I: Contention Resolution |
|
|
| Part II: Primality Testing |
|
|
| Part III: Randomized Quicksort: Expected Time |
|
|
| Part IV: Rand. Quicksort: High Probability Bound |
|
|
| 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 |
|
|
|
| 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 |
|
|
|
| Chapter 9: Online Algorithms |
|
|
Part I: Deterministic Paging |
|
|
| Part II: Randomized Paging |
|
|
|
