| Date | # | Scribbles | Notes | Slides |
|---|---|---|---|---|
| Week 1 | ||||
| Tue 8/24 | 1 | Scribbles |
NP Completeness I
NP Completeness II NP Completeness III |
slides |
| Thu 8/26 | 2 | Scribbles | slides | |
| Week 2 | ||||
| Tue 8/31 | 3 | Scribbles | Shopping list of NP complete problems. | |
| Thu 9/2 | 4 | Scribbles |
A quick review of graph algorithms See here for lectures/notes on the algorithms surveyed. |
|
| Week 3 | ||||
| Monday 9/6 | Labor day: Vacation day | |||
| Tue 9/7 | 5 | Scribbles | Dynamic Programming, | |
| Thu 9/9 | 6 | Scribbles | Even MORE Dynamic Programming | |
| Week 4 | ||||
| Tue 9/14 | 7 | scribbles: | Linear time algorithms: Lowest point above all lines, Deterministic median selection, Quick select. | |
| Thu 9/16 | 8 | scribbles: |
Divide & Conquer:
Maximum subarray,
Bucket sort,
Merge sort,
Strassen algorithm.
(Maybe closet pair.)
|
|
| Week 5 | ||||
| Tue 9/21 | 9 | scribbles | Fast Fourier Transform | |
| Thu 9/23 | 10 | scribbles | Sorting Networks | |
| Week 6 | ||||
| Tue 9/28 | Midterm 1: | |||
| Thu 9/30 | 11 | Scribbles |
Randomized Algorithms I
Some probability, nuts and bolts, neat analysis of quick sort. |
|
| Week 7 | ||||
| Tue 10/5 | 12 | Scribbles |
QuickSort: high probability
Markov inequality, Max cut 2 approx, Conditional expectation, QuickSort with high probability via conditional expectation.. Mentioned treaps. |
|
| Thu 10/7 | 13 | Scribbles | Treaps, Chernoff inequality, Galton-Watson process. | |
| Week 8 | ||||
| Tue 10/12 | 14 | scribbles | Mincut | |
| Thu 10/14 | 15 | scribbles |
hashing |
|
| Week 9 | ||||
| Tue 10/19 | 16 | scribbles |
Backward analysis |
|
| Thu 10/21 | 17 | Scribbles | Approximation algorithms | |
| Week 10 | ||||
| Tue 10/26 | 18 | Scribbles | Approximation algorithms II | |
| Thu 10/28 | 19 | Scribbles | Approximation algorithms III TSP, Max SAT Approx subset sum, Max Matching, Bin Packing, Independent set of rectangles. | |
| Week 11 | ||||
| Tue 11/2 | 20 | Scribbles | Linear programming -- low dimension | |
| Thu 11/4 | 21 | Scribbles | Matchings, Matchings II | |
| Tue 11/9 | Midterm 2: In class 3:30-5:30. | |||
| Thu 11/11 | 22 | Scribbles | Network flow I Network flow: II, Network flow III, IV. | |
| Tue 11/16 | 23 | Scribbles | Network flow applications | |
| Thu 11/18 | 24 | Slides |
Network flow, duality and
Linear Programming
More on linear programming |
|
| 11/20-28 Say thanks, go on vacation | ||||
| Tue 11/30 | 25 | scribbles | Approximation algorithms via LP. | |
| Thu 12/2 | 26 | scribbles | Directed MST | |
| Tue 12/7 | 27 | scribbles. | Fair divisions | |
| 12/15/2021, Wednesday 1:30 PM-4:30 PM 1404 SC |
FINAL | |||