| Date |
Topics |
Video |
| Thu 8/29 |
0. administrivia and introduction |
Video
|
| Tue 9/3 |
1. divide and conquer |
Video
|
| Thu 9/5 |
2. dynamic programming |
Video
|
| Tue 9/10 |
3. more dynamic programming |
Video
|
| Thu 9/12 |
4. randomization |
Video
|
| Tue 9/17 |
5. treaps and skip lists: Jeff Spring 2001 |
56K
100K
|
| |
5. treaps : Sariel Fall 2001 |
56K
100K
|
| Thu 9/19 |
6. randomized minimum cut |
Video
|
| Tue 9/24 |
7. uniform and universal hashing |
Video
|
| Thu 9/26 |
8. "Cuckoo hashing" |
Video
|
| Tue 10/1 |
In-Class Midterm 1 |
|
| Thu 10/3 |
9. amortized analysis |
Video
|
| Tue 10/8 |
10. scapegoat trees |
Video
|
| Thu 10/10 |
11. splay trees and union-find |
Video
|
| Tue 10/15 |
12. union-find analysis |
Video
|
| Thu 10/17 |
13. representing and searching graphs |
Video
|
| Tue 10/22 |
14. single-source shortest paths |
Video
|
| Thu 10/24 |
15. all-pairs shortest paths |
Video
|
| Tue 10/29 |
16. minimum spanning trees |
Video
|
| Thu 10/31 |
17. fast randomized MST |
Video
|
| Tue 11/5 |
In-Class Midterm 2 |
|
| Thu 11/7 |
18. fast Fourier transforms |
Video
|
| Tue 11/12 |
19. basic number theory |
Video
|
| Thu 11/14 |
20. primality testing |
Video
|
| Tue 11/19 |
21. RSA encryption[Guest lecturer] |
Video
|
| Thu 11/21 |
22. "Primes is in P" |
Video
|
| Tue 11/26 |
Thanksgiving Vacation |
|
| Thu 11/28 |
Thanksgiving Vacation |
|
| Tue 12/3 |
23. NP-hard, NP-easy, and NP-complete |
Video
|
| Thu 12/5 |
24. More NP-complete problems |
Video
|
| Tue 12/10 |
25. approximation algorithms |
Video
|
| Thu 12/12 |
26. final review session |
Video
|