[ Course home page | The other 202 home page ]

CSE 202 Class Notes

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.


Other Resources

Available notes

Lecture date Description Links Last Updated
Sep 26, 2002Introduction to the classPDF | LaTeX09/26/2002 02:58pm
Oct 1, 2002Divide and Conquer; the Closest Pair of PointsPDF | LaTeX10/02/2002 06:33pm
Oct 3, 2002Linear time median, randomized algorithmsPDF | LaTeX10/08/2002 02:45pm
Oct 8, 2002Multiplication of big integersPDF | LaTeX10/08/2002 02:56pm
Oct 10, 2002The FFT (simple case, discrete)PDF | LaTeX10/17/2005 05:41pm
Oct 22, 2002Independent SetPDF | LaTeX10/25/2002 11:33am
Oct 24, 2002Graph 3-coloring, backtrackingPDF | LaTeX10/25/2002 11:33am
Oct 29, 2002Dynamic Programming: Counting Cards, and Binomial Coefficients.PDF | LaTeX11/14/2002 06:16pm
Oct 31, 2002Dynamic Programming: Belman-Ford / Floyd-Warshall APSPPDF | LaTeX11/14/2002 05:52pm
Nov 5, 2002Greedy Algorithms, Job Scheduling.PDF | LaTeX11/14/2002 06:03pm
Nov 7, 2002Greedy Algorithms, MTS lemma, Dijkstra.PDF | LaTeX11/14/2002 06:28pm
Nov 12, 2002Dijkstra's APSP algorithm improved with data structures (short).PDF | LaTeX11/14/2002 06:38pm
Nov 14, 2002Data structures improving Kruskal's MST Algorithm.PDF | LaTeX11/14/2002 06:48pm
Nov 19, 2002Network flows.PDF | LaTeX12/03/2002 05:32pm
Nov 21, 2002Problem reductions, bipartite matching.PDF | LaTeX12/09/2002 12:54pm

Not yet done

Lecture date Content ETA
Oct 15, 2002Precision for the FFT.Honestly, probably not this year
Oct 17, 2002Comparison models.Honestly, probably not this year
Nov 27, 2002Reductions/job scheduling (partition).Not sure.
Dec 3, 2002PTAS for job scheduling (partition).Not sure.

This page last modified on 12/05/2002 01:19pm PST by Neil Jones (ncjones at cs dot ucsd dot edu).