Schedule

Please keep in mind that this is very preliminary and may change.

Day Date  Instr Topics Covered Notes and Readings
Mon Jan 12 Victor Lecture 1: Introduction/Master Theorem/Karatsuba Slides
Tue Jan 13 Recitation 1 - Big-Oh 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 In-class 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 2D-LP   Duality
Tue Mar 31 Recitation 11 - LP
Wed Apr 01 In-class Midterm - Practice Exam - Solutions
Mon Apr 06 Victor Lecture 20: NP-Completeness 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