| Date | # | Slides | Notes | |
|---|---|---|---|---|
| Week 1 | ||||
| Tue 8/28 | 1 | Scribbles |
NP Completeness I
NP Completeness II NP Completeness III |
|
| Thu 8/30 | 2 |
Scribbles
(transcript) |
||
| Discussion 1 notes. | ||||
| Week 2 | ||||
| Tue 9/4 | 3 | Scribbles |
Dynamic Programming
|
|
| Thu 9/6 | 4 | Scribbles | Even MORE Dynamic Programming | |
| Discussion 2 notes. | ||||
| Week 3 | ||||
| Tue 9/11 | 5 | Scribbles |
Deterministic median selection Quick select Lowest point above all lines | |
| Thu 9/13 | 6 | slides | Fast Fourier Transform | |
| Disc. 3: More dyanmic programming | ||||
| Week 4 | ||||
| Disc. 4: FFT | ||||
| Tue 9/18 | 7 | slides | Sorting Networks | |
| Thu 9/20 | 8 | scribbles: |
Covered in class:
Probability, Chernoff's inequality, quicksort with high probability.
Randomized Algorithms I QuickSort: high probabiliyt |
|
| Week 5 | ||||
| Disc. 5: some randomized algorithms | ||||
| Tue 9/25 | 9 | scribbles | hashing | |
| Thu 9/27 | 10 | scribbles | Backward analysis | |
| Week 6 | ||||
| Tue 10/2 | Midterm 1: 7pm-9pm, DCL 1320 | |||
| Thu 10/4 | 11 | Scribbles | Mincut | |
| Week 7 | ||||
| Tue 10/9 | 12 | Scribbles | Streaming | |
| Thu 10/11 | 13 | Scribbles |
Approximation algorithms
Approximation algorithms II Approximation algorithms III |
|
| Week 8 | ||||
| Tue 10/16 | 14 | scribbles | TSP, Max SAT | |
| Thu 10/18 | 15 | slides | Approx subset sum, Max Matching, Bin Packing, Independent set of rectangles. | |
| Week 9 | ||||
| Tue 10/23 | 16 | Scribbles | Matchings | |
| Thu 10/25 | 17 | Scribbles | Matchings II | |
| Week 10 | ||||
| Tue 10/30 | 18 | Scribbles | Network flow I | |
| Thu 11/1 | 19 | Scribbles | Network flow: II, III, IV. | |
| Week 11 | ||||
| Tue 11/6 | 20 | Scribbles | Linear programming -- low dimension | |
| Thu 11/8 | 21 | slides and more slides | ||
| Tue 11/13 | Midterm 2: 7-9pm, DCL 1310 | |||
| Thu 11/15 | 22 | More on linear programming |
slides
and more
slides.
Scribbled ver: a and b. |
|
| 11/17-26 Say thanks, go on vacation | ||||
| Tue 11/27 | 23 | Scribbles | Approximation algorithms via LP. | |
| Thu 11/29 | 24 | scribbles | Max cut | |
| Tue 12/4 | 25 | scribbles | A bit on Machine Learning, | |
| Thu 12/6 | 26 | slides and more slides. | Entropy and Huffman's compression | |
| Tue 12/11 | FINAL | In class final (during regular lecture time). | ||