CSE 202 Notes page

[ 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.

Bugs

The old version of the FFT notes from Oct 8 were very weird. I had trouble following them (and I wrote the document), so I suggest getting the new notes on the FFT.
I am not sure when I'll be done with the notes from the parallel algorithms paper. Please let me know if this causes problems for you.
The notes for November 14 are both out of order and not very detailed. As time permits I'll fix the detail problem, but I'm sure you can overlook the fact that the MST problem wasn't actually introduced on Nov 14 but is presented that way in the notes.
If, for some wacky reason, you decide to download the latex source code, beware of files that have illustrations. I use MetaPost, so it's not necessarily easy to compile the document. If you must have PostScript and you can't compile the notes, please let me know and I'll do it for you.
The notes for 11/21 will not be available until tomorrow, Dec 6, due to certain content issues. If you already downloaded and/or printed those notes, I ask that you delete or toss them, and redownload and/or reprint them tomorrow.

Other Resources

Here are some great notes about Kruskal's and Prim's algorithms for MST. (This is from the other 202 section.)

Available notes

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

Not yet done

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.

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