Algorithms Course Materials

by Jeff Erickson

This page contains all my lecture notes for the algorithms classes required for all computer science undergraduate and graduate students at the University of Illinois, Urbana-Champaign. I have taught incarnations of this course eight times: Spring 1999, Fall 2000, Spring 2001, Fall 2002, Spring 2004, Fall 2005, Fall 2006, and Spring 2007. These notes are numbered in the order I used them in Fall 2006, with (lettered) notes from other semesters sprinkled in reasonable places. More information about these notes is available after the notes themselves.

A large collection of old homeworks and exams follows the lecture notes. Except for various Homework Zeros, which are solely my fault, most of the homework problems were written by my teaching assistants:

Aditya Ramani, Asha Seetharam, Brian Ensink, Chris Neihengen, Dan Bullok, Dan Cranston, John Fischer, Ekta Manaktala, Erin Wolf Chambers, Igor Gammer, Gio Kao, Kevin Milans, Kevin Small, Lan Chen, Michael Bond, Mitch Harris, Nick Hurlburt, Nitish Korula, Rishi Talreja, Rob McCann, Shripad Thite, and Yasu Furakawa.
I plan to incorporate most of these problems into the appropriate lecture notes during the next revision cycle; a few notes already have problems at the end. Please do not ask me for solutions. If you're a student, you will (usually) learn more from trying to solve a problem and failing than by reading the answer. If you really need help, ask your instructor, your TAs, and/or your fellow students. If you're an instructor, you really shouldn't assign problems that you can't solve yourself! (Since I don't always follow my own advice, some of the problems are buggy.)

More recent version of these notes, along with current homework and exams, may be available at the official sites for the undergraduate and graduate algorithms classes at UIUC.

Feedback of any kind is always welcome, especially bug reports. I would particularly appreciate hearing from anyone outside UIUC who finds these notes useful (or useless)!

Copyright. Except as indicated otherwise, all material linked from this web page is Copyright © 1999–2006 Jeff Erickson. Anyone may freely download, print, copy, and/or distribute anything on this page, either electronically or on paper. However, nothing on this page may be sold in any form for more than the actual cost of printing and/or reproduction. For example, you are welcome to make local copies on your own web server, but you are not allowed to require an access fee (such as tuition) to view your local copy; that's the same as selling it. If you distribute these notes, please give me proper credit and please include a pointer to this web page (http://www.cs.uiuc.edu/~jeffe/teaching/algorithms). If you're a lawyer, read the legalese.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 2.5 License.

You know, I could write a book.
And this book would be thick enough to stun an ox.
— Laurie Anderson, "Let X=X", Big Science (1982)

Everything

If we are ready to tolerate everything as understood, there is nothing left to explain; while if we sourly refuse to take anything, even tentatively, as clear, no explanation can be given. What intrigues us as a problem, and what will satisfy us as a solution, will depend upon the line we draw between what is already clear and what needs to be clarified.
— Nelson Goodman, Fact, Fiction & Forecast (1955)

Lecture Notes

The problem is that we attempt to solve the simplest questions cleverly, thereby rendering them unusually complex.
One should seek the simple solution.
— Anton Pavlovich Chekhov (c. 1890)

Homeworks, Exams, etc.

More Information

Caveat Lector. Some of these lecture notes have been used less often than others and are therefore (sometimes considerably) less complete/polished. Almost all of these notes contain more than one lecture's worth of material. In a typical 75-minute lecture, I tend to cover 4-5 pages of material—a bit more if I'm lecturing to grad students than to undergraduates. Your mileage may vary! (Arguably, that means that as I continue to add material, the label "lecture notes" becomes less and less accurate.)

Alternate sources. My UIUC colleague Sariel Har-Peled maintains his own collection of algorithms lecture notes, which heavily overlap mine, although our presentation styles and specific topical choices are different, sometimes radically so. Choice is good! For people who really prefer dead trees, I recommend the textbooks by Dasgupta, Papadimitriou, and Vazirani; by Kleinberg and Tardos; and (especially for stunning oxen) by Cormen, Leiserson, Rivest, and Stein. An increasing amount of basic algorithmic material can be found at the Source of All Lies. Many more references are listed in the cover material for the lecture notes.

Drawing tools. Most of the figures were drawn with OmniGraffle, but a few very old figures were drawn with xfig, and a few particularly complex figures were drawn with either Freehand or Illustrator. Some figures in the recurrences notes were "drawn" using pstricks-enabled latex code, but that's not my fault. The map on the first page of the maxflow/mincut notes was copied from Lex Schrijver's excellent survey "On the history of combinatorial optimization (till 1960)"; the original map is from a US Government work in the public domain.

Am I writing a textbook? No. All textbooks suck. (Partly that's because of the unethical rapacious profitable business practices of (most) textbook publishers—these notes will always be freely available. But also, I've never seen a textbook on any topic that I'd be willing to teach from for more than a few weeks; that's why I wrote these notes in the first place.) In particular, if these notes ever became a textbook, they would immediately suck. (Determining whether they already suck is an illuminating exercise for the reader.) Besides, have you ever talked to someone who's actually written a textbook? Do you realize how much work is involved?! No way, man. Not for me.

Jeff Erickson — 11 Jan 2007