Lecture: Tu/Th 3:30  5:00 pm, Dwinelle 155
Textbook: Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani (DPV)
Week  Date  Lecture  Reading  Section  Assignments 

1 
Tu 1/21 
Introduction, bigO notation, arithmetic webcast 
DPV §0 , §1.1  
Th 1/23 
DivideandConquer Part I webcast 
DPV §2.1 , §2.2 , §2.3  
2 
Tu 1/28 
DivideandConquer Part II webcast 
DPV §2.4 , §2.5 , §2.6  
Th 1/30 
Fast Fourier Transform webcast 
DPV §2.6  
3 
Tu 2/4 
Decompositions of graphs webcast 
DPV §3  
Th 2/6 
Paths in graphs Part I webcast 
DPV §4.1 , §4.2 , §4.3 , §4.4  
4 
Tu 2/11 
Paths in graphs Part II webcast 
DPV §4.4 , §4.5 , §4.6 , §4.7  
Th 2/13 
Greedy Algorithms webcast 
DPV §5.4  
5 
Tu 2/18 
Minimum Spanning Trees webcast 
DPV §5.1  
Th 2/20 
Midterm 1 on Th 2/20 (No lecture)  
6 
Tu 2/25 
Union Find webcast 
DPV §5.1.4  
Th 2/27 
Dynamic Programming Part I notebook webcast 
DPV §6  
7 
Tu 3/3 
Dynamic Programming Part II webcast 
DPV §6  
Th 3/5 
Linear Programming and Duality webcast 
DPV §7.1 , §7.4  
8 
Tu 3/10 
Network Flow webcast 
DPV §7.2  
Th 3/12 
Network Flow webcast 
DPV §7.2  
9 
Tu 3/17 
ZeroSum Games webcast 
DPV §7.5  
Th 3/19 
Multiplicative Updates webcast 
notes  
10 
Tu 3/24 
Spring Break  
Th 3/26 
Spring Break  
11 
Tu 3/31 
Reductions, Bipartite Matching webcast 
DPV §7.3 


Th 4/2 
No Lecture (Time to work on the checkpoint)  
12 
Tu 4/7 
Search Problems webcast 
DPV §8.1 


Th 4/9 
NPCompleteness webcast 
DPV §8.2 , §8.3  
13 
Tu 4/14 
Coping with NPCompleteness webcast 
DPV §9 


Th 4/16 
Randomized Algorithms webcast 
notes  
14 
Tu 4/21 
Sketching, Streaming webcast 
notes 


Th 4/23 
Lower Bounds webcast 
notes  
15 
Tu 4/28 
Hashing webcast 
DPV §1.5 


Th 4/30 
Special Topic webcast 