15-451/651: Algorithm Design and Analysis

Spring 2024

- PDF Schedule (last updated Jan-21 2024)
- Cumulative Notes

Tue 16-Jan | Lecture 1: Introduction, Algorithm Analysis, Linear-time Selection | [Notes] [Slides] [Further Review] |

Thu 18-Jan | Lecture 2: Concrete Models and Lower Bounds | [Notes] [Slides] [Further Review] |

Homework 1 released | [Homework 1] | |

Fri 19-Jan | Recitation 1: Lower Bounds | [Recitation 1] [Solutions] |

Tue 23-Jan | Lecture 3: Integer Models and Integer Sorting | [Notes] [Slides] |

Wed 24-Jan | Homework 1 due | [Solutions] |

Thu 25-Jan | Lecture 4: Hashing: Universal and Perfect Hashing | [Notes] [Slides] [Further Review] |

Homework 2 released | [Homework 2] | |

Fri 26-Jan | Recitation 2: Integer Sorting and Hashing | [Recitation 2] [Solutions] |

Tue 30-Jan | Lecture 5: Fingerprinting | [Notes] [Slides] [Further Review] |

Programming 1 Released | [Programming 1] | |

Wed 31-Jan | Homework 2 due | [Solutions] |

Thu 01-Feb | Lecture 6: Amortized Analysis with Potential Functions^{†} |
[Notes] [Slides] [Further Review] |

Homework 3 released | [Homework 3] | |

Fri 02-Feb | Recitation 3: Fingerprinting and Potential Functions | [Recitation 3] [Solutions] |

Tue 06-Feb | Lecture 7: Union-Find (More Amortized Analysis!) | [Notes] [Slides] |

Wed 07-Feb | Homework 3 orals | |

Thu 08-Feb | Lecture 8: Range Query Data Structures | [Notes] [Slides] [Further Review] |

Homework 3 orals | ||

Fri 09-Feb | Recitation 4: Union-Find and SegTrees (Range Queries) | [Recitation 4] [Solutions] |

Programming 1 due | ||

Homework 3 orals | [Solutions] |

Tue 13-Feb | Midterm One at 7:00pm | |

Thu 15-Feb | Lecture 9: Dynamic Programming | [Notes] [Slides] [Further Review] |

Homework 4 released | [Homework 4] | |

Fri 16-Feb | Recitation 5: Dynamic Programming | [Recitation 5] [Solutions] |

Tue 20-Feb | Lecture 10: Dynamic Programming II | [Notes] [Slides] [Further Review] |

Programming 2 Released | [Programming 2] | |

Thu 22-Feb | Lecture 11: Network Flows I: Flows, Cuts, and Matchings | [Notes] [Slides] [Further Review] |

Homework 4 due | [Solutions] | |

Homework 5 released | [Homework 5] | |

Fri 23-Feb | Recitation 6: Network Flow | [Recitation 6] [Solutions] |

Tue 27-Feb | Lecture 12: Network Flows II: Advanced Flow Algorithms | [Notes] [Slides] [Further Review] |

Wed 28-Feb | Homework 5 due | [Solutions] |

Thu 29-Feb | Lecture 13: Network Flows III: Minimum-cost Flows | [Notes] [Slides] [Further Review] |

Fri 01-Mar | Recitation 7: Advanced Flow | [Recitation 7] [Solutions] |

Programming 2 due |

Mon 04-Mar | Spring Break begins | |

Fri 08-Mar | Spring Break ends |

Tue 12-Mar | Lecture 14: Game Theory (alt. video) | [Notes] [Slides] [Further Review] |

Programming 3 released | [Programming 3] | |

Thu 14-Mar | Lecture 15: Linear Programming I: Fundamentals (alt. video) | [Notes] [Slides] [Further Review] |

Homework 6 released | [Homework 6] | |

Fri 15-Mar | Recitation 8: Game Theory and Linear Programming | [Recitation 8] [Solutions] |

Tue 19-Mar | Lecture 16: Linear Programming II: Seidel's Algorithm (alt. video) | [Notes] [Slides] [Further Review] |

Wed 20-Mar | Homework 6 orals | |

Thu 21-Mar | Lecture 17: Linear Programming III: Duality (alt. video) | [Notes] [Slides] [Further Review] |

Homework 6 orals | ||

Fri 22-Mar | Recitation 9: LP Duality and Algorithms | [Recitation 9] [Solutions] |

Homework 6 orals | [Solutions] | |

Programming 3 due |

Tue 26-Mar | Midterm Two at 7:00pm | |

Thu 28-Mar | Lecture 18: Approximation Algorithms | [Notes] [Slides] [Further Review] |

Homework 7 released | [Homework 7] | |

Fri 29-Mar | Recitation 10: Approximation Algorithms | [Recitation 10] [Solutions] |

Tue 02-Apr | Lecture 19: Online Algorithms | [Notes] [Slides] [Further Review] |

Programming 4 released | [Programming 4] | |

Wed 03-Apr | Homework 7 due | [Solutions] |

Thu 04-Apr | Lecture 20: Streaming Algorithms | [Notes] [Slides] [Further Review] |

Homework 8 released | [Homework 8] | |

Fri 5-Apr | Recitation 11: Online and Streamling Algorithms | [Recitation 11] [Solutions] |

Tue 09-Apr | Lecture 21: Computational Geometry I: Fundamentals | [Notes] [Slides] [Further Review] |

Wed 10-Apr | Homework 8 due | |

Homework Bonus released | [Homework Bonus] | |

Programming 4 due | ||

Thu 11-Apr | Spring Carnival begins | |

Sat 13-Apr | Spring Carnival ends |

Tue 16-Apr | Lecture 22: Computational Geometry II: Incremental Algorithms | [Notes] [Slides] [Further Review] |

Programming 5 released | [Programming 5] | |

Thu 18-Apr | Lecture 23: Polynomials in Algorithm Design | [Notes] [Slides] [Further Review] |

Homework 9 released | [Homework 9] | |

Fri 19-Apr | Recitation 12: Computation Geometry | [Recitation 12] [Solutions] |

Tue 23-Apr | Lecture 24: The Fast Fourier Transform | [Notes] [Slides] [Further Review] |

Wed 24-Apr | Homework 9 orals | |

Thu 25-Apr | Lecture 25: Online Learning (The Multiplicative Weights Algorithm) | [Notes] [Slides] [Further Review] |

Homework 9 orals | ||

Fri 26-Apr | Recitation 13: Polynomials, FFT, Online learning | [Recitation 13] [Solutions] |

Homework 9 orals | ||

Programming 5 due |

Tue 30-Apr | Final Exam at 5:30pm |