Sep 15, 2009
Sep 7, 2009
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, Spring 2007, Fall 2008, and Spring 2009. These notes are numbered roughly in the order I used them in my undergraduate class, with (lettered) notes containing sprinkled in reasonable places. More advanced material is indicated by the symbol ※. More information about these notes is available after the notes themselves.
August 2009 revision
A large collection of old homeworks and exams follows the lecture notes. Most of these homework and exam problems also appear at the ends of the appropriate 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, Alina Ene, Amir Nayyeri, Asha Seetharam, Ben Moseley, Brian Ensink, Chris Neihengen, Dan Bullok, Dan Cranston, Johnathon Fischer, Ekta Manaktala, Erin Wolf Chambers, Igor Gammer, Gio Kao, Kevin Milans, Kevin Small, Lan Chen, Michael Bond, Mitch Harris, Nick Hurlburt, Nitish Korula, Reza Zamani-Nasab, Rishi Talreja, Rob McCann, Shripad Thite, and Yasu Furakawa.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! (Because I don't always follow my own advice, some of the problems are buggy, especially in older homeworks and exams. I've tried to keep the buggy problems out of the lecture notes themselves.)
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–2009 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://
This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States 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 in one file (765 pages)
- Cover material (6 pages)
- All lecture notes in one file (379 pages)
- All homework, head-banging, and exam problems in one file (386 pages)
|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)|
- 0. Introduction, history, and course goals
- Amortized analysis
- String algorithms
- Basic graph algorithms
- Flows and cuts
- Linear programming
- Lower bounds
- Retired: These notes contain material that I have not covered in several years, and that I do not expect to cover in the future.
|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, and Head-Banging Sessions
- Johnny's algorithms homework (Fall 2000 HW 1)
- Spring 1999: everything
- Fall 2000: everything
- Spring 2001: everything
- Fall 2002: everything
- Spring 2004: everything
- Fall 2005: everything
- Fall 2006: everything
- Spring 2007: everything
- Fall 2008: everything
- Spring 2009: everything
Caveat Lector. Some of these lecture notes have been used less often than others and are therefore (sometimes considerably) less complete/
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. 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.