| Date | # | Scribbles | Notes | Slides | |||||
|---|---|---|---|---|---|---|---|---|---|
| Week 1 | |||||||||
| Tue 8/22 | 1 | Scribbles | Divide & conquer [wiki] | ||||||
| Thu 8/24 | 2 | Scribbles | FFT [wiki] | ||||||
| Week 2 | |||||||||
| Tue 8/29 | 3 | Scribbles | D&C, FFT: More divide & conquer (Karatsuba's algorithm, Strassen algorithm. Closest pair, string matching with don't cares. | ||||||
| Thu 8/31 | 4 | Scribbles | Sorting networks | ||||||
| Week 3 | |||||||||
| Monday 9/4 | Labor day: Vacation day | ||||||||
| Tue 9/5 | 5 | Scribbles | Dynamic Programming, | ||||||
| Thu 9/7 | 6 | Scribbles | Even MORE Dynamic Programming | ||||||
| Week 4 | |||||||||
| Tue 9/12 | 7 | scribbles: |
Advanced dynamic programming I:
(1) Faster BST via monotonicity,
(2) Finding minimum in each row if matrix is monotone.
(3) Edit distance -- using linear space, and still
recovering the solution.
(4) Modifying BST to support max-y queries.
Some stuff is taken from Jeff's class notes. |
||||||
| Thu 9/14 | 8 | scribbles | Last lecture on dynamic programming. | ||||||
| Week 5 | |||||||||
| Tue 9/19 | 9 | Scribbles | Fixed parameter tractable algorithmstd>a>. | ||||||
| Thu 9/21 | 10 | Scribbles |
Randomized Algorithms I
Some probability, nuts and bolts, neat analysis of quick sort. |
||||||
| Week 6 | |||||||||
| Tue 9/26 | 11 | scribbles |
QuickSort: high probability
Markov inequality, Max cut 2 approx, Conditional expectation, QuickSort with high probability via conditional expectation.. Mentioned treaps. |
||||||
| Thu 9/28 | Midterm 1: 7-9pm, Loomis 151. | ||||||||
| Week 7 | |||||||||
| Tue 10/3 | 12 | Scribbles | Chebychev inequality and Mincut. | ||||||
| Thu 10/5 | 13 | Scribbles | Mincut | ||||||
| Week 8 | |||||||||
| Tue 10/10 | 14 | scribbles |
hashing |
||||||
| Thu 10/12 | 15 | scribbles |
Backward analysis |
||||||
| Week 9 | |||||||||
| Tue 10/17 | 16 | scribbles | Closest pair in expected linear time (see Section 11.3 in here. | ||||||
| Thu 10/19 | 17 | Scribbles | Approximation algorithms | ||||||
| Week 10 | |||||||||
| Tue 10/24 | 18 | Scribbles | Approximation algorithms II | ||||||
| Thu 10/26 | 19 | Scribbles | Approximation algorithms III TSP, Max SAT, clustering | ||||||
| Week 11 | |||||||||
| Tue 10/31 | 20 | See notes | Linear programming | ||||||
| Thu 11/2 | 21 | See notes | Linear programming II: Duality | ||||||
| Week 12 | |||||||||
| Thu 11/7 | 22 | Scribbles | Approximation algorithms via LP. | ||||||
| Thu 11/9 | Midterm 2: 7-9pm, Loomis 151. | ||||||||
| Week 13 | |||||||||
| Tue 11/14 | 23 | Scribbles |
NP Completeness I
NP Completeness II NP Completeness III |
||||||
| Thu 11/16 | 24 | Scribbles |
NPC II
|
||||||
| 11/18-26 Say thanks, go on vacation | |||||||||
| Week 14 | |||||||||
| Tue 11/28 | 25 | scribbles | NPC III | ||||||
| Thu 11/30 | 26 | scribbles | NPC IV | ||||||
| Week 15 | |||||||||
| Tue 12/5 | 27 | scribbles. | Directed MST | ||||||
| Wed 12/6 | LAST DAY OF Instruction | ||||||||
| 12/12/2023, ??? 7:00-10PM, 2079 Natural History Building | FINAL
proof. |
||||||||