Lecture: Tu/Th 9:30 am  11:00 am
Textbook: Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani (DPV)
Week  Date  Lecture  Reading  Section  Videos  Assignments 

1 
Tu 1/18 
Introduction, bigO notation, arithmetic webcast 
DPV §0 , §1.1  
Th 1/20 
DivideandConquer (Part I) webcast 
DPV §2.1 , §2.2 , §2.3  
2 
Tu 1/25 
DivideandConquer (Part II) webcast 
DPV §2.4 , §2.5 , §2.6 


Th 1/27 
Fast Fourier Transform webcast 
DPV §2.6  
3 
Tu 2/1 
Decompositions of graphs 
DPV §3 


Th 2/3 
Paths in graphs (Part I) 
DPV §4.1 , §4.2 , §4.3 , §4.4  
4 
Tu 2/8 
Paths in graphs (Part II) Prof. Wright's notes 
DPV §4.4 , §4.5 , §4.6 , §4.7 


Th 2/10 
Greedy Algorithms Prof. Wright's notes 
DPV §5 , §5.4  
5 
Tu 2/15 
Minimum Spanning Trees Prof. Wright's notes 
DPV §5.1 


Th 2/17 
Union Find Prof. Wright's notes 
DPV §5.1.4  
6 
Tu 2/22 
Dynamic Programming (Part I) Prof. Wright's notes 
DPV §6 


Th 2/24 
Dynamic Programming (Part II) Prof. Wright's notes 
DPV §6  
7 
Tu 3/1 
Dynamic Programming (Part III) Prof. Wright's notes 
DPV §6 


Th 3/3 
Dynamic Programming (Part IV) Prof. Raghavendra's notes 
DPV §7.1  
8 
Tu 3/8 
Linear Programming Prof. Raghavendra's notes 
DPV §7.2  
Th 3/10 
Network Flow + Bipartite Matching Prof. Raghavendra's notes 
DPV §7.4  
9 
Tu 3/15 
Duality + ZeroSum Games Prof. Raghavendra's notes 
DPV §7.5  
Th 3/17 
Multiplicative Updates Prof. Raghavendra's notes 
notes  
10 
Tu 3/22 
Spring Break 

Th 3/24 
Spring Break 

11 
Tu 3/29 
Reductions, Bipartite Matching Prof. Raghavendra's notes 
DPV §7.3  
Th 3/31 
Search Problems Prof. Raghavendra's notes 
DPV §8.1  
12 
Tu 4/5 
Midterm 2 

Th 4/7 
NPCompleteness Prof. Raghavendra's notes 
DPV §8.2 , §8.3  
13 
Tu 4/12 
Coping with NPcompleteness Prof. Raghavendra's notes 
DPV §9 


Th 4/14 
Streaming Prof. Raghavendra's notes 
DPV §1.2 , §1.3 notes  
14 
Tu 4/19 
Sketching, Streaming Prof. Wright's notes 
DPV §1.5 


Th 4/21 
Cancelled 

15 
Tu 4/26 
Randomized Algorithms Prof. Wright's notes 
DPV §1.3 notes §3 


Th 4/28 
Quantum Algorithms Prof. Wright's notes (Part 1)Prof. Wright's notes (Part 2) 