473U: Algorithms

Lecture notes

1. 1/18/05 - Introduction.
2. 1/20/05 - reductions.
3. 1/25/05 - divide and conquer.
4. 1/27/05 - FFT.
5. 2/01/05 - dynamic programming.
6. 2/03/05 - dynamic programming II.
7. 2/08/05 - Greeedy algorithms (Jeff Erickson class notes).
8. 2/10/05 - NP Completeness
9. 2/15/05 - NP Completeness II
10. 2/17/05 - NP Completeness III
11. 2/24/05 - Approx alg I
12. 3/01/05 - Approx alg II
13. 3/03/05 - Approx. Alg. III
14. 3/08/05 - Sorting networks
15. 3/10/05 - Rand Alg - Nuts and Bolts V. Kumar lecture version
16. 3/15/05 - Routing on the hypercube
17. 3/17/05 - Minimum cut in a graph
18. 3/29/05 - Network flow I
19. 3/31/05 - Network flow II
20. 4/5/05 - Network flow III - applications.
21. 4/7/05 - Network flow IV - applications II (slides).
22. 4/14/05 - Union-find.
23. 4/19/05 - Triangulations - Computatioanl Geometry
24. 4/21/05 - Triangulations II - CG.
25. 4/26/05 - convex hull - CG
26. 4/28/05 - Lower bounds
27. 5/3/05 - Linear programming in two dimensions

Some lecture slides

1. Network flow III - applications
2. Network flow IV - applications II
3. Polygon partitions and triangulations
4. Linear programming in two dimensions