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 mnenomic shortcut http://algorithms.wtf. Specifically:

The textbook Algorithms is licensed under a Creative Commons Attribution 4.0 International license.
All other lecture notes are licensed under a more restrictive Attribution-NonCommercial-ShareAlike 4.0 International license.

Please do not ask me for solutions to the exercises. Even if you are instructor, I will say no.

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.

Get the Book

Entire book (0th edition, December 2018, 448 pages)
- one page per page (for screens)
- two pages per page (for printing)
- GitHub (bug tracking)
- Internet Archive (permanent archival copy)
Individual chapters: These files are typeset separately, so page numbers (and possibly other minor typographic details) are inconsistent with the book, and hyperlinks to other chapters don't work.
1. Preface (8 pages)
2. Introduction (20 pages)
3. Recursion (48 pages)
4. Backtracking (26 pages)
5. Dynamic Programming (62 pages)
6. Greedy Algorithms (28 pages)
7. Basic Graph Algorithms (38 pages)
8. Depth-First Search (32 pages)
9. Minimum Spanning Trees (16 pages)
10. Shortest Paths (35 pages)
11. All-Pairs Shortest Paths (18 pages)
12. Maximum Flows & Minimum Cuts (26 pages)
13. Applications of Flows and Cuts (26 pages)
14. NP-Hardness (50 pages)

Related 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.

Extended Dance Remix: These are notes on more advanced material directly related to the textbook. The notes are ordered roughly to match the textbook chapters.
1. Fast Fourier Transforms (17 pages)
2. Fast Exponential Algorithms (14 pages)
3. Dynamic Programming for Formal Languages and Automata (7 pages, unfinished)
4. Advanced Dynamic Programming (18 pages)
5. Matroids (8 pages)
6. Balances and Pseudoflows (13 pages)
7. Minimum-Cost Flows (16 pages)
8. Linear Programming (21 pages)
9. Linear Programming Algorithms (18 pages)
10. Approximation Algorithms (25 pages)
Director's Cut: These are notes on topics not covered in the textbook. The numbering is completely independent to the textbook; I just started over at 1. We regularly cover some of the randomized algorithms material in CS 473, but I haven't used the amortized analysis or lower bounds notes in many years.
1. Discrete Probability (22 pages)
2. Nuts and Bolts (13 pages)
3. Treaps and Skip Lists (14 pages)
4. Tail Inequalities (10 pages)
5. Hashing (19 pages)
6. Filtering and Streaming (6 pages)
7. String Matching (14 pages)
8. Randomized Minimum Cut (7 pages)
9. Amortized Analysis (14 pages)
10. Scapegoat and Splay Trees (15 pages)
11. Disjoint Sets (14 pages)
12. Lower Bounds (6 pages)
13. Adversary Arguments (8 pages)
- Appendix I. Proof by Induction (30 pages)
- Appendix II. Solving Recurrences (22 pages)

Models of Computation

These notes cover (a superset of) the material on automata and formal language that appears in CS 374. Some of these notes are quite a bit more polished than others.

Everything (155 pages)
Individual notes:
1. Cover and preface (3 pages)
2. Strings (17 pages)
3. Regular languages (12 pages)
4. Finite-state automata (24 pages)
5. Nondeterministic automata (21 pages)
6. Context-free languages (20 pages)
7. Turing machings (20 pages)
8. Undecidability (20 pages)
9. Universal models (8 pages, unfinished)
10. Nondeterministic Turing machines (6 pages, unfinished)

Jeff Erickson — 30 Dec 2018