| Date |
Title |
Topics |
Reading |
|
|
|
|
|
| 9/7 |
Intro, Big-O, RAM model |
Course overview, Asymptotic notation, RAM model
slides
|
CLRS: Chapters 1–3
|
| |
|
|
|
| |
|
Graph algorithms |
|
| 9/12 |
Minimum spanning trees I |
Minimum spanning tree problem, Kruskal's algorithm, Prim's algorithm
|
KT: Section 4.5 or CLRS: Chapter 23
|
| 9/14 |
Minimum spanning trees II |
Kruskal's algorithm, Prim's algorithm
slides
|
KT: 4.6 or CLRS: Sections 21.1–21.3
|
|
|
Problem Set 1 (to be released on Sep 14 night) - Due Friday, Sep 30 at 11:55pm
|
|
| 9/19 |
No face-to-face lecture!!
Minimum spanning trees III (brief)
Union-Find I (main part)
|
Watch recorded lectures from Spring 2021 (linked below)
Prim's algorithm: slides video
Dynamic connectivity problem, Union-Find: notes slides video
|
|
| 9/21 |
Union-Find II
Shortest paths I |
Weighted Quick-Union, Path compression
Single-source shortest paths problem: slides
|
CLRS: Chapter 24 (everything except for Section 24.4)
|
| 9/26 |
Shortest paths II |
Single-source shortest paths problem, BFS solution, DFS-based solution
slides
|
|
| 9/28 |
Shortest paths III |
Dijkstra's algorithm, Bellman-Ford algorithm
slides
|
|
| |
|
|
|
| 10/3 |
Shortest paths IV
Network flows I |
Bellman-Ford continued, All-pairs shortest paths problem, Floyd-Warshall algorithm
Flow networks
slides
|
KT: Sections 7.1-7.2
|
| 10/5 |
Network flows II |
Max-Flow problem, Min-Cut problem
Augmenting paths, Ford-Fulkerson algorithm
slides
|
|
| 10/10 |
NO CLASS |
Thanksgiving
|
|
| 10/12 |
Network flows III |
Analysis of Ford-Fulkerson algorithm,
Max-Flow Min-Cut Theorem
slides
|
CLRS: Sections 26.1 - 26.2 (for analysis of Edmonds-Karp)
|
|
|
Midterm - Monday, October 17th
|
|
| |
|
Randomized Algorithms |
|
| 10/19 |
Edmonds-Karp algorithm
|
Edmonds-Karp
|
|
| 10/24 |
Selecting the kth smallest element |
Quickselect with median of medians pivot
slides
|
• CLRS: Section 9.3
• Avrim Blum's notes: Section 4.3
|
| 10/26 |
Randomized Quickselect and Quicksort |
Basic probability: slides
Randomized Quickselect: slides
|
• Luca
Trevisan's notes: Sections 1 and 2 (Basic probability)
• Randomized analysis handout
• KT: Section 13.5
or
CLRS: Chapter 7
|
| 10/31 |
Randomized Quickselect and Quicksort |
Randomized Quickselect and Randomized Quicksort
|
CLRS: Chapter 11
(Section 11.3.3 is recommended; Section 11.5 is optional)
|
| 11/2 |
Hashing I |
Direct-address tables, Hash tables, Average-case analysis
slides
|
|
| |
|
|
|
| 11/7 |
Hashing II |
Universal hashing, Open addressing
|
|
| 11/9 |
NO CLASS |
Reading break
|
|
| |
|
Algorithms |
|
| 11/14 |
Hashing III
Amortized Analysis I |
Open addressing
Aggregate analysis, Accounting method: slides
|
CLRS: Chapter 17
|
| 11/16 |
Amortized Analysis II |
Accounting method (Dynamic tables)
|
CLRS: Chapter 32 (excluding section 32.4)
|
| 11/21 |
Amortized Analysis III
String search I |
Accounting method (Dynamic tables)
Substring search problem, Rabin-Karp algorithm: slides
|
|
| 11/23 |
String search II
|
Knuth-Morris-Pratt algorithm
|
KT: Sections 4.1-4.3 (but 4.3 is optional)
|
| 11/28 |
Greedy algorithms |
Interval scheduling, Interval partitioning, Scheduling to minimize lateness
slides
|
KT: Sections 6.1-6.4
|
| 11/30 |
Dynamic programming
|
Weighted interval scheduling, Knapsack
slides
|
CLRS: Section 15.4
|