15-451: Algorithms
Spring 2015
Schedule
Please keep in mind that this is very preliminary and will 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 |