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.

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

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

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