These are class notes and book notes for Algorithms, Design and Analysis (CSE 202) taught during Fall 2002 by Professor Impagliazzo. If you read these notes and find technical ambiguities, errors, or points that are just not clear, please let me know so that I can change them for other people. These documents are in PDF format, but the LaTeX is also available if you'd rather make postscript files.
Lecture date | Description | Links | Last Updated |
---|---|---|---|
Sep 26, 2002 | Introduction to the class | PDF | LaTeX | 09/26/2002 02:58pm |
Oct 1, 2002 | Divide and Conquer; the Closest Pair of Points | PDF | LaTeX | 10/02/2002 06:33pm |
Oct 3, 2002 | Linear time median, randomized algorithms | PDF | LaTeX | 10/08/2002 02:45pm |
Oct 8, 2002 | Multiplication of big integers | PDF | LaTeX | 10/08/2002 02:56pm |
Oct 10, 2002 | The FFT (simple case, discrete) | PDF | LaTeX | 10/17/2005 05:41pm |
Oct 22, 2002 | Independent Set | PDF | LaTeX | 10/25/2002 11:33am |
Oct 24, 2002 | Graph 3-coloring, backtracking | PDF | LaTeX | 10/25/2002 11:33am |
Oct 29, 2002 | Dynamic Programming: Counting Cards, and Binomial Coefficients. | PDF | LaTeX | 11/14/2002 06:16pm |
Oct 31, 2002 | Dynamic Programming: Belman-Ford / Floyd-Warshall APSP | PDF | LaTeX | 11/14/2002 05:52pm |
Nov 5, 2002 | Greedy Algorithms, Job Scheduling. | PDF | LaTeX | 11/14/2002 06:03pm |
Nov 7, 2002 | Greedy Algorithms, MTS lemma, Dijkstra. | PDF | LaTeX | 11/14/2002 06:28pm |
Nov 12, 2002 | Dijkstra's APSP algorithm improved with data structures (short). | PDF | LaTeX | 11/14/2002 06:38pm |
Nov 14, 2002 | Data structures improving Kruskal's MST Algorithm. | PDF | LaTeX | 11/14/2002 06:48pm |
Nov 19, 2002 | Network flows. | PDF | LaTeX | 12/03/2002 05:32pm |
Nov 21, 2002 | Problem reductions, bipartite matching. | PDF | LaTeX | 12/09/2002 12:54pm |
Lecture date | Content | ETA |
---|---|---|
Oct 15, 2002 | Precision for the FFT. | Honestly, probably not this year |
Oct 17, 2002 | Comparison models. | Honestly, probably not this year |
Nov 27, 2002 | Reductions/job scheduling (partition). | Not sure. |
Dec 3, 2002 | PTAS for job scheduling (partition). | Not sure. |