Day 
Date 
Instr 
Topics Covered 
Notes and Readings 
Mon 
Jan 12 
Victor 
Lecture 1: Introduction/Master Theorem/Karatsuba 
Slides 
Tue 
Jan 13 

Recitation 1  BigOh and recurrences. 
Recitation notes

Wed 
Jan 14 
Victor 
Lecture 2: Strassen/FFT 
Slides  Homework 1 out

Mon 
Jan 19 

Martin Luther King Day  No Class 

Tue 
Jan 21 

Recitation 2  Multiplication 
Recitation notes

Wed 
Jan 21 
Victor 
Lecture 3: FFT 
Slides  Homework 2 out

Mon 
Jan 26 
Danny 
Lecture 4: Dynamic programming  I 
Notes

Tue 
Jan 27 

Recitation 3  DP 
Recitation notes

Wed 
Jan 28 
Danny 
Lecture 5: Dynamic programming  II 
Notes  Homework 3 out

Mon 
Feb 02 
Danny 
Lecture 6: Amortized Analysis 
Sleator's notes 
Growing/Shrinkng Table 
Victor's notes

Tue 
Feb 03 

Recitation 4  Amortized Analysis 
Recitation notes

Wed 
Feb 04 
Danny 
Lecture 7: Splay Trees and Amortized Analysis 
Notes

Mon 
Feb 09 
Victor 
Lecture 8: DFS, Biconnected Graphs 
LectureNotes 
Tue 
Feb 10 

Recitation 5  Splay Trees 
Recitation notes

Wed 
Feb 11 
Victor 
Lecture 9: Tarjan's SCC 
LectureNotes

Mon 
Feb 16 
Victor 
Lecture 10: Arborescences 
LectureNotes

Tue 
Feb 17 

Recitation 6  Graphs 
Recitation notes

Wed 
Feb 18 
Danny 
Lecture 11: Edmond's Blossom Algorithm 
LectureNotes 
Mon 
Feb 23 

Inclass Midterm
 Practice Exam  Solutions 

Tue 
Feb 24 

Recitation 7 
Recitation notes

Wed 
Feb 25 
Victor 
Lecture 12: Maximum Flow 
LectureNotes 
notes 1 
notes 2

Mon 
Mar 02 
Victor 
Lecture 13: Minimum Cost Maximum Flow 
LectureNotes 
Tue 
Mar 03 

Recitation 8 
Recitation notes

Wed 
Mar 04 
Danny 
Lecture 14: Fibonacci Heaps 
Lecture Notes

Mon 
Mar 09 

Spring Break  No Class 

Tue 
Mar 10 

Spring Break  No Class 

Wed 
Mar 11 

Spring Break  No Class 

Mon 
Mar 14 
Danny 
Lecture 15: Computational Geometry  I (Convex Hull) 
Lecture Notes

Tue 
Mar 15 

Recitation 9 
Recitation notes

Wed 
Mar 18 
Danny 
Lecture 16: Computational Geometry  II (Closest Pair) 
Lecture Notes

Mon 
Mar 23 
Danny 
Lecture 17: Voronoi Diagrams and Delaunay Triangulations 
Lecture Notes

Tue 
Mar 24 

Recitation 10  Linear Programming 
Recitation notes

Wed 
Mar 25 
Danny 
Lecture 18: Linear Programming I 
Gupta Notes

Mon 
Mar 30 
Danny 
Lecture 19: Linear Programming II 
2DLP
Duality

Tue 
Mar 31 

Recitation 11  LP 

Wed 
Apr 01 

Inclass Midterm
 Practice Exam
 Solutions


Mon 
Apr 06 
Victor 
Lecture 20: NPCompleteness I 
Slides 
Tue 
Apr 07 

Recitation 12  P vs NP 

Wed 
Apr 08 
Victor 
Lecture 21: Aproximation Algorithms 
Slides 
Mon 
Apr 13 
Victor 
Lecture 22: Online Algorithms and Competitive Analysis 
Slides 
Tue 
Apr 14 

Recitation 13  Approximations 

Wed 
Apr 15 
Dannay 
Lecture 23: Randomized Online Algorithms 
Notes 
Mon 
Apr 20 
Victor 
Lecture 24: String Matching 
lecture notes 
Tue 
Apr 21 

Recitation 14  Online Algorithms 

Wed 
Apr 22 
Danny 
Lecture 25: Suffix Trees 
Lecture Notes

Mon 
Apr 27 
Danny 
Lecture 26: Least Common Ancestors and Range Min Queries 
Lecture Notes

Tue 
Apr 28 

Recitation 15  String Matching 

Wed 
Apr 29 
Victor 
Lecture 27: Review 
lecture notes 
Mon 
May 4 

Final Exam 
Final Exam with Solutions 