Schedule

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

Day Date Instr Topics Covered Notes and Readings
Mon Jan 13 Victor Lecture 1: Introduction, Master Theorem Slides - Lecture notes supplement
Tue Jan 14 Recitation 1 - Big-Oh and recurrences. Recitation notes
Wed Jan 15 Victor Lecture 2: Strassen Slides - Homework 1 out
Fri Jan 17 Victor Lecture 3: FFT Slides
Mon Jan 20 Martin Luther King Day - No Class
Tue Jan 21 Recitation 2 - FFT Recitation notes
Wed Jan 22 Victor Lecture 4: FFT II Slides - Homework 2 out
Fri Jan 24 Victor Lecture 5: Dynamic Programming: I Slides
Mon Jan 27 Victor Lecture 6: Dynamic programming II Slides
Tue Jan 28 Recitation 3 - DP Recitation notes
Wed Jan 29 Gary Lecture 7: Treaps and QuickSort ClassNotes - Kozen Chap 13

Homework 3 out

Fri Jan 31 Gary Lecture 8: Treaps-Continued + Amortized Analysis Intro ClassNotes - CLRS Chap 17
Mon Feb 03 Gary Lecture 9: Splay Trees and Amortized Analysis ClassNotes - Sleator's notes
Tue Feb 04 Recitation 4 - Treaps, Binomial Heaps, and Amortized Analysis Recitation notes
Wed Feb 05 Gary Lecture 10: Splay Trees
Fri Feb 07 Victor Lecture 11: Graphs I Slides - LectureNotes - Homework 4 out
Mon Feb 10 Victor Lecture 12: Graphs II Slides - LectureNotes - Sleator's notes
Tue Feb 11 Recitation 5 - Access Lemma and Static Optimality of Splay Trees
Wed Feb 12 Victor Lecture 13: Graphs III Slides - LectureNotes
Fri Feb 14 Victor Lecture 14: Graphs IV Slides - LectureNotes - Kleinberg-Tardos
Mon Feb 17 Gary Lecture 15: Sorting Lower Bounds, Backwards Analysis ClassNotes-Sorting
- ClassNotes-CompGeo
Tue Feb 18 Recitation 6 - Midterm Review Recitation notes
Wed Feb 19 Gary Lecture 16: Computational Geometry I:
Line Segment Intersection
ClassNotes -- BKOS Chap 2.1
Fri Feb 21 Gary Lecture 17: Computational Geometry II:

2D-Linear Programming

ClassNotes -- BKOS Chap 4.3-4.5 - Homework 5 out
Mon Feb 24 Gary Lecture 18: Computational Geometry III: LP-Boundedness -- Convex-hull ClassNotes -- LectureNotes
Tue Feb 25 Recitation 7 - Minimum Enclosing Disc Recitation notes
Wed Feb 26 Gary Lecture 19: Computational Geometry IV: Convex-hull Random Incremental ClassNotes -- LectureNotes
Fri Feb 28 Gary Lecture 20: Computational Geometry V: Closest Pair Using Hashing ClassNotes -- Har-Peled-Chap1

Homework 6 out
Mon Mar 03 Victor Lecture 21: Maximum Flow I A. Blum's notes
Tue Mar 04 Recitation 8 - Max-Flow and Application of Hashing Recitation notes
Wed Mar 05 Victor Lecture 22: Maximum Flow II A. Blum's notes
Fri Mar 07 Mid Semester Break - No Class
Mon Mar 10 Spring Break - No Class
Tue Mar 11 Spring Break - No Class
Wed Mar 12 Spring Break - No Class
Fri Mar 14 Spring Break - No Class
Mon Mar 17 Victor Lecture 23: Maximum Flow III
Tue Mar 18 Recitation 9 - Applications of Max-Flow and Min-Cut Recitation notes
Wed Mar 19 Victor Lecture 24: Minimum Cost Maximum Flow Sleator's notes
Fri Mar 21 Gary Lecture 25: Linear Programming Introduction ClassNotes -- Readings: CLRS Chapter 29 -- A Blum's notes -- Homework 7 out
Mon Mar 24 Gary Lecture 26: Linear Programming Examples Readings: CLRS Chapter 29 -- A Blum's notes
Tue Mar 25 Recitation 10 - Linear Programming Duality Recitation notes
Wed Mar 26 Gary Lecture 27: Linear Programming Duality ClassNotes -- Trevisan Chap 5,6,15 -- Gordon's Notes
Fri Mar 28 Gary Lecture 28: Parallel Algorithms I: Intro ClassNotes -- Homework 8 out
Mon Mar 31 Gary Lecture 29: Parallel Algorithms II: Prescan and List Ranking ClassNotes -- Blelloch Prefix Sum
Tue Apr 01 Recitation 11 - Parallel Tree Contraction Notes by Tangwongsan
Wed Apr 02 Gary Lecture 30: Parallel Algorithms III: More List Ranking ClassNotes -- Reid-Miller Chap 2
Fri Apr 04 Gary Lecture 31: Parallel Algorithms IV: Maximal Independent Set ClassNotes -- Julian Shun's Notes
Mon Apr 07 Victor Lecture 32: NP-Completeness I LectureNotes
Tue Apr 08 Recitation 12 - Reductions
Wed Apr 09 Victor Lecture 33: NP-Completeness II LectureNotes
Fri Apr 11 Spring Carnival - No Class
Mon Apr 14 Gary Lecture 34: Online Algorithms and Competitive Analysis ClassNotes -- LectureNotes Adamchik -- LectureNotes Sleator
Tue Apr 15 Recitation 13 - More reductions Jeff Erickson's notes
Wed Apr 16 Gary Lecture 35: Randomized Online Algorithms ClassNotes -- LectureNotes Sleator
Fri Apr 18 Gary Lecture 36: Randomized Online Algorithms: Continued ClassNotes -- LectureNotes Sleator
Mon Apr 21 Victor Lecture 37: Aproximation Algorithms - I lecture notes
Tue Apr 22 Recitation 14 - Parallel MIS and LP-relaxation of Vertex/Set Cover Kleinberg & Tardos 11.4 and 11.6
Wed Apr 23 Victor Lecture 38: Aproximation Algorithms - II lecture notes
Fri Apr 25 Victor Lecture 39: String Matching - I lecture notes
Mon Apr 28 Victor Lecture 40: String Matching - II lecture notes
Tue Apr 29 Recitation 15 - KMP Revisited Jeff Erickson's notes
Wed Apr 30 Victor Lecture 41: Tries and Suffix Trees lecture notes
Fri May 02 Gary Lecture 42: TBA Last Class