Lecture videos and answers to homeworks for Algorithms: Design and Analysis, Part 2 - an online course offered by Stanford University and taught by Prof. Tim Roughgarden.
1.1 Application: Internet Routing
1.2 Application: Sequence Alignment
2.1 Introduction to Greedy Algorithms
2.2 Application: Optimal Caching
3.3 Correctness Proof - Part I
3.4 Correctness Proof - Part II
3.5 Handling Ties (Advanced - Optional)
4.5 Proof of Cut Property (Advanced - Optional)
5.2 Correctness of Kruskal's Alogrithm
5.3 Implementing Kruskal's Alogrithm via Union-Find I
5.4 Implementing Kruskal's Alogrithm via Union-Find II
5.5 MSTs: State-of-the-Art and Open Questions (Advanced - Optional)
6.2 Correctness of Clustering Algorithm
7.1 Lazy Unions (Advanced - Optional)
7.2 Union-By-Rank (Advanced - Optional)
7.3 Analysis of Union-By-Rank (Advanced - Optional)
7.4 Path Compression (Advanced - Optional)
7.5 Path Compression: The Hopcroft-Ullman Analysis I (Advanced - Optional)
7.6 Path Compression: The Hopcroft-Ullman Analysis II (Advanced - Optional)
7.7 The Ackermann Function (Advanced - Optional)
7.8 Path Compression: Tarjan's Analysis I (Advanced - Optional)
7.9 Path Compression: Tarjan's Analysis II (Advanced - Optional)
8.1 Introduction and Motivation
9.1 Introduction: Weighted Independent Sets in Path Graphs
9.2 WIS in Path Graphs: Optimal Substructure
9.3 WIS in Path Graphs: A Linear-Time Algorithm
9.4 WIS in Path Graphs: A Reconstruction Algorithm
9.5 Principles of Dynamic Programming
10.1 The Knapsack Problem
10.2 A Dynamic Programming Algorithm
10.3 Example [Review - Optional]
11.1 Optimal Substructure
11.2 A Dynamic Programming Algorithm
12.1 Problem Definition
12.2 Optimal Substructure
12.3 Proof of Optimal Substructure
12.4 A Dynamic Programming Algorithm I
12.5 A Dynamic Programming Algorithm II
13.1 Single-Source Shortest Paths, Revisted
13.2 Optimal Substructure
13.5 Detecting Negative Cycles
13.6 A Space Optimization
13.7 Internet Routing I (Optional)
13.8 Internet Routing II (Optional)
14.1 Problem Definition
14.2 Optimal Substructure
14.3 The Floyd-Warshall Algorithm
15.1 Polynomial-Time Solvable Problems
15.2 Reductions and Completeness
15.3 Definition and Interpretation of NP-Completeness I
15.4 Definition and Interpretation of NP-Completeness II
15.6 Algorithmic Approaches to NP-Complete Problems
16.2 Smarter Search for Vertex Cover I
16.3 Smarter Search for Vertex Cover II
16.4 The Traveling Salesman Problem
16.5 A Dynamic Programming Algorithm for TSP
17.1 A Greedy Knapsack Heuristic
17.2 Analysis of a Greedy Knapsack Heuristic I
17.3 Analysis of a Greedy Knapsack Heuristic II
17.4 A Dynamic Programming Heuristic for Knapsack
17.5 Knapsack via Dynamic Programming, Revisited
17.6 Analysis of Dynamic Programming Heuristic
18.1 The Maximum Cut Problem I
18.2 The Maximum Cut Problem II
18.3 Principles of Local Search I
18.4 Principles of Local Search II
18.5 The 2-SAT Problem
18.7 Analysis of Papadimitriou's Algorithm
19.1 Stable Matching (Optional)