Algorithms

Algorithms are the lifeblood of computer science. They are the machines that proofs build and the music that programs play. Their history is as old as mathematics itself. This textbook is a wide-ranging, idiosyncratic treatise on the design and analysis of algorithms, covering several fundamental techniques, with an emphasis on intuition and the problem-solving process. The book includes important classical examples, hundreds of battle-tested exercises, far too many historical digressions, and exactly four typos. Jeff Erickson is a computer science professor at the University of Illinois, Urbana-Champaign; this book is based on algorithms classes he has taught there since 1998.

Table of Contents

1. Introduction
2. Recursion
3. Backtracking
4. Dynamic Programming
5. Greedy Algorithms
6. Basic Graph Algorithms
7. Depth-First Search
8. Minimum Spanning Trees
9. Shortest Paths
10. All-Pairs Shortest Paths
11. Maximum Flows & Minimum Cuts
12. Applications of Flows and Cuts
13. NP-Hardness

About the Author

Jeff Erickson is a professor of computer science at the University of Illinois at Urbana-Champaign, where he has been a faculty member since 1998. His research interests lie at the intersection of algorithm design and discrete mathematics, especially for problems involving geometry, topology, graphs, and optimization.

Jeff’s father used to keep an “electric hammer” in his office. It was a regular hammer with a battery, an LED, and a toggle switch that he’d built into the handle. Whenever someone would ask how it worked, he would flip the switch, turning the LED on, and say “There. Now it’s on.”