## Course Schedule, Lecture Notes, Homeworks, and Exams

Please let me know if you find major bugs in the lecture notes.

I will gladly email homework and exam solutions to interestedinstructors.

## Administrivia

Instructor:- Jeff Erickson (jeffe@cs.uiuc.edu), 2113 DCL
Teaching assistants:- Mitch Harris (maharri@cs.uiuc.edu), 1216 DCL

Shripad Thite (thite@cs.uiuc.edu), 1216 DCL

Prerequisites:- Students are assumed to have working knowledge of the material taught in CS 225 and CS 273. (This is
notthe same as merely having passed.) If you're an undergraduate and you haven't taken those classes, you need my permission to enroll.

Coursework:- Grades will be based on 6-8 homeworks (30%) (dropping the lowest), two in-class midterms (20% each), and a final exam (30%). Graduate students taking the class for a full unit will have extra work: extra homework and exam problems, a semester project, or both. There will be three different grade scales: undergraduates, 3/4-unit graduates, and 1-unit graduates. Undergraduates interested in honors credit should contact the instructor.

Topics:

Design and analysis techniques:divide and conquer, dynamic programming, randomization, amortizationAdvanced data structures:universal hashing, splay trees, treaps, Fibonacci heaps, union/findGraph algorithms:representations, minimum spanning trees, shortest pathsGeometric algorithms:convex hulls, plane sweep, polygon triangulation, Bézier curvesLower bounds:decision trees, adversaries, reductions, NP-hardness, approximation algorithms

Textbooks:

[CLR]- Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, Introduction to Algorithms, MIT Press/McGrawHill, 1990.
Required.

- Frequently asked questions
- Errata (Caveat lector!)

[Par]- Ian Parberry, Problems on Algorithms, PrenticeHall, 1995.
Recommended, especially for students who want or need practice with prerequisite material.

- Errata (Caveat lector!)

Some useful web pages and other handouts: