Date 
Title 
Topics 
Reading 




9/7 
Intro, BigO, 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 facetoface lecture!!
Minimum spanning trees III (brief)
UnionFind I (main part)

Watch recorded lectures from Spring 2021 (linked below)
Prim's algorithm: slides video
Dynamic connectivity problem, UnionFind: notes slides video


9/21 
UnionFind II Shortest paths I 
Weighted QuickUnion, Path compression Singlesource shortest paths problem: slides

CLRS: Chapter 24 (everything except for Section 24.4)

9/26 
Shortest paths II 
Singlesource shortest paths problem, BFS solution, DFSbased solution
slides


9/28 
Shortest paths III 
Dijkstra's algorithm, BellmanFord algorithm
slides






10/3 
Shortest paths IV Network flows I 
BellmanFord continued, Allpairs shortest paths problem, FloydWarshall algorithm
Flow networks
slides

KT: Sections 7.17.2

10/5 
Network flows II 
MaxFlow problem, MinCut problem
Augmenting paths, FordFulkerson algorithm
slides


10/10 
NO CLASS 
Thanksgiving


10/12 
Network flows III 
Analysis of FordFulkerson algorithm,
MaxFlow MinCut Theorem
slides

CLRS: Sections 26.1  26.2 (for analysis of EdmondsKarp)



Midterm  Monday, October 17th




Randomized Algorithms 

10/19 
EdmondsKarp algorithm

EdmondsKarp


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 
Directaddress tables, Hash tables, Averagecase 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, RabinKarp algorithm: slides


11/23 
String search II

KnuthMorrisPratt algorithm

KT: Sections 4.14.3 (but 4.3 is optional)

11/28 
Greedy algorithms 
Interval scheduling, Interval partitioning, Scheduling to minimize lateness
slides

KT: Sections 6.16.4

11/30 
Dynamic programming

Weighted interval scheduling, Knapsack
slides

CLRS: Section 15.4
