Algorithms

by Jeff Erickson

0th edition (prepublication draft), December 2018

This web page contains a free electronic version of my (soon to be) self-published textbook Algorithms, along with other lecture notes I have written for various theoretical computer science classes at the University of Illinois, Urbana-Champaign since 1998.


More Information

Publication. As you might guess from the typesetting, I am planning to self-publish a paper version of this book in the near future. Except for the missing index (and a few minor typesetting issues), the electronic copy is a “final” prepublication draft. Everything will remain freely available here after publication.

Bug reports. After years of trying and failing to manage bug reports by email, I now maintain an issue-tracking page at GitHub. If you find an error in the textbook, in the lecture notes, or in any other materials, please submit a bug report. All other feedback is welcome as well.

Permissions. Anyone is welcome to download, print, use, copy, and/or distribute anything on this page, either electronically or on paper. You do not need to ask my permission, although I would appreciate hearing from you if you find this material useful. If you redistribute any of this material, please include a link back to this web page, either directly or through the mnemomic shortcut http://algorithms.wtf. Specifically:

Please do not ask me for solutions to the exercises. See the course materials page for an explanation.

Context. You can see all this material in context at the websites of my most recent courses: CS 374 (Spring 2018) and CS 473 (Spring 2017). I maintain a complete archive of past homeworks, exams, and lab handouts on a separate page.

Prerequisites. The textbook assumes knowledge of discrete math (especially induction) and basic data structures and algorithms (especially recursion) consistent with the prerequisite courses CS 173 and CS 225 at Illinois. (See the Preface for more details.) For a thorough overview of prerequisite material, I strongly recommend the following resources:


Get the Book


More Algorithms Lecture Notes

Both the topical coverage (except for flows) and the level of difficulty of the textbook material (mostly) reflect the algorithmic content of CS 374. The remainder of these notes cover either more advanced aspects of topics from the book, or other topics that appear only in our more advanced algorithms class CS 473. Don't be fooled by the fancy typesetting; these notes are considerably less polished than the textbook.

Models of Computation

These notes cover (a superset of) the automata and formal languages material in CS 374. Some of these notes are a lot more polished than others.
If were not a little mad and generally silly
I should give you my advice upon the subject, willy-nilly;
I should show you in a moment how to grapple with the question,
And you'd really be astonished at the force of my suggestion.
On the subject I shall write you a most valuable letter,
Full of excellent suggestions when I feel a little better,
But at present I'm afraid I am as mad as any hatter,
So I'll keep 'em to myself, for my opinion doesn't matter!
—J. S. Gilbert and Arthur Sullivan, "My Eyes are Fully Open", Ruddigore; or, The Witch's Curse (1887)
It is time we did away with “publish or perish” and replace it with “publish and perish.”
Nothing will be more blasphemous than writing a textbook that anyone can go out and buy.
Daniel J. Woodhouse, “An Open Letter to the Mathematical Community”, McSweeny’s (January 15, 2019)

Jeff Erickson — 30 Dec 2018