W Jan 20 | Introduction; read Chapters 1-2 for background |
M Jan 25 | Asymptotic notation; read lectures notes Ch. 9; CLRS Ch. 3 |
W Jan 27 | Sums; read lecture notes Ch. 7 |
M Feb 01 | Lower bounds |
T Feb 02 | Flipped: Finding the 2nd Largest Element |
W Feb 03 | Lower bounds |
M Feb 08 | Review: Divide and Conquer (optional) |
M Feb 08 | Review: Strassen's matrix multiplication (optional) |
M Feb 08 | Divide and Conquer; read Chapter 4 |
T Feb 09 | Flipped: Fast Fourier Transform, Part I |
T Feb 09 | Flipped: Fast Fourier Transform, Part II |
W Feb 10 | Divide and Conquer; Fast Fourier Transform |
M Feb 15 | Review: Greedy Algorithms: Giving Change (review) |
M Feb 15 | Greedy Algorithms; read Chapter 16 |
W Feb 16 | Greedy Algorithms and Matroids; read Chapter 16 |
W Feb 16 | Review: Greedy Algorithms and Matroids |
M Feb 22 | Greedy Algorithms; Dynamic Programming; read Chapter 15 |
T Feb 23 | Flipped: Bipartite Matching |
W Feb 24 | Dynamic Programming; read Chapter 15 |
R Feb 25 | Flipped: Matrix Chain video |
S Feb 27 | Review: Amortized Analysis of the Multipop Stack |
M Feb 29 | Amortized Analysis; read Chapter 17 |
W Mar 02 | Midterm |
M Mar 07 | Midterm solution; Amortized Analysis; Graph Algorithms |
T Mar 08 | Review: Amortized Analysis of vector::push_back |
W Mar 09 | Topological Sorting, Strongly Connected Components, Quiz |
M Mar 14 | Spring break |
W Mar 16 | Spring break |
M Mar 21 | Shortest Path Algorithms |
W Mar 23 | Randomized Algorithms, background; Quiz |
W Mar 23 | Flipped: Background on Probability Theory |
M Mar 28 | Randomized algorithms; minimum cut |
W Mar 30 | Randomized Algorithms; Randomized Quicksort and Selection |
M Apr 04 | Birthday problems |
W Apr 06 | 2SAT, Complexity Theory |
M Apr 11 | Complexity Theory: The Complexity Classes P and NP |
W Apr 13 | Complexity Theory: NP-Completeness, SAT, 3SAT |
R Apr 14 | Flipped: Read Chapter 34 in CLRS |
M Apr 18 | Complexity Theory |
W Apr 20 | Complexity Theory |
M Apr 25 | Undecidability |
W Apr 27 | Undecidability, Complexity Potpurri, Quiz |
M May 02 | Review |