| Tue 8/25 | 1: slides/h/n | NP Completeness I |
| Thu 8/27 | 2: slides/h/n | NP Completeness II |
| Tue 9/1 | 3: slides/h/n | NP Completeness III |
| Thu 9/3 | 4: slides/h/n | See above class notes. |
| Tue 9/8 | 5: slides/h/n | See above class notes. |
| Thu 9/10 | 6: slides/h/n |
Dynamic Programming
|
| Tue 9/15 | 7: slides/h/n | Even MORE Dynamic Programming |
| Thu 9/17 | 8: slides/h/n | Approximation algorithms |
| Tue 9/22 | 9: slides/h/n | Approximation algorithms II |
| Thu 9/24 | 10: slides/h/n | Approximation algorithms III |
| Tue 9/29 | Midterm I: 5-6:50pm, Siebel 1404 | |
| Thu 10/1 | 11: slides/ h/ n | Randomized Algorithms I |
| Tue 10/6 | 12: slides/ h/ n | RA II: QuickSort: high probability/Chernoff's inequality |
| Thu 10/8 | 13: slides/ h/ n | RA III: Backward analysis |
| Tue 10/13 | 14: slides/ h/ n | RA IV: Mincut |
| Thu 10/15 | 15: slides/ h/ n | Union find |
| Fri 10/16 | Drop deadline for undergrads | |
| Tue 10/20 | 16: slides/ h/ n | Matchings |
| Thu 10/22 | 17: slides/ h/ n | Matchings II - bipartite weighted and non-bipartite |
| Tue 10/27 | 18: slides/ h/ n | Linear programming |
| Thu 10/29 | 19: slides/ h/ n | LP II |
| Tue 11/3 |
Midterm 2:
5-6:50pm, Siebel 1404 A collection of some review questions. |
|
| Thu 11/5 | 20: slides/ h/ n | LP III |
| Tue 11/10 | 21: slides/ h/ n | |
| Thu 11/12 | 22: slides/ h/ n | Lower bounds |
| Fri 11/13 | --- | Drop deadline for graduate students |
| Tue 11/17 | 23: slides/ h/ n | Fast Fourier Transform |
| Thu 11/19 | 24: slides/ h/ n | Sorting Network |
| Tue 11/24 | Thanksgiving Vacation | |
| Thu 11/26 | Thanksgiving Vacation | |
| Tue 12/1 | 25: slides/ h/ n |
Huffman's compression
(a mild introduction to
what is information) |
| Thu 12/3 | 26: slides/ h/ n |
Entropy II: Extracting randomness |
| Tue 12/8 | 27: slides/ h/ n |
Entropy III: More on
extracting ranodmness
Shannon's theorem Max cut |
| Tue 12/10 | Reading Day | |
| Fri 12/11 | Proof | Final:
8:00 AM- 11:00 AM, Location: 1BUR 124.
|