15-451: Algorithms
Spring 2014
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 |