## Algorithms

## by Jeff Erickson

December 2013 revisionThis page contains lecture notes for the undergraduate and graduate algorithms classes I have taught at the University of Illinois, Urbana-Champaign. The notes are numbered roughly in the order I use them in undergraduate algorithms classes. More advanced material is indicated by the symbol ♥. Each lecture note includes several exercises; a near-complete archive of my old homeworks, exams, and discussion problems follows the lecture notes on this page.

Please do not ask me for solutions to the exercises.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 shouldn't assign problems that you can't solve yourself! (Because I don't always follow my own advice, I sometimes assign buggy problems, but I’ve tried to keep these out of the lecture notes themselves.)More information about this material is available at the bottom of this page. Many other recommended algorithms resources, both online and off, including course materials, videos, MOOCs, and even a few dead-tree textbooks, are listed on a separate page.

Feedback is always welcome, especially bug reports. I would particularly appreciate hearing from anyone outside UIUC who finds this stuff useful (or useless)!

Algorithmsby Jeff Erickson is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International 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(983 pages)

- Cover material (7 pages)
- All lecture notes in one file (451 pages)
- All homework, head-banging, and exam problems in one file (532 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
RecursionRandomization

- 9. Nuts and bolts (randomized quicksort)
- 10. Treaps and skip lists
- 11. Tail inequalities ♥
- 12. Hashing
- 13. String matching
- 14. Randomized minimum cut
Amortization

- 15. Aggregation, taxation, potential
- 16. Scapegoat trees and splay trees
- 17. Maintaining disjoint sets ("union-find") — includes O(α(n)) amortized analysis ♥
Basic graph algorithmsCombinatorial optimizationLower 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
- Fall 2012 (undergraduate):
- Fall 2013 (undergraduate):

Knowledge is of two kinds.

We know a subject ourselves,

or we know where we can find information upon it.— Samuel Johnson (April 18, 1775)

quoted by James Boswell, The Life of Samuel Johnson, LL.D. (1791)## More Information

Copyright.Except as indicated otherwise, all material linked from this web page is Copyright © 1999–2013 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 reproduction or distribution. For example, you are welcome to maintain 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 link to this web page (http://www.cs.uiuc.edu/ . If you're a lawyer, read the legalese.~jeffe/ teaching/ algorithms)

Teaching assistants.I am deeply indebted to my fantastic teaching assistants, without whom running effective courses would be utterly impossible. In particular, these TAs contributed a significant fraction of the homework and discussion problems.Aditya Ramani, Akash Gautam, Alina Ene, Amir Nayyeri, Asha Seetharam, Ashish Vulimiri, Ben Moseley, Brian Ensink, Chris Neihengen, Dan Bullok, Dan Cranston, Daniel Khashabi, David Morrison, Johnathon Fischer, Ekta Manaktala, Erin Wolf Chambers, Hsien-Chih Chang, Igor Gammer, Gio Kao, Kent Quanrud, Kevin Milans, Kevin Small, Kyle Fox, Kyle Jao, Lan Chen, Michael Bond, Mitch Harris, Nick Hurlburt, Nirman Kumar, Nitish Korula, Rachit Agarwal, Reza Zamani-Nasab, Rishi Talreja, Rob McCann, Shripad Thite, Subhro Roy, and Yasu Furakawa.

Figure credits.The picture of the Spirit of Arithmetic from Margarita Philosophica at the end of the introductory notes was copied from Wikimedia Commons; the original 1508 woodcut is in the public domain. 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. Several of Randall Munroe's xkcd comic strips are reproduced under a Creative Commons License. One well-known frame from Allie Brosh's comic strip Hyperbole and a Half appears in two of these noteswithoutexplicit permission. Johnny's algorithm homework was submitted by an anonymous student. I drew all other figures in the notes myself, mostly using OmniGraffle, but some earlier figures using (shudder) xfig.

Previous versions.The 2009 and 2011 editions of this material are still available; these include a few "retired" notes on material I have not taught for several years. More recent revisions are probably available on the official web site of whatever algorithms course I'm teaching this semester. Some day I will join the 20th century and use a real source-control repository.

Caveat Lector.Some of these lecture notes have been used less often than others and are therefore (sometimesconsiderably) less complete/polished. I offer extra credit to my own students for finding bugs in the notes, and I strongly encourage anyone else using them to do the same. Also, each of these notes contains significantly 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 graduate students than to undergraduates. I realize this makes the description "lecture notes" rather inaccurate.Please send me bug reports.

Am I writing a textbook?No. All textbooks suck. (That's partly due to the~~rapacious~~~~unethical~~profitable business practices of (most) textbook publishers. But also, I'veneverseen a textbook onanytopic that I've been willing to teach from for more than a few weeks; that's why I wrote these notes in the first place.) 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. At some point, I may realize (or admit to myself) that these notes already suck enough to be a textbook, at which point I may slap a cover on them and sell some cheap dead-tree copies. But they'llalwaysbe freely available here.

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

Jeff Erickson — 28 Dec 2013