## 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, Spring 2009, Spring 2010, and Fall 2010. These notes are numbered roughly in the order I use them in my undergraduate class. More advanced material is indicated by the symbol ♥. More information about these notes is available after the notes themselves.

January 2011 revisionA 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, David Morrison, Johnathon Fischer, Ekta Manaktala, Erin Wolf Chambers, Igor Gammer, Gio Kao, Kevin Milans, Kevin Small, Kyle Fox, Lan Chen, Michael Bond, Mitch Harris, Nick Hurlburt, Nitish Korula, Rachit Agarwal, 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.)The previous edition of this material, which includes notes on material I have not taught for several years, including string algorithms and computational geometry. More recent version of these notes, along with current homework and exams, may be available at the official sites for the undergraduate and/or 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–2011 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 besoldin 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/ . If you're a lawyer, read the legalese.~jeffe/ teaching/ algorithms)

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

Everything in one file(814 pages)

- Cover material (6 pages)
- All lecture notes in one file (374 pages)
- All homework, head-banging, and exam problems in one file (440 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) ## Lecture Notes

- 0. Introduction, history, and course goals
RecursionRandomizationAmortized analysis

- 14. Aggregation, taxation, potential
- 15. Scapegoat trees and splay trees
- 16. Maintaining disjoint sets ("union-find") — includes O(α(n)) amortized analysis ♥
Basic graph algorithmsFlows and cutsLinear programming

- 25. Definitions and duality ♥
- 26. The simplex algorithm ♥
Lower boundsAppendix

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 (mixed): everything
- Fall 2000 (mixed): everything
- Spring 2001 (mixed): everything
- Fall 2002 (mixed): everything
- Spring 2004 (undergraduate): everything
- Fall 2005 (graduate): everything
- Fall 2006 (undergraduate): everything
- Spring 2007 (graduate): everything
- Fall 2008 (graduate): everything
- Spring 2009 (undergraduate): everything
- Spring 2010 (undergraduate): everything
- Fall 2010 (graduate): everything

## More Information

Caveat Lector.Some of these lecture notes have been used less often than others and are therefore (sometimesconsiderably) 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! Algorithms course materials are also available from several other universities, including MIT (Spring 2008; Fall 2005, with video and alternate notes), CMU (Fall 2008; Spring 2010), and the University of Washington. (This is an embarrassingly incomplete list!) Finally, as a review of important mathematical prerequisites, I strongly recommend Eric Lehman and Tom Leighton's extensive lecture notes for the Mathematics for Computer Science course at MIT. An increasing amount of basic algorithmic material can also be found at the Source of All Lies.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. Many more dead-tree 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 willalwaysbe freely available. But also, I've never seen a textbook onanytopic 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 theyalreadysuck is an illuminating exercise for the reader.) Besides, have you ever talked to someone who's actually written a textbook? Do you realize how muchworkis involved?! No way, man. Not for me.

No doubt this statement will be followed by an annotated list of all textbooks, and why each one is crap.— shmegegge, MetaFilter, January 4, 2010

Jeff Erickson — 19 Jan 2011