Lectures
| Date | Lecture | Readings and additional material |
|---|---|---|
| 01/27/20 | Lecture 1: Introduction I: Euclidean algorithm, Fibonacci numbers and computational problems classification. | CLRS 3.2, CRLS 31.2, Fast Fibonacci calculation, P and NP, Online C compiler |
| 01/29/20 | Lecture 2: Introduction II: Insertion sort, asymptotic notation and mergesort. | CLRS 2, CRLS 3, Bottom-up mergesort C code |
| 02/03/20 | Lecture 3: Divide and conquer I: Maximum subarray, substitution method and master theorem. | CLRS 4.1, CRLS 4.3, CLRS 4.5, Recursive mergesort C code |
| 02/05/20 | Lecture 4: Divide and conquer II: Multiplication of integers (Karatsuba) and matrices (Strassen). | CLRS 4.2, Notes on Karatsuba algorithm |
| 02/10/20 | Lecture 5: Divide and conquer III: Order statistics in linear time. | CLRS 9.3, Notes on linear-time selection |
| 02/12/20 | Lecture 6: Randomized algorithms I: Quicksort. | CLRS 7, Notes on Quicksort analysis |
| 02/17/20 | Lecture 7: Randomized algorithms II: Balanced allocation (balls and bins), polynomial identity verification (Schwartz–Zippel) and matrix product verification (Freivald). | CLRS 5.4.1, Balls and bins analysis, Schwartz–Zippel lemma, Freivalds’ algorithm |
| 02/19/20 | Lecture 8: Randomized algorithms III: Minimum cuts (Karger) and set balancing (Chernoff bounds). | CLRS 5.4.2, Randomized minimum cuts, Set balancing and Chernoff bounds |
| 02/24/20 | Lecture 9: Dynamic programming I: Rod cutting. | CLRS 15.1 |
| 02/26/20 | Lecture 10: Dynamic programming II: Longest common subsequence. | Notes on longest common subsequence |
| 03/02/20 | Lecture 11: Dynamic programming III: Matrix chain multiplication and segmented least squares. | CLRS 15.2, Notes on segmented least squares |
| 03/04/20 | Lecture 12: Greedy algorithms I: Activity selection and fractional knapsack. | CLRS 16.1, Notes on fractional knapsack |
| 03/06/20 | Lecture 13: Greedy algorithms II: Set cover and minimum spanning trees. | Notes on set cover, Notes on minimum spanning trees |
| 03/30/20 | Lecture 14: Basic data structures I: Stacks, Queues, Linked Lists. | CLRS 10 |
| 04/01/20 | Lecture 15: Basic data structures II: Universal hashing. | CLRS 11 |
| 04/06/20 | Lecture 16: Basic data structures III: Open addressing. | CLRS 11 |
| 04/08/20 | Lecture 17: Search trees I: Binary search trees. | CLRS 12 |
| 04/13/20 | Lecture 18: Search trees II: Red-black trees (insertion). | CLRS 13, Notes on red-black trees by Lyn Turbak |
| 04/15/20 | Lecture 19: Search trees III: Red-black trees (deletion). | CLRS 13, Notes on red-black trees by Lyn Turbak |
| 04/20/20 | Lecture 20: Graph Algorithms I: Breadth first search. | CLRS 22.2 |
| 04/22/20 | Lecture 21: Graph Algorithms II: Dijskta’s algorithm. | CLRS 24.3 |
| 04/27/20 | Lecture 22: NP-completeness I: Definitions | CLRS 34 |
| 04/29/20 | Lecture 23: NP-completeness II: Reductions | CLRS 34 |
| 05/04/20 | Lecture 24: Special Topics I: FFT algorithm | |
| 05/06/20 | Lecture 25: Special Topics II: Aproximation algorithms | |
| 05/11/20 | Lecture 26: Discussion on the final |