Algorithms

Jeff Erickson
 th edition (pre-publication draft) — December ,
Ωth edition (pre-publication draft) — April ,
st paperback edition — June ,

� — ��

ISBN: -- - - (paperback)

© Copyright Jeff Erickson

cb
This work is available under a Creative Commons Attribution . International License.
For license details, see http://creativecommons.org/licenses/by/ . /.

Download this book at http://jeffe.cs.illinois.edu/teaching/algorithms/

or http://algorithms.wtf
or https://archive.org/details/Algorithms-Jeff-Erickson
Please report errors at https://github.com/jeffgerickson/algorithms

Portions of our programming are mechanically reproduced,

and we now begin our broadcast day.
For Kim, Kay, and Hannah
with love and admiration

And for Erin

with thanks
for breaking her promise
Incipit prologus in libro alghoarismi de practica arismetrice.
— Ioannis Hispalensis [John of Seville?],
Liber algorismi de pratica arismetrice (c.����)

Shall I tell you, my friend, how you will come to understand it?
Go and write a book upon it.
— Henry Home, Lord Kames (�6�6–��8�),
in a letter to Sir Gilbert Elliot

The individual is always mistaken. He designed many things, and drew in other
persons as coadjutors, quarrelled with some or all, blundered much, and
something is done; all are a little advanced, but the individual is always mistaken.
It turns out somewhat new and very unlike what he promised himself.
— Ralph Waldo Emerson, “Experience”, Essays, Second Series (�8��)

What I have outlined above is the content of a book the realization of whose basic
plan and the incorporation of whose details would perhaps be impossible; what I
have written is a second or third draft of a preliminary version of this book
— Michael Spivak, preface of the �rst edition of
Differential Geometry, Volume I (����)

Preface

About This Book

This textbook grew out of a collection of lecture notes that I wrote for various
algorithms classes at the University of Illinois at Urbana-Champaign, which I
have been teaching about once a year since January . Spurred by changes
of our undergraduate theory curriculum, I undertook a major revision of my
notes in ; this book consists of a subset of my revised notes on the most
fundamental course material, mostly reflecting the algorithmic content of our
new required junior-level theory course.

Prerequisites
The algorithms classes I teach at Illinois have two significant prerequisites:
a course on discrete mathematics and a course on fundamental data structures.
Consequently, this textbook is probably not suitable for most students as a first

i
P������

course in data structures and algorithms. In particular, I assume at least passing

familiarity with the following specific topics:

• Discrete mathematics: High-school algebra, logarithm identities, naive

set theory, Boolean algebra, first-order predicate logic, sets, functions,
equivalences, partial orders, modular arithmetic, recursive definitions, trees
(as abstract objects, not data structures), graphs (vertices and edges, not
function plots).
• Proof techniques: direct, indirect, contradiction, exhaustive case analysis,
and induction (especially “strong” and “structural” induction). Chapter
uses induction, and whenever Chapter n 1 uses induction, so does Chapter n.
• Iterative programming concepts: variables, conditionals, loops, records,
indirection (addresses/pointers/references), subroutines, recursion. I do not
assume fluency in any particular programming language, but I do assume
experience with at least one language that supports both indirection and
recursion.
• Fundamental abstract data types: scalars, sequences, vectors, sets, stacks,
queues, maps/dictionaries, ordered maps/dictionaries, priority queues.
• Fundamental data structures: arrays, linked lists (single and double,
linear and circular), binary search trees, at least one form of balanced binary
search tree (such as AVL trees, red-black trees, treaps, skip lists, or splay
trees), hash tables, binary heaps, and most importantly, the difference
between this list and the previous list.
• Fundamental computational problems: elementary arithmetic, sorting,
searching, enumeration, tree traversal (preorder, inorder, postorder, level-
order, and so on).
• Fundamental algorithms: elementary algorism, sequential search, binary
search, sorting (selection, insertion, merge, heap, quick, radix, and so
on), breadth- and depth-first search in (at least binary) trees, and most
importantly, the difference between this list and the previous list.
• Elementary algorithm analysis: Asymptotic notation (o, O, ⇥, ⌦, !),
translating loops into sums and recursive calls into recurrences, evaluating
simple sums and recurrences.
• Mathematical maturity: facility with abstraction, formal (especially recur-
sive) definitions, and (especially inductive) proofs; writing and following
mathematical arguments; recognizing and avoiding syntactic, semantic,
and/or logical nonsense.

The book briefly covers some of this prerequisite material when it arises in
context, but more as a reminder than a good introduction. For a more thorough
overview, I strongly recommend the following freely available references:

ii
 Additional References

• Margaret M. Fleck. Building Blocks for Theoretical Computer Science. Version

. (January ) or later available from http://mfleck.cs.illinois.edu/
building-blocks/.
• Eric Lehman, F. Thomson Leighton, and Albert R. Meyer. Mathematics for
Computer Science. June revision available from https://courses.csail.
mit.edu/ . /spring /. (I strongly recommend searching for the most
recent revision.)
• Pat Morin. Open Data Structures. Edition . G (January ) or later
available from http://opendatastructures.org/.
• Don Sheehy. A Course in Data Structures and Object-Oriented Design. Feb-
ruary or later revision available from https://donsheehy.github.io/
datastructures/.

Additional References
Please do not restrict yourself to this or any other single reference. Authors and
readers bring their own perspectives to any intellectual material; no instructor
“clicks” with every student, or even with every very strong student. Finding the
author that most effectively gets their intuition into your head takes some effort,
but that effort pays off handsomely in the long run.
The following references have been particularly valuable sources of intuition,
examples, exercises, and inspiration; this is not meant to be a complete list.
• Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The Design and
Analysis of Computer Algorithms. Addison-Wesley, . (I used this textbook
as an undergraduate at Rice and again as a masters student at UC Irvine.)
• Boaz Barak. Introduction to Theoretical Computer Science. Textbook draft,
most recently revised June . (Not your grandfather’s theoretical CS
textbook, and so much the better for it; the fact that it’s free is a delightful
bonus.)
• Thomas Cormen, Charles Leiserson, Ron Rivest, and Cliff Stein. Introduction
to Algorithms, third edition. MIT Press/McGraw-Hill, . (I used the first
edition as a teaching assistant at Berkeley.)
• Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh V. Vazirani. Algo-
rithms. McGraw-Hill, . (Probably the closest in content to this book,
but considerably less verbose.)
• Jeff Edmonds. How to Think about Algorithms. Cambridge University Press,
.
• Michael R. Garey and David S. Johnson. Computers and Intractability:
A Guide to the Theory of NP-Completeness. W. H. Freeman, .

iii
P������

• Michael T. Goodrich and Roberto Tamassia. Algorithm Design: Foundations,

Analysis, and Internet Examples. John Wiley & Sons, .
• Jon Kleinberg and Éva Tardos. Algorithm Design. Addison-Wesley, .
Borrow it from the library if you can.
• Donald Knuth. The Art of Computer Programming, volumes – A. Addison-
Wesley, and . (My parents gave me the first three volumes for
Christmas when I was . Alas, I didn’t actually read them until much later.)
• Udi Manber. Introduction to Algorithms: A Creative Approach. Addison-
Wesley, . (I used this textbook as a teaching assistant at Berkeley.)
• Ian Parberry. Problems on Algorithms. Prentice-Hall, (out of print).
Downloadable from https://larc.unt.edu/ian/books/free/license.html after
you agree to make a small charitable donation. Please honor your agreement.
• Robert Sedgewick and Kevin Wayne. Algorithms. Addison-Wesley, .
• Robert Endre Tarjan. Data Structures and Network Algorithms. SIAM, .
• Class notes from my own algorithms classes at Berkeley, especially those
taught by Dick Karp and Raimund Seidel.
• Lecture notes, slides, homeworks, exams, video lectures, research papers,
blog posts, StackExchange questions and answers, podcasts, and full-fledged
MOOCs made freely available on the web by innumerable colleagues around
the world.

About the Exercises

Each chapter ends with several exercises, most of which I have used at least
once in a homework assignment, discussion/lab section, or exam. The exercises
are not ordered by increasing difficulty, but (generally) clustered by common
techniques or themes. Some problems are annotated with symbols as follows:
• ™Red hearts indicate particularly challenging problems; many of these have
appeared on qualifying exams for PhD students at Illinois. A small number
of really hard problems are marked with ™large hearts.
• ©Blue diamonds indicate problems that require familiarity with material
from later chapters, but thematically belong where they are. Problems that
require familiarity with earlier material are not marked, however; the book,
like life, is cumulative.
• ®
Green clubs indicate problems that require familiarity with material out-
side the scope of this book, such as finite-state machines, linear algebra,
probability, or planar graphs. These are rare.
• ´Black spades indicate problems that require a significant amount of grunt
work and/or coding. These are rare.

iv
 Steal This Book!

∆
• Orange stars indicate that you are eating Lucky Charms that were manu-
factured before . Ew.
These exercises are designed as opportunities to practice, not as targets for their
own sake. The goal of each problem is not to solve that specific problem, but to
exercise a certain set of skills, or to practice solving a certain type of problem.
Partly for this reason, I don’t provide solutions to the exercises; the solutions are
not the point. In particular, there is no “instructor’s manual”; if you can’t solve a
problem yourself, you probably shouldn’t assign it to your students. That said,
you can probably find solutions to whatever homework problems I’ve assigned
this semester on the web page of whatever course I’m teaching. And nothing is
stopping you from writing an instructor’s manual!

Steal This Book!

This book is published under a Creative Commons Licence that allows you to
use, redistribute, adapt, and remix its contents without my permission, as long
as you point back to the original source. A complete electronic version of this
book is freely available at any of the following locations:
• The book web site: http://jeffe.cs.illinois.edu/teaching/algorithms/
• The mnemonic shortcut: http://algorithms.wtf
• The bug-report site: https://github.com/jeffgerickson/algorithms
• The Internet Archive: https://archive.org/details/Algorithms-Jeff-Erickson
The book web site also contains several hundred pages of additional lecture
notes on related and more advanced material, as well as a near-complete
archive of past homeworks, exams, discussion/lab problems, and other teaching
resources. Whenever I teach an algorithms class, I revise, update, and sometimes
cull my teaching materials, so you may find more recent revisions on the web
page of whatever course I am currently teaching.
Whether you are a student or an instructor, you are more than welcome to use
any subset of this textbook or my other lecture notes in your own classes, without
asking my permission—that’s why I put them on the web! However, please also
cite this book, either by name or with a link back to http://algorithms.wtf; this
is especially important if you are a student, and you use my course materials to
help with your homework. (Please also check with your instructor.)
However, if you are an instructor, I strongly encourage you to supplement
these with additional material that you write yourself. Writing the material
yourself will strengthen your mastery and in-class presentation of the material,
which will in turn improve your students’ mastery of the material. It will also
get you past the frustration of dealing with the parts of this book that you don’t
like. All textbooks are crap imperfect, and this one is no exception.

v
P������

Finally, please make whatever you write freely, easily, and globally avail-
able on the open web—not hidden behind the gates of a learning management
system or some other type of paywall—so that students and instructors else-
where can benefit from your unique insights. In particular, if you develop useful
resources that directly complement this textbook, such as slides, videos, or
solution manuals, please let me know so that I can add links to your resources
from the book web site.

Acknowledgments
This textbook draws heavily on the contributions of countless algorithms students,
teachers, and researchers. In particular, I am immensely grateful to more than
three thousand Illinois students who have used my lecture notes as a primary
reference, offered useful (if sometimes painful) criticism, and suffered through
some truly awful early drafts. Thanks also to many colleagues and students
around the world who have used these notes in their own classes and have sent
helpful feedback and bug reports.
I am particularly grateful for the feedback and contributions (especially
exercises) from my amazing teaching assistants:
Aditya Ramani, Akash Gautam, Alex Steiger, Alina Ene, Amir Nayyeri,
Asha Seetharam, Ashish Vulimiri, Ben Moseley, Brad Sturt, Brian Ensink,
Chao Xu, Charlie Carlson, Chris Neihengen, Connor Clark, Dan Bullok,
Dan Cranston, Daniel Khashabi, David Morrison, Ekta Manaktala, Erin
Wolf Chambers, Gail Steitz, Gio Kao, Grant Czajkowski, Hsien-Chih Chang,
Igor Gammer, Jacob Laurel, John Lee, Johnathon Fischer, Junqing Deng,
Kent Quanrud, Kevin Milans, Kevin Small, Konstantinos Koiliaris, Kyle Fox,
Kyle Jao, Lan Chen, Mark Idleman, Michael Bond, Mitch Harris, Naveen
Arivazhagen, Nick Bachmair, Nick Hurlburt, Nirman Kumar, Nitish Korula,
Patrick Lin, Phillip Shih, Rachit Agarwal, Reza Zamani-Nasab, Rishi Talreja,
Rob McCann, Sahand Mozaffari, Shalan Naqvi, Shripad Thite, Spencer
Gordon, Srihita Vatsavaya, Subhro Roy, Tana Wattanawaroon, Umang
Mathur, Vipul Goyal, Yasu Furakawa, and Yipu Wang.

I’ve also been helped tremendously by many discussions with faculty col-
leagues at Illinois: Alexandra Kolla, Cinda Heeren, Edgar Ramos, Herbert
Edelsbrunner, Jason Zych, Kim Whittlesey, Lenny Pitt, Madhu Parasarathy,
Mahesh Viswanathan, Margaret Fleck, Shang-Hua Teng, Steve LaValle, and
especially Chandra Chekuri, Ed Reingold, and Sariel Har-Peled.
Of course this book owes a great debt to the people who taught me this
algorithms stuff in the first place: Bob Bixby and Michael Pearlman at Rice;
David Eppstein, Dan Hirschberg, and George Lueker at Irvine; and Abhiram
Ranade, Dick Karp, Manuel Blum, Mike Luby, and Raimund Seidel at Berkeley.

vi
 Caveat Lector!

I stole the first iteration of the overall course structure, and the idea to write
up my own lecture notes in the first place, from Herbert Edelsbrunner; the idea
of turning a subset of my notes into a book from Steve LaValle; and several
components of the book design from Robert Ghrist.

Caveat Lector!
Of course, none of those people should be blamed for any flaws in the resulting
book. Despite many rounds of revision and editing, this book contains several
mistakes, bugs, gaffes, omissions, snafus, kludges, typos, mathos, grammaros,
thinkos, brain farts, poor design decisions, historical inaccuracies, anachronisms,
inconsistencies, exaggerations, dithering, blather, distortions, oversimplifications,
redundancy, logorrhea, nonsense, garbage, cruft, junk, and outright lies, all of
which are entirely Steve Skiena’s fault.
I maintain an issue tracker at https://github.com/jeffgerickson/algorithms,
where readers like you can submit bug reports, feature requests, and general
feedback on the book. Please let me know if you find an error of any kind,
whether mathematical, grammatical, historical, typographical, cultural, or
otherwise, whether in the main text, in the exercises, or in my other course
materials. (Steve is unlikely to care.) Of course, all other feedback is also
welcome!
Enjoy!

— Jeff

It is traditional for the author to magnanimously accept the blame for whatever
de�ciencies remain. I don’t. Any errors, de�ciencies, or problems in this book are
somebody else’s fault, but I would appreciate knowing about them so as to
determine who is to blame.
— Steven S. Skiena, The Algorithm Design Manual (����)

No doubt this statement will be followed by an annotated list of all textbooks,

and why each one is crap.
— Adam Contini, MetaFilter, January �, ����

vii
 Table of Contents

Preface i
About This Book . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
Prerequisites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
Additional References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
About the Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
Steal This Book! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi
Caveat Lector! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii

Table of Contents ix

� Introduction �
. What is an algorithm? . . . . . . . . . . . . . . . . . . . . . . . . . .
. Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ix
T���� �� C�������

Lattice Multiplication • Duplation and Mediation • Compass and Straight-

edge
. Congressional Apportionment . . . . . . . . . . . . . . . . . . . . .
. A Bad Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. Describing Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . .
Specifying the Problem • Describing the Algorithm
. Analyzing Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . .
Correctness • Running Time
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

� Recursion ��
. Reductions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. Simplify and Delegate . . . . . . . . . . . . . . . . . . . . . . . . . .
. Tower of Hanoi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. Mergesort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Correctness • Analysis
. Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Correctness • Analysis
. The Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. Recursion Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
™Ignoring Floors and Ceilings Is Okay, Honest
. Linear-Time Selection . . . . . . . . . . . . . . . . .
™
. . . . . . . . .
Quickselect • Good pivots • Analysis • Sanity Checking
. Fast Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. Exponentiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

� Backtracking ��
. N Queens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. Game Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. Subset Sum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Correctness • Analysis • Variants
. The General Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . .
. Text Segmentation (Interpunctio Verborum) . . . . . . . . . . . . .
Index Formulation • ™Analysis • Variants
. Longest Increasing Subsequence . . . . . . . . . . . . . . . . . . . .
. Longest Increasing Subsequence, Take . . . . . . . . . . . . . . .
. Optimal Binary Search Trees . . . . . . . . . . . . . . . . . . . . . .
™Analysis

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

� Dynamic Programming ��

x
 Table of Contents

. Mātrāvr.tta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Backtracking Can Be Slow • Memo(r)ization: Remember Everything • Dy-
namic Programming: Fill Deliberately • Don’t Remember Everything After
All
. ™
Aside: Even Faster Fibonacci Numbers . . . . . . . . . . . . . . .
Whoa! Not so fast!
. Interpunctio Verborum Redux . . . . . . . . . . . . . . . . . . . . . .
. The Pattern: Smart Recursion . . . . . . . . . . . . . . . . . . . . .
. Warning: Greed is Stupid . . . . . . . . . . . . . . . . . . . . . . . .
. Longest Increasing Subsequence . . . . . . . . . . . . . . . . . . . .
First Recurrence: Is This Next? • Second Recurrence: What’s Next?
. Edit Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Recursive Structure • Recurrence • Dynamic Programming
. Subset Sum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. Optimal Binary Search Trees . . . . . . . . . . . . . . . . . . . . . .
. Dynamic Programming on Trees . . . . . . . . . . . . . . . . . . . .
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

� Greedy Algorithms ���

. Storing Files on Tape . . . . . . . . . . . . . . . . . . . . . . . . . . .
. Scheduling Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. General Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. Huffman Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. Stable Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Some Bad Ideas • The Boston Pool and Gale-Shapley Algorithms • Running
Time • Correctness • Optimality!
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

� Basic Graph Algorithms ���

. Introduction and History . . . . . . . . . . . . . . . . . . . . . . . .
. Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. Representations and Examples . . . . . . . . . . . . . . . . . . . . .
. Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Adjacency Lists • Adjacency Matrices • Comparison
. Whatever-First Search . . . . . . . . . . . . . . . . . . . . . . . . . .
Analysis
. Important Variants . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Stack: Depth-First • Queue: Breadth-First • Priority Queue: Best-
First • Disconnected Graphs • Directed Graphs
. Graph Reductions: Flood Fill . . . . . . . . . . . . . . . . . . . . . .
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

xi
T���� �� C�������

� Depth-First Search ���

. Preorder and Postorder . . . . . . . . . . . . . . . . . . . . . . . . .
Classifying Vertices and Edges
. Detecting Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. Topological Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Implicit Topological Sort
. Memoization and Dynamic Programming . . . . . . . . . . . . . .
Dynamic Programming in Dags
. Strong Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . .
. Strong Components in Linear Time . . . . . . . . . . . . . . . . . .
Kosaraju and Sharir’s Algorithm • ™Tarjan’s Algorithm
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

� Minimum Spanning Trees ���

. Distinct Edge Weights . . . . . . . . . . . . . . . . . . . . . . . . . .
. The Only Minimum Spanning Tree Algorithm . . . . . . . . . . .
. Bor vka’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . .
This is the MST Algorithm You Want
. Jarník’s (“Prim’s”) Algorithm . . . . . . . . . . . . . . . . . . . . . .
™Improving Jarník’s Algorithm
. Kruskal’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

� Shortest Paths ���

. Shortest Path Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. ™
Negative Edges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. The Only SSSP Algorithm . . . . . . . . . . . . . . . . . . . . . . . .
. Unweighted Graphs: Breadth-First Search . . . . . . . . . . . . . .
. Directed Acyclic Graphs: Depth-First Search . . . . . . . . . . . .
. Best-First: Dijkstra’s Algorithm . . . . . . . . . . . . . . . . . . . . .
No Negative Edges • ™Negative Edges
. Relax ALL the Edges: Bellman-Ford . . . . . . . . . . . . . . . . . .
Moore’s Improvement • Dynamic Programming Formulation
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

� All-Pairs Shortest Paths ���

. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. Lots of Single Sources . . . . . . . . . . . . . . . . . . . . . . . . . .
. Reweighting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. Johnson’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . .
. Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . . . .
. Divide and Conquer . . . . . . . . . . . . . . . . . . . . . . . . . . .

xii
 Table of Contents

. Funny Matrix Multiplication . . . . . . . . . . . . . . . . . . . . . .

. (Kleene-Roy-)Floyd-Warshall(-Ingerman) . . . . . . . . . . . . . .
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

�� Maximum Flows & Minimum Cuts ���

. Flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. Cuts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. The Maxflow-Mincut Theorem . . . . . . . . . . . . . . . . . . . . .
. Ford and Fulkerson’s augmenting-path algorithm . . . . . . . . .
™Irrational Capacities
. Combining and Decomposing Flows . . . . . . . . . . . . . . . . .
. Edmonds and Karp’s Algorithms . . . . . . . . . . . . . . . . . . . .
Fattest Augmenting Paths • Shortest Augmenting Paths
. Further Progress . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

�� Applications of Flows and Cuts ���

. Edge-Disjoint Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. Vertex Capacities and Vertex-Disjoint Paths . . . . . . . . . . . . .
. Bipartite Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. Tuple Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Exam Scheduling
. Disjoint-Path Covers . . . . . . . . . . . . . . . . . . . . . . . . . . .
Minimal Faculty Hiring
. Baseball Elimination . . . . . . . . . . . . . . . . . . . . . . . . . . .
. Project Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

�� NP-Hardness ���
. A Game You Can’t Win . . . . . . . . . . . . . . . . . . . . . . . . . .
. P versus NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. NP-hard, NP-easy, and NP-complete . . . . . . . . . . . . . . . . . .
. ™Formal Definitions (HC SVNT DRACONES) . . . . . . . . . . . . .
. Reductions and S . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. S (from C S ). . . . . . . . . . . . . . . . . . . . . . . . .
. Maximum Independent Set (from S ) . . . . . . . . . . . . . . .
. The General Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . .
. Clique and Vertex Cover (from Independent Set) . . . . . . . . .
. Graph Coloring (from S ) . . . . . . . . . . . . . . . . . . . . . .
. Hamiltonian Cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . .
From Vertex Cover • From S • Variants and Extensions
. Subset Sum (from Vertex Cover) . . . . . . . . . . . . . . . . . . . .

xiii
T���� �� C�������

Caveat Reductor!
. Other Useful NP-hard Problems . . . . . . . . . . . . . . . . . . . .
. Choosing the Right Problem . . . . . . . . . . . . . . . . . . . . . .
. A Frivolous Real-World Example . . . . . . . . . . . . . . . . . . . .
. ™
On Beyond Zebra . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Polynomial Space • Exponential Time • Excelsior!
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Index ���

Index of People ���

Index of Pseudocode ���

Image Credits ���

Colophon ���

xiv