Lecture videos and answers to homeworks for Algorithms: Design and Analysis - an online course offered by Stanford University and taught by Prof. Tim Roughgarden.
1.4 About the Course
1.5 Merge Sort: Motivation and Example
1.8 Guiding Principles for Analysis of Algorithms
2.1 The Gist
2.2 Big-Oh Notation
2.3 Basic Examples
2.5 Additional Examples (Review - Optional)
3.1 O(n log n) Algorithm for Counting Inversions I
3.2 O(n log n) Algorithm for Counting Inversions II
3.3 Strassen's Subcubic Matrix Multiplication Algorithm
3.4 O(n log n) Algorithm for Closest Pair I (Advanced - Optional)
3.5 O(n log n) Algorithm for Closest Pair II (Advanced - Optional)
4.1 Motivation
4.2 Formal Statement
4.3 Examples
4.4 Proof I
4.5 Interpretation of the 3 Cases
4.6 Proof II
5.2 Partitioning Around a Pivot
5.3 Correctness of Quicksort (Review - Optional)
6.1 Analysis I: A Decomposition Principle (Advanced - Optional)
6.2 Analysis II: The Key Insight (Advanced - Optional)
6.3 Analysis III: Final Calculations (Advanced - Optional)
7.1 Probability Review I (Review - Optional)
7.2 Probability Review II (Review - Optional)
8.1 Randomized Selection - Algorithm
8.2 Randomized Selection - Analysis
8.3 Deterministic Selection - Algorithm (Advanced - Optional)
8.4 Deterministic Selection - Analysis I (Advanced - Optional)
8.5 Deterministic Selection - Analysis II (Advanced - Optional)
8.6 Omega(n log n) Lower Bound for Comparison-Based Sorting (Advanced - Optional)
9.3 Random Contraction Algorithm
9.4 Analysis of Contraction Algorithm
10.2 Breadth-First Search (BFS): The Basics
10.4 BFS and Undirected Connectivity
10.5 Depth-First Search (DFS): The Basics
10.6 Topological Sort
10.7 Computing Strong Components: The Algorithm
10.8 Computing Strong Components: The Analysis
10.9 Structure of the Web (Optional)
11.1 Dijkstra's Shortest-Path Algorithm
11.2 Dijkstra's Algorithm: Examples
11.3 Correctness of Dijkstra's Algorithm (Advanced - Optional)
11.4 Dijkstra's Algorithm: Implementation and Running Time
12.1 Data Structures: Overview
12.2 Heaps: Operations and Applications
12.3 Heaps: Implementation Details (Advanced - Optional)
13.1 Balanced Search Trees: Operations and Applications
13.2 Binary Search Tree Basics I
13.3 Binary Search Tree Basics II
13.4 Red-Black Trees
13.5 Rotations (Advanced - Optional)
13.6 Insertion in a Red-Black Tree (Advanced)
14.1 Hash Tables: Operations and Applications
14.2 Hash Tables: Implementation Details I
14.3 Hash Tables: Implementation Details II
15.1 Pathological Data Sets and Universal Hashing Motivation
15.2 Universal Hashing: Definition and Example (Advanced - Optional)
15.3 Universal Hashing: Analysis of Chaining (Advanced - Optional)
15.4 Hash Table Performance with Open Addressing (Advanced - Optional)