Algorithms

0th edition (pre-publication draft) — December 30, 2018

½th edition (pre-publication draft) — April 9, 2019
1st paperback edition — June 13, 2019

1 2 3 4 5 6 7 8 9 — 27 26 25 24 23 22 21 20 19

ISBN: 978-1-792-64483-2 (paperback)

© Copyright 2019 Jeff Erickson

cb
This work is available under a Creative Commons Attribution 4.0 International License.

Jeff Erickson For license details, see [Link]

Download this book at [Link]

or [Link]
or [Link]
Please report errors at [Link]

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
 PREFACE
Incipit prologus in libro alghoarismi de practica arismetrice.
— Ioannis Hispalensis [John of Seville?],
Liber algorismi de pratica arismetrice (c.1135) course in data structures and algorithms. In particular, I assume at least passing
Shall I tell you, my friend, how you will come to understand it?
familiarity with the following specific topics:
Go and write a book upon it.
• Discrete mathematics: High-school algebra, logarithm identities, naive
— Henry Home, Lord Kames (1696–1782),
in a letter to Sir Gilbert Elliot
set theory, Boolean algebra, first-order predicate logic, sets, functions,
equivalences, partial orders, modular arithmetic, recursive definitions, trees
The individual is always mistaken. He designed many things, and drew in other
persons as coadjutors, quarrelled with some or all, blundered much, and
(as abstract objects, not data structures), graphs (vertices and edges, not
something is done; all are a little advanced, but the individual is always mistaken. function plots).
It turns out somewhat new and very unlike what he promised himself. • Proof techniques: direct, indirect, contradiction, exhaustive case analysis,
— Ralph Waldo Emerson, “Experience”, Essays, Second Series (1844) and induction (especially “strong” and “structural” induction). Chapter 0
What I have outlined above is the content of a book the realization of whose basic uses induction, and whenever Chapter n−1 uses induction, so does Chapter n.
plan and the incorporation of whose details would perhaps be impossible; what I • Iterative programming concepts: variables, conditionals, loops, records,
have written is a second or third draft of a preliminary version of this book
indirection (addresses/pointers/references), subroutines, recursion. I do not
— Michael Spivak, preface of the first edition of
Differential Geometry, Volume I (1970)
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
Preface 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).
About This Book • Fundamental algorithms: elementary algorism, sequential search, binary
search, sorting (selection, insertion, merge, heap, quick, radix, and so
This textbook grew out of a collection of lecture notes that I wrote for various
on), breadth- and depth-first search in (at least binary) trees, and most
algorithms classes at the University of Illinois at Urbana-Champaign, which I
importantly, the difference between this list and the previous list.
have been teaching about once a year since January 1999. Spurred by changes
of our undergraduate theory curriculum, I undertook a major revision of my • Elementary algorithm analysis: Asymptotic notation (o, O, Θ, Ω, ω),
notes in 2016; this book consists of a subset of my revised notes on the most translating loops into sums and recursive calls into recurrences, evaluating
fundamental course material, mostly reflecting the algorithmic content of our simple sums and recurrences.
new required junior-level theory course. • Mathematical maturity: facility with abstraction, formal (especially recur-
sive) definitions, and (especially inductive) proofs; writing and following
mathematical arguments; recognizing and avoiding syntactic, semantic,
Prerequisites and/or logical nonsense.

The algorithms classes I teach at Illinois have two significant prerequisites: The book briefly covers some of this prerequisite material when it arises in
a course on discrete mathematics and a course on fundamental data structures. context, but more as a reminder than a good introduction. For a more thorough
Consequently, this textbook is probably not suitable for most students as a first overview, I strongly recommend the following freely available references:

i ii
 Additional References PREFACE

• Margaret M. Fleck. Building Blocks for Theoretical Computer Science. Version • Michael T. Goodrich and Roberto Tamassia. Algorithm Design: Foundations,
1.3 (January 2013) or later available from [Link] Analysis, and Internet Examples. John Wiley & Sons, 2002.
building-blocks/. • Jon Kleinberg and Éva Tardos. Algorithm Design. Addison-Wesley, 2005.
• Eric Lehman, F. Thomson Leighton, and Albert R. Meyer. Mathematics for Borrow it from the library if you can.
Computer Science. June 2018 revision available from [Link] • Donald Knuth. The Art of Computer Programming, volumes 1–4A. Addison-
[Link]/6.042/spring18/. (I strongly recommend searching for the most Wesley, 1997 and 2011. (My parents gave me the first three volumes for
recent revision.) Christmas when I was 14. Alas, I didn’t actually read them until much later.)
• Pat Morin. Open Data Structures. Edition 0.1Gβ (January 2016) or later • Udi Manber. Introduction to Algorithms: A Creative Approach. Addison-
available from [Link] Wesley, 1989. (I used this textbook as a teaching assistant at Berkeley.)
• Don Sheehy. A Course in Data Structures and Object-Oriented Design. Feb- • Ian Parberry. Problems on Algorithms. Prentice-Hall, 1995 (out of print).
ruary 2019 or later revision available from [Link] Downloadable from [Link] after
datastructures/. you agree to make a small charitable donation. Please honor your agreement.
• Robert Sedgewick and Kevin Wayne. Algorithms. Addison-Wesley, 2011.
• Robert Endre Tarjan. Data Structures and Network Algorithms. SIAM, 1983.
Additional References
• Class notes from my own algorithms classes at Berkeley, especially those
Please do not restrict yourself to this or any other single reference. Authors and taught by Dick Karp and Raimund Seidel.
readers bring their own perspectives to any intellectual material; no instructor • Lecture notes, slides, homeworks, exams, video lectures, research papers,
“clicks” with every student, or even with every very strong student. Finding the blog posts, StackExchange questions and answers, podcasts, and full-fledged
author that most effectively gets their intuition into your head takes some effort, MOOCs made freely available on the web by innumerable colleagues around
but that effort pays off handsomely in the long run. the world.
The following references have been particularly valuable sources of intuition,
examples, exercises, and inspiration; this is not meant to be a complete list. About the Exercises
• Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The Design and
Analysis of Computer Algorithms. Addison-Wesley, 1974. (I used this textbook Each chapter ends with several exercises, most of which I have used at least
as an undergraduate at Rice and again as a masters student at UC Irvine.) once in a homework assignment, discussion/lab section, or exam. The exercises
are not ordered by increasing difficulty, but (generally) clustered by common
• Boaz Barak. Introduction to Theoretical Computer Science. Textbook draft,
techniques or themes. Some problems are annotated with symbols as follows:
most recently revised June 2019. (Not your grandfather’s theoretical CS
textbook, and so much the better for it; the fact that it’s free is a delightful • ªRed hearts indicate particularly challenging problems; many of these have
bonus.) appeared on qualifying exams for PhD students at Illinois. A small number
of really hard problems are marked with ªlarge hearts.
• Thomas Cormen, Charles Leiserson, Ron Rivest, and Cliff Stein. Introduction
to Algorithms, third edition. MIT Press/McGraw-Hill, 2009. (I used the first • ©Blue diamonds indicate problems that require familiarity with material
edition as a teaching assistant at Berkeley.) from later chapters, but thematically belong where they are. Problems that
• Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh V. Vazirani. Algo- require familiarity with earlier material are not marked, however; the book,
rithms. McGraw-Hill, 2006. (Probably the closest in content to this book, like life, is cumulative.
but considerably less verbose.) ¨
• Green clubs indicate problems that require familiarity with material out-
• Jeff Edmonds. How to Think about Algorithms. Cambridge University Press, side the scope of this book, such as finite-state machines, linear algebra,
2008. probability, or planar graphs. These are rare.
• Michael R. Garey and David S. Johnson. Computers and Intractability: • «Black spades indicate problems that require a significant amount of grunt
A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. work and/or coding. These are rare.

iii iv
 Steal This Book! PREFACE

Æ
• Orange stars indicate that you are eating Lucky Charms that were manu- Finally, please make whatever you write freely, easily, and globally avail-
factured before 1998. Ew. able on the open web—not hidden behind the gates of a learning management
These exercises are designed as opportunities to practice, not as targets for their system or some other type of paywall—so that students and instructors else-
own sake. The goal of each problem is not to solve that specific problem, but to where can benefit from your unique insights. In particular, if you develop useful
exercise a certain set of skills, or to practice solving a certain type of problem. resources that directly complement this textbook, such as slides, videos, or
Partly for this reason, I don’t provide solutions to the exercises; the solutions are solution manuals, please let me know so that I can add links to your resources
not the point. In particular, there is no “instructor’s manual”; if you can’t solve a from the book web site.
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
Acknowledgments
stopping you from writing an instructor’s manual!
This textbook draws heavily on the contributions of countless algorithms students,
teachers, and researchers. In particular, I am immensely grateful to more than
Steal This Book! three thousand Illinois students who have used my lecture notes as a primary
reference, offered useful (if sometimes painful) criticism, and suffered through
This book is published under a Creative Commons Licence that allows you to some truly awful early drafts. Thanks also to many colleagues and students
use, redistribute, adapt, and remix its contents without my permission, as long around the world who have used these notes in their own classes and have sent
as you point back to the original source. A complete electronic version of this helpful feedback and bug reports.
book is freely available at any of the following locations: I am particularly grateful for the feedback and contributions (especially
• The book web site: [Link] exercises) from my amazing teaching assistants:
• The mnemonic shortcut: [Link] Aditya Ramani, Akash Gautam, Alex Steiger, Alina Ene, Amir Nayyeri,
• The bug-report site: [Link] Asha Seetharam, Ashish Vulimiri, Ben Moseley, Brad Sturt, Brian Ensink,
• The Internet Archive: [Link] Chao Xu, Charlie Carlson, Chris Neihengen, Connor Clark, Dan Bullok,
Dan Cranston, Daniel Khashabi, David Morrison, Ekta Manaktala, Erin
The book web site also contains several hundred pages of additional lecture Wolf Chambers, Gail Steitz, Gio Kao, Grant Czajkowski, Hsien-Chih Chang,
notes on related and more advanced material, as well as a near-complete Igor Gammer, Jacob Laurel, John Lee, Johnathon Fischer, Junqing Deng,
archive of past homeworks, exams, discussion/lab problems, and other teaching Kent Quanrud, Kevin Milans, Kevin Small, Konstantinos Koiliaris, Kyle Fox,
resources. Whenever I teach an algorithms class, I revise, update, and sometimes Kyle Jao, Lan Chen, Mark Idleman, Michael Bond, Mitch Harris, Naveen
cull my teaching materials, so you may find more recent revisions on the web Arivazhagen, Nick Bachmair, Nick Hurlburt, Nirman Kumar, Nitish Korula,
page of whatever course I am currently teaching. Patrick Lin, Phillip Shih, Rachit Agarwal, Reza Zamani-Nasab, Rishi Talreja,
Rob McCann, Sahand Mozaffari, Shalan Naqvi, Shripad Thite, Spencer
Whether you are a student or an instructor, you are more than welcome to use
Gordon, Srihita Vatsavaya, Subhro Roy, Tana Wattanawaroon, Umang
any subset of this textbook or my other lecture notes in your own classes, without Mathur, Vipul Goyal, Yasu Furakawa, and Yipu Wang.
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 [Link] this I’ve also been helped tremendously by many discussions with faculty col-
is especially important if you are a student, and you use my course materials to leagues at Illinois: Alexandra Kolla, Cinda Heeren, Edgar Ramos, Herbert
help with your homework. (Please also check with your instructor.) Edelsbrunner, Jason Zych, Kim Whittlesey, Lenny Pitt, Madhu Parasarathy,
However, if you are an instructor, I strongly encourage you to supplement Mahesh Viswanathan, Margaret Fleck, Shang-Hua Teng, Steve LaValle, and
these with additional material that you write yourself. Writing the material especially Chandra Chekuri, Ed Reingold, and Sariel Har-Peled.
yourself will strengthen your mastery and in-class presentation of the material, Of course this book owes a great debt to the people who taught me this
which will in turn improve your students’ mastery of the material. It will also algorithms stuff in the first place: Bob Bixby and Michael Pearlman at Rice;
get you past the frustration of dealing with the parts of this book that you don’t David Eppstein, Dan Hirschberg, and George Lueker at Irvine; and Abhiram
like. All textbooks are crap imperfect, and this one is no exception. Ranade, Dick Karp, Manuel Blum, Mike Luby, and Raimund Seidel at Berkeley.

v 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 [Link]
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
deficiencies remain. I don’t. Any errors, deficiencies, 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 (1997)

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

vii
 TABLE OF CONTENTS

Lattice Multiplication • Duplation and Mediation • Compass and Straight-

edge
0.3 Congressional Apportionment . . . . . . . . . . . . . . . . . . . . . 8
0.4 A Bad Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
0.5 Describing Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Specifying the Problem • Describing the Algorithm
0.6 Analyzing Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Correctness • Running Time
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

1 Recursion 21
1.1 Reductions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.2 Simplify and Delegate . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.3 Tower of Hanoi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.4 Mergesort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Correctness • Analysis
1.5 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Correctness • Analysis
1.6 The Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
1.7 Recursion Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
ªIgnoring Floors and Ceilings Is Okay, Honest
ª
1.8 Linear-Time Selection . . . . . . . . . . . . . . . . . . . . . . . . . . 35
Table of Contents Quickselect • Good pivots • Analysis • Sanity Checking
1.9 Fast Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
1.10 Exponentiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

Preface i 2 Backtracking 71
About This Book . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i 2.1 N Queens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
Prerequisites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i 2.2 Game Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
Additional References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii 2.3 Subset Sum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
Correctness • Analysis • Variants
About the Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
2.4 The General Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
Steal This Book! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
2.5 Text Segmentation (Interpunctio Verborum) . . . . . . . . . . . . . 80
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi
Index Formulation • ªAnalysis • Variants
Caveat Lector! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
2.6 Longest Increasing Subsequence . . . . . . . . . . . . . . . . . . . . 86
2.7 Longest Increasing Subsequence, Take 2 . . . . . . . . . . . . . . . 89
Table of Contents ix 2.8 Optimal Binary Search Trees . . . . . . . . . . . . . . . . . . . . . . 91
ªAnalysis
0 Introduction 1 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
0.1 What is an algorithm? . . . . . . . . . . . . . . . . . . . . . . . . . . 1
0.2 Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3 Dynamic Programming 97

ix x
 Table of Contents TABLE OF CONTENTS

3.1 Mātrā[Link] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 6 Depth-First Search 225

Backtracking Can Be Slow • Memo(r)ization: Remember Everything • Dy- 6.1 Preorder and Postorder . . . . . . . . . . . . . . . . . . . . . . . . . 227
namic Programming: Fill Deliberately • Don’t Remember Everything After Classifying Vertices and Edges
All 6.2 Detecting Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
ª 6.3 Topological Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
3.2 Aside: Even Faster Fibonacci Numbers . . . . . . . . . . . . . . . 103
Whoa! Not so fast! Implicit Topological Sort
3.3 Interpunctio Verborum Redux . . . . . . . . . . . . . . . . . . . . . . 105 6.4 Memoization and Dynamic Programming . . . . . . . . . . . . . . 234
3.4 The Pattern: Smart Recursion . . . . . . . . . . . . . . . . . . . . . 105 Dynamic Programming in Dags
3.5 Warning: Greed is Stupid . . . . . . . . . . . . . . . . . . . . . . . . 107 6.5 Strong Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
3.6 Longest Increasing Subsequence . . . . . . . . . . . . . . . . . . . . 109 6.6 Strong Components in Linear Time . . . . . . . . . . . . . . . . . . 238
First Recurrence: Is This Next? • Second Recurrence: What’s Next? Kosaraju and Sharir’s Algorithm • ªTarjan’s Algorithm
3.7 Edit Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
Recursive Structure • Recurrence • Dynamic Programming
3.8 Subset Sum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 7 Minimum Spanning Trees 257
7.1 Distinct Edge Weights . . . . . . . . . . . . . . . . . . . . . . . . . . 257
3.9 Optimal Binary Search Trees . . . . . . . . . . . . . . . . . . . . . . 117
7.2 The Only Minimum Spanning Tree Algorithm . . . . . . . . . . . 259
3.10 Dynamic Programming on Trees . . . . . . . . . . . . . . . . . . . . 120
7.3 Borůvka’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
This is the MST Algorithm You Want

4 Greedy Algorithms 159 7.4 Jarník’s (“Prim’s”) Algorithm . . . . . . . . . . . . . . . . . . . . . . 263

ªImproving Jarník’s Algorithm
4.1 Storing Files on Tape . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
7.5 Kruskal’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
4.2 Scheduling Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268
4.3 General Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
4.4 Huffman Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 8 Shortest Paths 273
4.5 Stable Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 8.1 Shortest Path Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
Some Bad Ideas • The Boston Pool and Gale-Shapley Algorithms • Running
8.2 ªNegative Edges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
Time • Correctness • Optimality!
8.3 The Only SSSP Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 276
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 8.4 Unweighted Graphs: Breadth-First Search . . . . . . . . . . . . . . 278
8.5 Directed Acyclic Graphs: Depth-First Search . . . . . . . . . . . . 282
5 Basic Graph Algorithms 187 8.6 Best-First: Dijkstra’s Algorithm . . . . . . . . . . . . . . . . . . . . . 284
5.1 Introduction and History . . . . . . . . . . . . . . . . . . . . . . . . 187 No Negative Edges • ªNegative Edges
5.2 Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 8.7 Relax ALL the Edges: Bellman-Ford . . . . . . . . . . . . . . . . . . 289
5.3 Representations and Examples . . . . . . . . . . . . . . . . . . . . . 192 Moore’s Improvement • Dynamic Programming Formulation
5.4 Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
Adjacency Lists • Adjacency Matrices • Comparison
5.5 Whatever-First Search . . . . . . . . . . . . . . . . . . . . . . . . . . 199 9 All-Pairs Shortest Paths 309
Analysis 9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
5.6 Important Variants . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 9.2 Lots of Single Sources . . . . . . . . . . . . . . . . . . . . . . . . . . 310
Stack: Depth-First • Queue: Breadth-First • Priority Queue: Best- 9.3 Reweighting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
First • Disconnected Graphs • Directed Graphs 9.4 Johnson’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 312
5.7 Graph Reductions: Flood Fill . . . . . . . . . . . . . . . . . . . . . . 205 9.5 Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . . . . 313
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 9.6 Divide and Conquer . . . . . . . . . . . . . . . . . . . . . . . . . . . 315

xi xii
 Table of Contents TABLE OF CONTENTS

9.7 Funny Matrix Multiplication . . . . . . . . . . . . . . . . . . . . . . 316 Caveat Reductor!

9.8 (Kleene-Roy-)Floyd-Warshall(-Ingerman) . . . . . . . . . . . . . . 318 12.13Other Useful NP-hard Problems . . . . . . . . . . . . . . . . . . . . 404
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320 12.14Choosing the Right Problem . . . . . . . . . . . . . . . . . . . . . . 407
12.15A Frivolous Real-World Example . . . . . . . . . . . . . . . . . . . . 408
10 Maximum Flows & Minimum Cuts 327 ª
12.16 On Beyond Zebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412
10.1 Flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328 Polynomial Space • Exponential Time • Excelsior!
10.2 Cuts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415
10.3 The Maxflow-Mincut Theorem . . . . . . . . . . . . . . . . . . . . . 331
10.4 Ford and Fulkerson’s augmenting-path algorithm . . . . . . . . . 334 Index 442
ªIrrational Capacities
10.5 Combining and Decomposing Flows . . . . . . . . . . . . . . . . . 336 Index of People 446
10.6 Edmonds and Karp’s Algorithms . . . . . . . . . . . . . . . . . . . . 340
Index of Pseudocode 449
Fattest Augmenting Paths • Shortest Augmenting Paths
10.7 Further Progress . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343 Image Credits 451
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344
Colophon 453
11 Applications of Flows and Cuts 353
11.1 Edge-Disjoint Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353
11.2 Vertex Capacities and Vertex-Disjoint Paths . . . . . . . . . . . . . 354
11.3 Bipartite Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355
11.4 Tuple Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357
Exam Scheduling
11.5 Disjoint-Path Covers . . . . . . . . . . . . . . . . . . . . . . . . . . . 360
Minimal Faculty Hiring
11.6 Baseball Elimination . . . . . . . . . . . . . . . . . . . . . . . . . . . 363
11.7 Project Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368

12 NP-Hardness 379
12.1 A Game You Can’t Win . . . . . . . . . . . . . . . . . . . . . . . . . . 379
12.2 P versus NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
12.3 NP-hard, NP-easy, and NP-complete . . . . . . . . . . . . . . . . . . 382
12.4 ªFormal Definitions (HC SVNT DRACONES) . . . . . . . . . . . . . 384
12.5 Reductions and Sat . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385
12.6 3Sat (from CircuitSat) . . . . . . . . . . . . . . . . . . . . . . . . . 388
12.7 Maximum Independent Set (from 3Sat) . . . . . . . . . . . . . . . 390
12.8 The General Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . . 392
12.9 Clique and Vertex Cover (from Independent Set) . . . . . . . . . 394
12.10 Graph Coloring (from 3Sat) . . . . . . . . . . . . . . . . . . . . . . 395
12.11 Hamiltonian Cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 398
From Vertex Cover • From 3Sat • Variants and Extensions
12.12 Subset Sum (from Vertex Cover) . . . . . . . . . . . . . . . . . . . . 402

xiii xiv
 0. INTRODUCTION
Hinc incipit algorismus. Haec algorismus ars praesens dicitur in qua
talibus indorum fruimur bis quinque figuris 0. 9. 8. 7. 6. 5. 4. 3. 2. 1.
— Friar Alexander de Villa Dei, Carmen de Algorismo (c. 1220) (ἄλγος), meaning “pain”. Rather, it is a corruption of the name of the 9th century
You are right to demand that an artist engage his work consciously, Persian scholar [Link] ibn Mūsā al-Khwārizmı̄.1 Al-Khwārizmı̄ is perhaps
but you confuse two different things: best known as the writer of the treatise Al-Kitāb [Link] fı̄hı̄sāb al-ğabr
solving the problem and correctly posing the question. wa’l-muqābala,2 from which the modern word algebra derives. In a different
— Anton Chekhov, in a letter to A. S. Suvorin (October 27, 1888) treatise, al-Khwārizmı̄ described the modern decimal system for writing and
The more we reduce ourselves to machines in the lower things, manipulating numbers—in particular, the use of a small circle or .sifr to represent
the more force we shall set free to use in the higher.
a missing quantity—which had been developed in India several centuries earlier.
— Anna C. Brackett, The Technique of Rest (1892)
The methods described in this latter treatise, using either written figures or
And here I am at 2:30 a.m. writing about technique, in spite of a strong conviction counting stones, became known in English as algorism or augrym, and its figures
that the moment a man begins to talk about technique that’s proof that he is fresh
became known in English as ciphers.
out of ideas.
— Raymond Chandler, letter to Erle Stanley Gardner (May 5, 1939) Although both place-value notation and al-Khwārizmı̄’s works were already
known by some European scholars, the “Hindu-Arabic” numeric system was
Good men don’t need rules.
Today is not the day to find out why I have so many, popularized in Europe by the medieval Italian mathematician and tradesman
— The Doctor [Matt Smith], “A Good Man Goes to War”, Doctor Who (2011) Leonardo of Pisa, better known as Fibonacci. Thanks in part to his 1202 book
Liber Abaci,3 written figures began to replace the counting table (then known as
an abacus) and finger arithmetic4 as the preferred platform for calculation5 in
Europe in the 13th century—not because written decimal figures were easier to

0 learn or use, but because they provided an audit trail. Ciphers became common
in Western Europe only with the advent of movable type, and truly ubiquitous
only after cheap paper became plentiful in the early 19th century.
Eventually the word algorism evolved into the modern algorithm, via folk
etymology from the Greek arithmos (and perhaps the previously mentioned
Introduction algos).6 Thus, until very recently, the word algorithm referred exclusively
1
“Mohammad, father of Adbdulla, son of Moses, the Kwārizmian”. Kwārizm is an ancient
city, now called Khiva, in the Khorezm Province of Uzbekistan.
2
“The Compendious Book on Calculation by Completion and Balancing”
3
0.1 What is an algorithm? While it is tempting to translate the title Liber Abaci as “The Book of the Abacus”, a more
accurate translation is “The Book of Calculation”. Both before and after Fibonacci, the Italian
An algorithm is an explicit, precise, unambiguous, mechanically-executable word abaco was used to describe anything related to numerical calculation—devices, methods,
schools, books, and so on—much in the same way that “computer science” is used today in
sequence of elementary instructions, usually intended to accomplish a specific English, or as the Chinese phrase for “operations research” translates literally as “the study of
purpose. For example, here is an algorithm for singing that annoying song “99 using counting rods”.
Bottles of Beer on the Wall”, for arbitrary values of 99: 4
+ Reckoning with digits! +
5
The word calculate derives from the Latin word calculus, meaning “small rock”, referring to
the stones on a counting table, or as Chaucer called them, augrym stones. In 440bce, Herodotus
BottlesOfBeer(n):
wrote in his Histories that “The Greeks write and calculate (λογίζεσθαι ψήφοις, literally ‘reckon
For i ← n down to 1 with pebbles’) from left to right; the Egyptians do the opposite. Yet they say that their way of
Sing “i bottles of beer on the wall, i bottles of beer,” writing is toward the right, and the Greek way toward the left.” (Herodotus is strangely silent on
Sing “Take one down, pass it around, i − 1 bottles of beer on the wall.” which end of the egg the Egyptians ate first.)
6
Sing “No bottles of beer on the wall, no bottles of beer,” Some medieval sources claim that the Greek prefix “algo-” means “art” or “introduction”.
Sing “Go to the store, buy some more, n bottles of beer on the wall.” Others claim that algorithms were invented by a Greek philosopher, or a king of India, or perhaps
a king of Spain, named “Algus” or “Algor” or “Argus”. A few, possibly including Dante Alighieri,
even identified the inventor with the mythological Greek shipbuilder and eponymous argonaut.
The word “algorithm” does not derive, as algorithmophobic classicists might It’s unclear whether any of these risible claims were intended to be historically accurate, or
guess, from the Greek roots arithmos (άριθμός), meaning “number”, and algos merely mnemonic.

1 2
 0.2. Multiplication 0. INTRODUCTION

to mechanical techniques for place-value arithmetic using “Arabic” numerals. input consists of a pair of arrays X [0 .. m − 1] and Y [0 .. n − 1], representing the
People trained in the fast and reliable execution of these procedures were called numbers
m−1 n−1
algorists or computators, or more simply, computers. X X
x= X [i] · 10i and y = Y [ j] · 10 j ,
i=0 j=0

0.2 Multiplication and similarly, the output consists of a single array Z[0 .. m + n − 1], representing
the product
Although they have been a topic of formal academic study for only a few decades, m+n−1
X
algorithms have been with us since the dawn of civilization. Descriptions of z=x·y= Z[k] · 10k .
step-by-step arithmetic computation are among the earliest examples of written k=0
human language, long predating the expositions by Fibonacci and al-Khwārizmı̄, The algorithm uses addition and single-digit multiplication as primitive opera-
or even the place-value notation they popularized. tions. Addition can be performed using a simple for-loop. In practice, single-digit
multiplication is performed using a lookup table, either carved into clay tablets,
Lattice Multiplication painted on strips of wood or bamboo, written on paper, stored in read-only
memory, or memorized by the computator. The entire lattice algorithm can be
The most familiar method for multiplying large numbers, at least for American summarized by the formula
students, is the lattice algorithm. This algorithm was popularized by Fibonacci
in Liber Abaci, who learned it from Arabic sources including al-Khwārizmı̄, who m−1
XX n−1


in turn learned it from Indian sources including Brahmagupta’s 7th-century x·y = X [i] · Y [ j] · 10i+ j .
i=0 j=0
treatise Brā[Link]̄nta, who may have learned it from Chinese sources.
The oldest surviving descriptions of the algorithm appear in The Mathematical Different variants of the lattice algorithm evaluate the partial products X [i] ·
Classic of Sunzi, written in China between the 3rd and 5th centuries, and in Y [ j] · 10i+ j in different orders and use different strategies for computing their
Eutocius of Ascalon’s commentaries on Archimedes’ Measurement of the Circle, sum. For example, in Liber Abaco, Fibonacci describes a variant that considers
written around 500ce, but there is evidence that the algorithm was known much the mn partial products in increasing order of significance, as shown in modern
earlier. Eutocius credits the method to a lost treatise of Apollonius of Perga, pseudocode below.
who lived around 300bce, entitled Okytokion (᾿Ωκυτόκιον).7 The Sumerians
recorded multiplication tables on clay tablets as early as 2600bce, suggesting FibonacciMultiply(X [0 .. m − 1], Y [0 .. n − 1]):
that they may have used the lattice algorithm.8 hold ← 0
The lattice algorithm assumes that the input numbers are represented as for k ← 0 to n + m − 1
explicit strings of digits; I’ll assume here that we’re working in base ten, but the for all i and j such that i + j = k
hold ← hold + X [i] · Y [ j]
algorithm generalizes immediately to any other base. To simplify notation,9 the
Z[k] ← hold mod 10
7
Literally “medicine that promotes quick and easy childbirth”! Pappus of Alexandria repro- hold ← bhold/10c
duced several excerpts of Okytokion about 200 years before Eutocius, but his description of the return Z[0 .. m + n − 1]
lattice multiplication algorithm (if he gave one) is also lost.
8
There is ample evidence that ancient Sumerians calculated accurately with extremely Fibonacci’s algorithm is often executed by storing all the partial products in a
large numbers using their base-60 place-value numerical system, but I am not aware of any
surviving record of the actual methods they used. In addition to standard multiplication
two-dimensional table (often called a “tableau” or “grate” or “lattice”) and then
and reciprocal tables, tables listing the squares of integers from 1 to 59 have been found, summing along the diagonals with appropriate carries, as shown on the right in
leading some math historians to conjecture that Babylonians multiplied using an identity like Figure 0.1. American elementary-school students are taught to multiply one
x y = ((x + y)2 − x 2 − y 2 )/2. But this trick only works when x + y < 60; history is silent on how factor (the “multiplicand”) by each digit in the other factor (the “multiplier”),
the Babylonians might have computed x 2 when x ≥ 60.
9
but at the risk of inflaming the historical enmity between Greece and Egypt, or Lilliput and
writing down all the multiplicand-by-digit products before adding them up, as
Blefuscu, or Macs and PCs, or people who think zero is a natural number and people who are shown on the left in Figure 0.1. This was also the method described by Eutocius,
wrong although he fittingly considered the multiplier digits from left to right, as shown

3 4
 0.2. Multiplication 0. INTRODUCTION

in Figure 0.2. Both of these variants (and several others) are described and variant of this algorithm was copied into the Rhind papyrus by the Egyptian
illustrated side by side in the anonymous 1458 textbook L’Arte dell’Abbaco, also scribe Ahmes around 1650bce, from a document he claimed was (then) about
known as the Treviso Arithmetic, the first printed mathematics book in the West. 350 years old.10 This algorithm was still taught in elementary schools in Eastern
Europe in the late 20th century; it was also commonly used by early digital
computers that did not implement integer multiplication directly in hardware.
The peasant multiplication algorithm reduces the difficult task of multiplying
arbitrary numbers to a sequence of four simpler operations: (1) determining
parity (even or odd), (2) addition, (3) duplation (doubling a number), and (4)
mediation (halving a number, rounding down).

PeasantMultiply(x, y): x y prod

prod ← 0 0
while x > 0 123 + 456 = 456
Figure 0.1. Computing 934 × 314 = 293276 using “long" multiplication (with error-checking by casting
61 + 912 = 1368
out nines) and “lattice" multiplication, from L’Arte dell’Abbaco (1458). (See Image Credits at the end of if x is odd
30 1824
the book.) prod ← prod + y
15 + 3648 = 5016
x ← bx/2c 7 + 7296 = 12312
y← y+y 3 + 14592 = 26904
return prod 1 + 29184 = 56088
Figure 0.3. Multiplication by duplation and mediation

The correctness of this algorithm follows by induction from the following

recursive identity, which holds for all non-negative integers x and y:

0
 if x = 0
x·y= bx/2c · ( y + y) if x is even
bx/2c · ( y + y) + y

if x is odd

Arguably, this recurrence is the peasant multiplication algorithm. Don’t let the
Figure 0.2. Eutocius’s 6th-century calculation of 1172 81 × 1172 81 = 1373877 64
1
, in his commentary on
Archimedes’ Measurement of the Circle, transcribed (left) and translated into modern notation (right) by
iterative pseudocode fool you; the algorithm is fundamentally recursive!
Johan Heiberg (1891). (See Image Credits at the end of the book.) As stated, PeasantMultiply performs O(log x) parity, addition, and media-
tion operations, but we can improve this bound to O(log min{x, y}) by swapping
All of these variants of the lattice algorithm—and other similar variants the two arguments when x > y. Assuming the numbers are represented us-
described by Sunzi, al-Khwārizmı̄, Fibonacci, L’Arte dell’Abbaco, and many other ing any reasonable place-value notation (like binary, decimal, Babylonian
sources—compute the product of any m-digit number and any n-digit number hexagesimal, Egyptian duodecimal, Roman numeral, Chinese counting rods,
in O(mn) time; the running time of every variant is dominated by the number bead positions on an abacus, and so on), each operation requires at most
of single-digit multiplications. O(log(x y)) = O(log max{x, y}) single-digit operations, so the overall running
time of the algorithm is O(log min{x, y} · log max{x, y}) = O(log x · log y).
Duplation and Mediation 10
The version of this algorithm actually used in ancient Egypt does not use mediation or
The lattice algorithm is not the oldest multiplication algorithm for which we parity, but it does use comparisons. To avoid halving, the algorithm pre-computes two tables
by repeated doubling: one containing all the powers of 2 not exceeding x, the other containing
have direct recorded evidence. An even older and arguably simpler algorithm, the same powers of 2 multiplied by y. The powers of 2 that sum to x are then found by greedy
which does not rely on place-value notation, is sometimes called Russian peasant subtraction, and the corresponding entries in the other table are added together to form the
multiplication, Ethiopian peasant multiplication, or just peasant multiplication.A product.

5 6
 0.2. Multiplication 0. INTRODUCTION

In other words, this algorithm requires O(mn) time to multiply an m-digit 〈〈Construct the line perpendicular to ` passing through P .〉〉
RightAngle(`, P): Z
number by an n-digit number; up to constant factors, this is the same running
Choose a point A ∈ `
time as the lattice algorithm. This algorithm requires (a constant factor!) more A, B ← Intersect(Circle(P, A), `)
paperwork to execute by hand than the lattice algorithm, but the necessary C, D ← Intersect(Circle(A, B), Circle(B, A))
primitive operations are arguably easier for humans to perform. In fact, the two return Line(C, D) C
algorithms are equivalent when numbers are represented in binary. 〈〈Construct a point Z such that |AZ| = |AC||AD|/|AB|.〉〉 D
MultiplyOrDivide(A, B, C, D): B
α ← RightAngle(Line(A, C), A)
Compass and Straightedge E ← Intersect(Circle(A, B), α) β
F ← Intersect(Circle(A, D), α)
Classical Greek geometers identified numbers (or more accurately, magnitudes) A E F α
β ← RightAngle(Line(E, C), F )
with line segments of the appropriate length, which they manipulated using two γ ← RightAngle(β, F )
γ
simple mechanical tools—the compass and the straightedge—versions of which return Intersect(γ, Line(A, C))
had already been in common use by surveyors, architects, and other artisans for Figure 0.4. Multiplication by compass and straightedge.
centuries. Using only these two tools, these scholars reduced several complex
geometric constructions to the following primitive operations, starting with one of the algorithm follows from the observation that triangles A C E and A Z F
or more identified reference points.
are similar. The second and third lines of the main algorithm are ambiguous,
• Draw the unique line passing through two distinct identified points. because α intersects any circle centered at A at two distinct points, but the
• Draw the unique circle centered at one identified point and passing through algorithm is actually correct no matter which intersection points are chosen
another. for E and F .
• Identify the intersection point (if any) of two lines. Euclid’s algorithm reduces the problem of multiplying two magnitudes
• Identify the intersection points (if any) of a line and a circle. (lengths) to a series of primitive compass-and-straightedge operations. These
• Identify the intersection points (if any) of two circles. operations are difficult to implement precisely on a modern digital computer, but
Euclid’s algorithm wasn’t designed for a digital computer. It was designed for the
In practice, Greek geometry students almost certainly drew their constructions
on an abax (ἄβαξ), a table covered in dust or sand.11 Centuries earlier, Egyptian Platonic Ideal Geometer, wielding the Platonic Ideal Compass and the Platonic
surveyors carried out many of the same constructions using ropes to determine Ideal Straightedge, who could execute each operation perfectly in constant time
straight lines and circles on the ground.12 However, Euclid and other Greek by definition. In this model of computation, MultiplyOrDivide runs in O(1)
geometers presented compass and straightedge constructions as precise mathe- time!
matical abstractions—points are ideal points; lines are ideal lines; and circles
are ideal circles.
0.3 Congressional Apportionment
Figure 0.4 shows an algorithm, described in Euclid’s Elements about 2500
years ago, for multiplying or dividing two magnitudes. The input consists of Here is another real-world example of an algorithm of significant political
four distinct points A, B, C, and D, and the goal is to construct a point Z such importance. Article I, Section 2 of the United States Constitution requires that
that |AZ| = |AC||AD|/|AB|. In particular, if we define |AB| to be our unit of
Representatives and direct Taxes shall be apportioned among the several
length, then the algorithm computes the product of |AC| and |AD|. States which may be included within this Union, according to their respective
Notice that Euclid first defines a new primitive operation RightAngle by Numbers. . . . The Number of Representatives shall not exceed one for every
(as modern programmers would phrase it) writing a subroutine. The correctness thirty Thousand, but each State shall have at Least one Representative. . . .
11
The written numerals 1 through 9 were known in Europe at least two centuries before Because there are only a finite number of seats in the House of Representatives,
Fibonacci’s Liber Abaci as “gobar numerals”, from the Arabic word ghubār meaning dust, ultimately exact proportional representation requires either shared or fractional represen-
referring to the Indian practice of performing arithmetic on tables covered with sand. The Greek
tatives, neither of which are legal. As a result, over the next several decades,
word ἄβαξ is the origin of the Latin abacus, which also originally referred to a sand table.
12
Remember what “geometry” means? Democritus would later refer to these Egyptian many different apportionment algorithms were proposed and used to round
surveyors, somewhat derisively, as arpedonaptai (ἀρπεδονάπται), meaning “rope-fasteners”. the ideal fractional solution fairly. The algorithm actually used today, called

7 8
 0.3. Congressional Apportionment 0. INTRODUCTION

the Huntington-Hill method or the method of equal proportions, was first priority queue is implemented. The Census Bureau uses a sorted array, stored
suggested by Census Bureau statistician Joseph Hill in 1911, refined by Harvard in a single column of an Excel spreadsheet, which is recalculated from scratch
mathematician Edward Huntington in 1920, adopted into Federal law (2 U.S.C. at every iteration. You (should have) learned a more efficient implementation
§2a) in 1941, and survived a Supreme Court challenge in 1992.13 in your undergraduate data structures class.
The Huntington-Hill method allocates representatives to states one at a Similar apportionment algorithms are used in multi-party parliamentary
time. First, in a preprocessing stage, each state is allocated one representative. elections around the world, where the number of seats allocated to each party
Then in each iteration of the main loop, the next representative is assigned is supposed to be proportional to the number of votes that party receives. The
to the state
p with the highest priority. The priority of each state is defined two most common are the D’Hondt method14 and the Webster–Sainte-Laguë
to be P/ r(r + 1), where P is the state’s population and r is the number of method,15 which respectively use priorities P/(r + 1) and P/(2r + 1) in place of
representatives already allocated to that state. the square-root expression in Huntington-Hill. The Huntington-Hill method is
The algorithm is described in pseudocode in Figure 0.5. The input consists of essentially unique to the United States House of Representatives, thanks in part
an array Pop[1 .. n] storing the populations of the n states and an integer R equal to the constitutional requirement that each state must be allocated at least one
to the total number of representatives; the algorithm assumes R ≥ n. (Currently, representative.
in the United States, n = 50 and R = 435.) The output array Rep[1 .. n] records
the number of representatives allocated to each state.
0.4 A Bad Example
ApportionCongress(Pop[1 .. n], R):
PQ ← NewPriorityQueue As a prototypical example of a sequence of instructions that is not actually an
〈〈Give every state its first representative〉〉 algorithm, consider "Martin’s algorithm”:16
for s ← 1 to n
Rep[s] ← 1 BeAMillionaireAndNeverPayTaxes( ):
p
Get a million dollars.
Insert PQ, s, Pop[i]/ 2
If the tax man comes to your door and says, “You have never paid taxes!”
〈〈Allocate the remaining n − R representatives〉〉 Say “I forgot.”
for i ← 1 to n − R
s ← ExtractMax(PQ) Pretty simple, except for that first step; it’s a doozy! A group of billionaire CEOs,
Rep[s] ← Rep[s] +p1
Silicon Valley venture capitalists, or New York City real-estate hustlers might
priority ← Pop[s] Rep[s] (Rep[s] + 1)
consider this an algorithm, because for them the first step is both unambiguous
Insert(PQ, s, priority)
and trivial,17 but for the rest of us poor slobs, Martin’s procedure is too vague to
return Rep[1 .. n] be considered an actual algorithm. On the other hand, this is a perfect example
Figure 0.5. The Huntington-Hill apportionment algorithm of a reduction—it reduces the problem of being a millionaire and never paying
taxes to the “easier” problem of acquiring a million dollars. We’ll see reductions
This implementation of Huntington-Hill uses a priority queue that supports
over and over again in this book. As hundreds of businessmen and politicians
the operations NewPriorityQueue, Insert, and ExtractMax. (The actual
have demonstrated, if you know how to solve the easier problem, a reduction
law doesn’t say anything about priority queues, of course.) The output of the
tells you how to solve the harder one.
algorithm, and therefore its correctness, does not depend at all on how this
14
developed by Thomas Jefferson in 1792, used for U.S. Congressional apportionment from
13
Overruling an earlier ruling by a federal district court, the Supreme Court unanimously 1792 to 1832, rediscovered by Belgian mathematician Victor D’Hondt in 1878, and refined by Swiss
held that any apportionment method adopted in good faith by Congress is constitutional (United physicist Eduard Hagenbach-Bischoff in 1888.
15
States Department of Commerce v. Montana). The current congressional apportionment algorithm developed by Daniel Webster in 1832, used for U.S. Congressional apportionment from 1842
is described in gruesome detail at the U.S. Census Department web site [Link] to 1911, rediscovered by French mathematician André Sainte-Laguë in 1910, and rediscovered
topics/public-sector/[Link]. A good history of the apportionment again by German physicist Hans Schepers in 1980.
16
problem can be found at [Link] A report Steve Martin, “You Can Be A Millionaire”, Saturday Night Live, January 21, 1978. Also
by the Congressional Research Service describing various apportionment methods is available at appears on Comedy Is Not Pretty, Warner Bros. Records, 1979.
17
[Link] Something something secure quantum blockchain deep-learning something.

9 10
 0.5. Describing Algorithms 0. INTRODUCTION

Martin’s algorithm, like some of our previous examples, is not the kind through fine details, no matter how “obvious” or “intuitive” your high-level ideas
of algorithm that computer scientists are used to thinking about, because it may seem at the moment. Similarly, writing for a skeptical audience forces you
is phrased in terms of operations that are difficult for computers to perform. to develop robust arguments for correctness and efficiency, instead of trusting
This book focuses (almost!) exclusively on algorithms that can be reasonably your intuition or your intelligence.18
implemented on a standard digital computer. Each step in these algorithms I cannot emphasize this point enough: Your primary job as an algorithm
is either directly supported by common programming languages (such as designer is teaching other people how and why your algorithms work. If
arithmetic, assignments, loops, or recursion) or something that you’ve already you can’t communicate your ideas to other human beings, they may as well
learned how to do (like sorting, binary search, tree traversal, or singing “n not exist. Producing correct and efficient executable code is an important
Bottles of Beer on the Wall”). but secondary goal. Convincing yourself, your professors, your (prospective)
employers, your colleagues, or your students that you are smart is at best a
distant third.
0.5 Describing Algorithms
The skills required to effectively design and analyze algorithms are entangled Specifying the Problem
with the skills required to effectively describe algorithms. At least in my classes, Before we can even start developing a new algorithm, we have to agree on what
a complete description of any algorithm has four components: problem our algorithm is supposed to solve. Similarly, before we can even start
• What: A precise specification of the problem that the algorithm solves. describing an algorithm, we have to describe the problem that the algorithm is
• How: A precise description of the algorithm itself. supposed to solve.
• Why: A proof that the algorithm solves the problem it is supposed to solve. Algorithmic problems are often presented using standard English, in terms
of real-world objects. It’s up to us, the algorithm designers, to restate these
• How fast: An analysis of the running time of the algorithm.
problems in terms of formal, abstract, mathematical objects—numbers, arrays,
It is not necessary (or even advisable) to develop these four components in this lists, graphs, trees, and so on—that we can reason about formally. We must also
particular order. Problem specifications, algorithm descriptions, correctness determine if the problem statement carries any hidden assumptions, and state
proofs, and time analyses usually evolve simultaneously, with the development those assumptions explicitly. (For example, in the song “n Bottles of Beer on the
of each component informing the development of the others. For example, Wall”, n is always a non-negative integer.19 )
we may need to tweak the problem description to support a faster algorithm, We may need to refine our specification as we develop the algorithm. For
or modify the algorithm to handle a tricky case in the proof of correctness. example, our algorithm may require a particular input representation, or
Nevertheless, presenting these components separately is usually clearest for the produce a particular output representation, that was left unspecified in the
reader. original informal problem description. Or our algorithm might actually solve a
As with any writing, it’s important to aim your descriptions at the right more general problem than we were originally asked to solve. (This is a common
audience; I recommend writing for a competent but skeptical programmer who feature of recursive algorithms.)
is not as clever as you are. Think of yourself six months ago. As you develop any The specification should include just enough detail that someone else could
new algorithm, you will naturally build up lots of intuition about the problem use our algorithm as a black box, without knowing how or why the algorithm
and about how your algorithm solves it, and your informal reasoning will be actually works. In particular, we must describe the type and meaning of each
guided by that intuition. But anyone reading your algorithm later, or the code input parameter, and exactly how the eventual output depends on the input
you derive from it, won’t share your intuition or experience. Neither will your parameters. On the other hand, our specification should deliberately hide any
compiler. Neither will you six months from now. All they will have is your details that are not necessary to use the algorithm as a black box. Let that which
written description. does not matter truly slide.
Even if you never have to explain your algorithms to anyone else, it’s still 18
In particular, I assume that you are a skeptical novice!
important to develop them with an audience in mind. Trying to communicate p
I’ve never heard anyone sing “ 2 Bottles of Beer on the Wall.” Occasionally I have heard set
19

clearly forces you to think more clearly. In particular, writing for a novice theorists singing “ℵ0 bottles of beer on the wall”, but for some reason they always gave up before
audience, who will interpret your words exactly as written, forces you to work the song was over.

11 12
 0.5. Describing Algorithms 0. INTRODUCTION

For example, the lattice and duplation-and-mediation algorithms both solve Whenever we describe an algorithm, our description should include every
the same problem: Given two non-negative integers x and y, each represented detail necessary to fully specify the algorithm, prove its correctness, and analyze
as an array of digits, compute the product x · y, also represented as an array of its running time. At the same time, it should exclude any details that are not
digits. To someone using these algorithms, the choice of algorithm is completely necessary to fully specify the algorithm, prove its correctness, and analyze its
irrelevant. On the other hand, the Greek straightedge-and-compass algorithm running time. (Slide.) At a more practical level, our description should allow
solves a different problem, because the input and output values are represented a competent but skeptical programmer who has not read this book to quickly
by line segments instead of arrays of digits. and correctly implement the algorithm in their favorite programming language,
without understanding why it works.
Describing the Algorithm I don’t want to bore you with the rules I follow for writing pseudocode, but
I must caution against one especially pernicious habit. Never describe repeated
Computer programs are concrete representations of algorithms, but algorithms operations informally, as in “Do [this] first, then do [that] second, and so on.” or
are not programs. Rather, algorithms are abstract mechanical procedures “Repeat this process until [something]”. As anyone who has taken one of those
that can be implemented in any programming language that supports the frustrating “What comes next in this sequence?” tests already knows, describing
underlying primitive operations. The idiosyncratic syntactic details of your the first few steps of an algorithm says little or nothing about what happens
favorite programming language are utterly irrelevant; focusing on these will in later steps. If your algorithm has a loop, write it as a loop, and explicitly
only distract you (and your readers) from what’s really going on.20 A good describe what happens in an arbitrary iteration. Similarly, if your algorithm is
algorithm description is closer to what we should write in the comments of a recursive, write it recursively, and explicitly describe the case boundaries and
real program than the code itself. Code is a poor medium for storytelling. what happens in each case.
On the other hand, a plain English prose description is usually not a good idea
either. Algorithms have lots of idiomatic structure—especially conditionals, loops,
function calls, and recursion—that are far too easily hidden by unstructured 0.6 Analyzing Algorithms
prose. Colloquial English is full of ambiguities and shades of meaning, but
algorithms must be described as unambiguously as possible. Prose is a poor It’s not enough just to write down an algorithm and say “Behold!” We must also
medium for precision. convince our audience (and ourselves!) that the algorithm actually does what
it’s supposed to do, and that it does so efficiently.
In my opinion, the clearest way to present an algorithm is using a combination
of pseudocode and structured English. Pseudocode uses the structure of formal
programming languages and mathematics to break algorithms into primitive Correctness
steps; the primitive steps themselves can be written using mathematical notation,
In some application settings, it is acceptable for programs to behave correctly
pure English, or an appropriate mixture of the two, whatever is clearest. Well-
most of the time, on all “reasonable” inputs. Not in this book; we require
written pseudocode reveals the internal structure of the algorithm but hides
algorithms that are always correct, for all possible inputs. Moreover, we must
irrelevant implementation details, making the algorithm easier to understand,
prove that our algorithms are correct; trusting our instincts, or trying a few test
analyze, debug, and implement.
cases, isn’t good enough. Sometimes correctness is truly obvious, especially
20 for algorithms you’ve seen in earlier courses. On the other hand, “obvious”
This is, of course, a matter of religious conviction. Armchair linguists argue incessantly over
the Sapir-Whorf hypothesis, which states (more or less) that people think only in the categories is all too often a synonym for “wrong”. Most of the algorithms we discuss in
imposed by their languages. According to an extreme formulation of this principle, some concepts this course require real work to prove correct. In particular, correctness proofs
in one language simply cannot be understood by speakers of other languages, not just because of
technological advancement—How would you translate “jump the shark” or “Fortnite streamer” usually involve induction. We like induction. Induction is our friend.21
into Aramaic?—but because of inherent structural differences between languages and cultures. Of course, before we can formally prove that our algorithm does what it’s
For a more skeptical view, see Steven Pinker’s The Language Instinct. There is admittedly some supposed to do, we have to formally describe what it’s supposed to do!
strength to this idea when applied to different programming paradigms. (What’s the Y combinator,
again? How do templates work? What’s an Abstract Factory?) Fortunately, those differences are
too subtle to have any impact on the material in this book. For a compelling counterexample, see
21
Chris Okasaki’s monograph Functional Data Structures and its more recent descendants. If induction is not your friend, you will have a hard time with this book.

13 14
 0.6. Analyzing Algorithms 0. INTRODUCTION

Running Time Other quadratic-time songs include “Old MacDonald Had a Farm”, “There
Was an Old Lady Who Swallowed a Fly”, “Hole in the Bottom of the Sea”, “Green
The most common way of ranking different algorithms for the same problem is
Grow the Rushes O”, “The Rattlin’ Bog”, “The Court Of King Caractacus”,“The
by how quickly they run. Ideally, we want the fastest possible algorithm for any
Barley-Mow”, “If I Were Not Upon the Stage”, “Star Trekkin’ ”,“Ist das nicht
particular problem. In many application settings, it is acceptable for programs
ein Schnitzelbank?”,22 “Il Pulcino Pio”, “Minkurinn í hænsnakofanum”, “Echad
to run efficiently most of the time, on all “reasonable” inputs. Not in this book;
Mi Yodea”, and “Το κοκοράκι”. For more examples, consult your favorite
we require algorithms that always run efficiently, even in the worst case.
preschooler.
But how do we measure running time? As a specific example, how long does
it take to sing the song BottlesOfBeer(n)? This is obviously a function of the Alouette(lapart[1 .. n]):
input value n, but it also depends on how quickly you can sing. Some singers Chantez « Alouette, gentille alouette, alouette, je te plumerai. »
pour tout i de 1 à n
might take ten seconds to sing a verse; others might take twenty. Technology
Chantez « Je te plumerai lapart[i]. Je te plumerai lapart[i]. »
widens the possibilities even further. Dictating the song over a telegraph using pour tout j de i à 1 〈〈à rebours〉〉
Morse code might take a full minute per verse. Downloading an mp3 over Chantez « Et lapart[ j] ! Et lapart[ j] ! »
the Web might take a tenth of a second per verse. Duplicating the mp3 in a Chantez « Alouette! Alouette! Aaaaaa. . . »
computer’s main memory might take only a few microseconds per verse. Chantez « . . . alouette, gentille allouette, alouette, je te plumerai. »
What’s important here is how the singing time changes as n grows. Singing
BottlesOfBeer(2n) requires about twice much time as singing BottlesOf- A few songs have even more bizarre singing times. A fairly modern example
Beer(n), no matter what technology is being used. This is reflected in the is “The TELNET Song” by Guy Steele, which actually takes Θ(2n ) time to sing
asymptotic singing time Θ(n). the first n verses; Steele recommended n = 4. Finally, there are some songs that
We can measure time by counting how many times the algorithm executes a never end.23
certain instruction or reaches a certain milestone in the “code”. For example, Except for “The TELNET Song”, all of these songs are most naturally
we might notice that the word “beer” is sung three times in every verse of expressed as a small set of nested loops, so their running singing times can be
BottlesOfBeer, so the number of times you sing “beer” is a good indication computed using nested summations. The running time of a recursive algorithm is
of the total singing time. For this question, we can give an exact answer: more easily expressed as a recurrence. For example, the peasant multiplication
BottlesOfBeer(n) mentions beer exactly 3n + 3 times. algorithm can be expressed recursively as follows:
Incidentally, there are lots of songs with quadratic singing time. This one is 
probably familiar to most English-speakers:
0
 if x = 0
x·y= bx/2c · ( y + y) if x is even
NDaysOfChristmas(gifts[2 .. n]):
bx/2c · ( y + y) + y

if x is odd
for i ← 1 to n
Sing “On the i th day of Christmas, my true love gave to me”
for j ← i down to 2 Let T (x, y) denote the number of parity, addition, and mediation operations
Sing “ j gifts[ j],” required to compute x · y. This function satisfies the recursive inequality
if i > 1 T (x, y) ≤ T (bx/2c, 2 y) + 2 with base case T (0, y) = 0. Techniques described
Sing “and”
in the next chapter imply the upper bound T (x, y) = O(log x).
Sing “a partridge in a pear tree.”
Sometimes the running time of an algorithm depends on a particular
The input to NDaysOfChristmas is a list of n − 1 gifts, represented here as implementation of some underlying data structure of subroutine. For example,
an array. It’s quite easy to show that Pthe singing time is Θ(n2 ); in particular, the Huntington-Hill apportionment algorithm ApportionCongress runs in
n
the singer mentions the name of a gift i=1 i = n(n + 1)/2 times (counting the O(N + RI + (R − n)E) time, where N denotes the running time of NewPriority-
partridge in the pear tree). It’s also easy toPsee that during the first n days of Queue, I denotes the running time of Insert, and E denotes the running time
n Pi
Christmas, my true love gave to me exactly i=1 j=1 j = n(n + 1)(n + 2)/6 = 22
Ja, das ist Otto von Schnitzelpusskrankengescheitmeyer!
Θ(n3 ) gifts. 23
They just go on and on, my friend.

15 16
 Exercises 0. INTRODUCTION

of ExtractMax. Under the reasonable assumption that R ≥ 2n (on average, (b) How long does it take to sing “n Bottles of Beer on the Wall”?
each state gets at least two representatives), we can simplify this bound to (c) How long does it take to sing “The n Days of Christmas”?
O(N + R(I + E)). The precise running time depends on the implementation
As usual, express your answers in the form O( f (n)) for some function f .
of the underlying priority queue. The Census Bureau implements the priority
queue as an unsorted array, which gives us N = I = Θ(1) and E = Θ(n), so the 3. The cumulative drinking song “The Barley Mow” has been sung throughout
Census Bureau’s implementation of ApportionCongress runs in O(Rn) time. the British Isles for centuries. The song has many variants; Figure 0.6
However, if we implement the priority queue as a binary heap or a heap-ordered contains pseudolyrics for one version traditionally sung in Devon and
array, we have N = Θ(1) and I = E = O(log n), so the overall algorithm runs in Cornwall, where vessel[i] is the name of a vessel that holds 2i ounces of
O(R log n) time. beer.25
Finally, sometimes we are interested in computational resources other than
BarleyMow(n):
time, such as space, number of coin flips, number of cache or page faults, number “Here’s a health to the barley-mow, my brave boys,”
of inter-process messages, or the number of gifts my true love gave to me. These “Here’s a health to the barley-mow!”
resources can be analyzed using the same techniques used to analyze running “We’ll drink it out of the jolly brown bowl,”
time. For example, lattice multiplication of two n-digit numbers requires O(n2 ) “Here’s a health to the barley-mow!”
space if we write down all the partial products before adding them, but only “Here’s a health to the barley-mow, my brave boys,”
“Here’s a health to the barley-mow!”
O(n) space if we add them on the fly.
for i ← 1 to n
“We’ll drink it out of the vessel[i], boys,”
“Here’s a health to the barley-mow!”
Exercises for j ← i downto 1
“The vessel[ j],”
0. Describe and analyze an efficient algorithm that determines, given a legal “And the jolly brown bowl!”
arrangement of standard pieces on a standard chess board, which player will “Here’s a health to the barley-mow!”
win at chess from the given starting position if both players play perfectly. “Here’s a health to the barley-mow, my brave boys,”
“Here’s a health to the barley-mow!”
[Hint: There is a trivial one-line solution!]
Figure 0.6. “The Barley Mow”.
ª
1. (a) Identify (or write) a song that requires Θ(n ) time to sing the first n
3

verses. (a) Suppose each name vessel[i] is a single word, and you can sing four
(b) Identify (or write) a song that requires Θ(n log n) time to sing the first words a second. How long would it take you to sing BarleyMow(n)?
n verses. (Give a tight asymptotic bound.)
(c) Identify (or write) a song that requires some other weird amount of (b) If you want to sing this song for arbitrarily large values of n, you’ll have
time to sing the first n verses. to make up your own vessel names. To avoid repetition, these names
must become progressively longer as n increases. Suppose vessel[n] has
2. Careful readers might complain that our analysis of songs like “n Bottles of 25
In practice, the song uses some subset of the following vessels; nipperkin, quarter-gill,
Beer on the Wall” or “The n Days of Christmas” is overly simplistic, because half-a-gill, gill, quarter-pint, half-a-pint, pint, quart, pottle, gallon, half-anker, anker, firkin,
larger numbers take longer to sing than shorter numbers. More generally, half-barrel/kilderkin, barrel, hogshead, pipe/butt, tun, well, river, and ocean. With a few
exceptions (especially at the end), every vessel in this list has twice the volume of its predecessor.
because there are only so many words of a given length, larger sets of words Irish and Scottish versions of the song have slightly different lyrics, and they usually switch to
necessarily contain longer words.24 We can more accurately estimate singing people (barmaid, landlord, drayer, and so on) after “gallon”.
time by counting the number of syllables sung, rather than the number of An early version of the song entitled “Give us once a drink” appears in the play Jack Drum’s
words. Entertainment (or the Comedie of Pasquill and Katherine) written by John Marston around 1600.
(“Giue vs once a drinke for and the black bole. Sing gentle Butler bally moy!”) There is some
(a) How long does it take to sing the integer n? disagreement whether Marston wrote the “high Dutch Song” specifically for the play, whether
“bally moy” is a mondegreen for “barley mow” or vice versa, or whether it’s actually the same
24
Ja, das ist das Subatomarteilchenbeschleunigungsnaturmäßigkeitsuntersuchungsmaschine! song at all. These discussions are best had over n bottles of beer.

17 18
 Exercises 0. INTRODUCTION

Θ(log n) syllables, and you can sing six syllables per second. Now how (a) Show that calling HHGuess with the standard divisor D = P/R does not
long would it take you to sing BarleyMow(n)? (Give a tight asymptotic necessarily yield a valid apportionment.
bound.) (b) Prove that if HHGuess returns the same value of reps for two different
(c) Suppose each time you mention the name of a vessel, you actually drink divisors D and D0 , it also computes the same allocation Rep[1 .. n] for
the corresponding amount of beer: one ounce for the jolly brown bowl, both of those divisors.
and 2i ounces for each vessel[i]. Assuming for purposes of this problem (c) Prove that if HHGuess returns the correct value R, it computes the same
that you are at least 21 years old, exactly how many ounces of beer would allocation Rep[1 .. n] as our earlier algorithm ApportionCongress.
you drink if you sang BarleyMow(n)? (Give an exact answer, not just
(d) Prove that a “correct” divisor D does not necessarily exist! That is,
an asymptotic bound.)
describe inputs Pop[1 .. n] and R, where n ≤ R ≤ P, such that for every
real number D > 0, the number of representatives allocated by HHGuess
4. Recall that the input to the Huntington-Hill algorithm ApportionCongress
is not equal to R. [Hint: What happens if we change < to ≤ in the
is an array Pop[1 .. n], where Pop[i] is the population of the ith state, and an
fourth line of HHGuess?]
integer R, the total number of representatives to be allotted. The output is
an array Rep[1 .. n], where Rep[i] is the number of representatives allotted
to the ith state by the algorithm.
The Huntington-Hill algorithm is sometimes described in a way that
avoids the use of priority queues entirely. The top-level algorithm “guesses”
a positive real number D, called the divisor, and then runs the following
subroutine to compute an apportionment. The variable q is the ideal quota
of representatives allocated to a state for the given divisor D; the actual
number of representatives allocated is always either dqe or bqc.
HHGuess(Pop[1 .. n], R, D):
reps ← 0
for i ← 1 to n
q ← Pop[i]/D
if q · q < dqe · bqc
Rep[i] ← bqc
else
Rep[i] ← dqe
reps ← reps + Rep[i]
return reps

There are three possibilities for the final return value reps. If reps < R,
we did not allocate enough representatives, which (at least intuitively)
means our divisor D was too small. If reps > R, we allocated too many
representatives, which (at least intuitively) means our divisor D was too
large. Finally, if reps = R, we can return the array Rep[1 .. n] as the final
apportionment. In practice, we can compute a valid apportionment (with
reps = R) by calling HHGuess with a small number of integer divisors close
to the standard divisor D = P/R.
Pn
In the following problems, let P = i=1 Pop[i] denote the total popula-
tion of all n states, and assume that n ≤ R ≤ P.

19 20
 1. RECURSION
The control of a large force is the same principle as the control of a few men:
it is merely a question of dividing up their numbers.
— Sun Zi, The Art of War (c. 400CE), translated by Lionel Giles (1910) depend on the precise data representation (tally marks, clay tokens, Babylonian
Our life is frittered away by detail. . . . Simplify, simplify.
hexagesimal, quipu, counting rods, Roman numerals, finger positions, augrym
— Henry David Thoreau, Walden (1854) stones, gobar numerals, binary, negabinary, Gray code, balanced ternary, phinary,
quater-imaginary, . . . ), or on the precise implementations of those operations.
Now, don’t ask me what Voom is. I never will know.
Of course, the running time of the multiplication algorithm depends on the
But, boy! Let me tell you, it DOES clean up snow!
running time of the addition, mediation, and parity operations, but that’s
— Dr. Seuss [Theodor Seuss Geisel], The Cat in the Hat Comes Back (1958)
a separate issue from correctness. Most importantly, we can create a more
Do the hard jobs first. The easy jobs will take care of themselves. efficient multiplication algorithm just by switching to a more efficient number
— attributed to Dale Carnegie representation (from tally marks to place-value notation, for example).
Similarly, the Huntington-Hill algorithm reduces the problem of apportioning
Congress to the problem of maintaining a priority queue that supports the
operations Insert and ExtractMax. The abstract data type “priority queue” is
a black box; the correctness of the apportionment algorithm does not depend
on any specific priority queue data structure. Of course, the running time of
the apportionment algorithm depends on the running time of the Insert and
ExtractMax algorithms, but that’s a separate issue from the correctness of the

1 algorithm. The beauty of the reduction is that we can create a more efficient
apportionment algorithm by simply swapping in a new priority queue data
structure. Moreover, the designer of that data structure does not need to know
or care that it will be used to apportion Congress.
When we design algorithms, we may not know exactly how the basic building
blocks we use are implemented, or how our algorithms might be used as building
Recursion blocks to solve even bigger problems. That ignorance is uncomfortable for many
beginners, but it is both unavoidable and extremely useful. Even when you
do know precisely how your components work, it is often extremely helpful to
pretend that you don’t.
1.1 Reductions

Reduction is the single most common technique used in designing algorithms. 1.2 Simplify and Delegate
Reducing one problem X to another problem Y means to write an algorithm
for X that uses an algorithm for Y as a black box or subroutine. Crucially, the Recursion is a particularly powerful kind of reduction, which can be described
correctness of the resulting algorithm for X cannot depend in any way on how loosely as follows:
the algorithm for Y works. The only thing we can assume is that the black box
• If the given instance of the problem can be solved directly, solve it directly.
solves Y correctly. The inner workings of the black box are simply none of our
business; they’re somebody else’s problem. It’s often best to literally think of the • Otherwise, reduce it to one or more simpler instances of the same problem.
black box as functioning purely by magic. If the self-reference is confusing, it may be helpful to imagine that someone else
For example, the peasant multiplication algorithm described in the previous is going to solve the simpler problems, just as you would assume for other types
chapter reduces the problem of multiplying two arbitrary positive integers to of reductions. I like to call that someone else the Recursion Fairy. Your only
three simpler problems: addition, mediation (halving), and parity-checking. The task is to simplify the original problem, or to solve it directly when simplification
algorithm relies on an abstract “positive integer” data type that supports those is either unnecessary or impossible; the Recursion Fairy will solve all the simpler
three operations, but the correctness of the multiplication algorithm does not subproblems for you, using Methods That Are None Of Your Business So Butt

21 22
 1.2. Simplify and Delegate 1. RECURSION

Out.1 Mathematically sophisticated readers might recognize the Recursion Fairy 1.3 Tower of Hanoi
by its more formal name: the Induction Hypothesis.
There is one mild technical condition that must be satisfied in order for The Tower of Hanoi puzzle was first published—as an actual physical puzzle!—by
any recursive method to work correctly: There must be no infinite sequence of the French teacher and recreational mathematician Édouard Lucas in 1883,2
reductions to simpler and simpler instances. Eventually, the recursive reductions under the pseudonym “N. Claus (de Siam)” (an anagram of “Lucas d’Amiens”).
must lead to an elementary base case that can be solved by some other method; The following year, Henri de Parville described the puzzle with the following
otherwise, the recursive algorithm will loop forever. The most common way remarkable story:3
to satisfy this condition is to reduce to one or more smaller instances of the In the great temple at Benares4 . . . beneath the dome which marks the centre of
same problem. For example, if the original input is a skreeble with n glurps, the the world, rests a brass plate in which are fixed three diamond needles, each
a cubit high and as thick as the body of a bee. On one of these needles, at the
input to each recursive call should be a skreeble with strictly less than n glurps.
creation, God placed sixty-four discs of pure gold, the largest disc resting on the
Of course this is impossible if the skreeble has no glurps at all—You can’t have brass plate, and the others getting smaller and smaller up to the top one. This is
negative glurps; that would be silly!—so in that case we must grindlebloff the the Tower of Bramah. Day and night unceasingly the priests transfer the discs
skreeble using some other method. from one diamond needle to another according to the fixed and immutable
We’ve already seen one instance of this pattern in the peasant multiplication laws of Bramah, which require that the priest on duty must not move more
algorithm, which is based directly on the following recursive identity. than one disc at a time and that he must place this disc on a needle so that
 there is no smaller disc below it. When the sixty-four discs shall have been thus

0
 if x = 0 transferred from the needle on which at the creation God placed them to one
of the other needles, tower, temple, and Brahmins alike will crumble into dust,
x · y = bx/2c · ( y + y) if x is even and with a thunderclap the world will vanish.
bx/2c · ( y + y) + y if x is odd


The same recurrence can be expressed algorithmically as follows:

PeasantMultiply(x, y):
if x = 0
return 0
else
x 0 ← bx/2c
y0 ← y + y
prod ← PeasantMultiply(x 0 , y 0 ) 〈〈Recurse!〉〉
if x is odd
prod ← prod + y
Figure 1.1. The (8-disk) Tower of Hanoi puzzle
return prod
Of course, as good computer scientists, our first instinct on reading this
A lazy Egyptian scribe could execute this algorithm by computing x 0 and y 0 ,
story is to substitute the variable n for the hardwired constant 64. And because
asking a more junior scribe to multiply x 0 and y 0 , and then possibly adding y
most physical instances of the puzzle are made of wood instead of diamonds
to the junior scribe’s response. The junior scribe’s problem is simpler because
and gold, I will call the three possible locations for the disks “pegs” instead of
x 0 < x, and repeatedly decreasing a positive integer eventually leads to 0. How
the junior scribe actually computes x 0 · y 0 is none of the senior scribe’s business 2
Lucas later claimed to have invented the puzzle in 1876.
3
(and it’s none of your business, either). This English translation is taken from W. W. Rouse Ball’s 1892 book Mathematical Recreations
and Essays.
1 4
When I was an undergraduate, I attributed recursion to “elves” instead of the Recursion Fairy, The “great temple at Benares” is almost certainly the Kashi Vishvanath Temple in Varanasi,
referring to the Brothers Grimm story about an old shoemaker who leaves his work unfinished Uttar Pradesh, India, located approximately 2400km west-north-west of Hà Nô.i, Viê.t Nam, where
when he goes to bed, only to discover upon waking that elves (“Wichtelmänner”) have finished the fictional N. Claus supposedly resided. Coincidentally, the French Army invaded Hanoi in 1883,
everything overnight. Someone more entheogenically experienced than I might recognize these the same year Lucas released his puzzle, ultimately leading to its establishment as the capital of
Rekursionswichtelmänner as Terence McKenna’s “self-transforming machine elves”. French Indochina.

23 24
 1.3. Tower of Hanoi 1. RECURSION

“needles”. How can we move a tower of n disks from one peg to another, using a It may be tempting to think about how all those smaller disks move around—
third spare peg as an occasional placeholder, without ever placing a disk on top or more generally, what happens when the recursion is unrolled—but really,
of a smaller disk? don’t do it. For most recursive algorithms, unrolling the recursion is neither
As N. Claus (de Siam) pointed out in the pamphlet included with his puzzle, necessary nor helpful. Our only task is to reduce the problem instance we’re
the secret to solving this puzzle is to think recursively. Instead of trying to solve given to one or more simpler instances, or to solve the problem directly if such
the entire puzzle at once, let’s concentrate on moving just the largest disk. We a reduction is impossible. Our recursive Tower of Hanoi algorithm is trivially
can’t move it at the beginning, because all the other disks are in the way. So correct when n = 0. For any n ≥ 1, the Recursion Fairy correctly moves the top
first we have to move those n − 1 smaller disks to the spare peg. Once that’s n − 1 disks (more formally, the Inductive Hypothesis implies that our recursive
done, we can move the largest disk directly to its destination. Finally, to finish algorithm correctly moves the top n − 1 disks) so our algorithm is correct.
the puzzle, we have to move the n − 1 smaller disks from the spare peg to their The recursive Hanoi algorithm is expressed in pseudocode in Figure 1.4.
destination. The algorithm moves a stack of n disks from a source peg (src) to a destination
peg (dst) using a third temporary peg (tmp) as a placeholder. Notice that the
algorithm correctly does nothing at all when n = 0.
recursion

Hanoi(n, src, dst, tmp):

if n > 0
Hanoi(n − 1, src, tmp, dst) 〈〈Recurse!〉〉
move disk n from src to dst
recursion
Hanoi(n − 1, tmp, dst, src) 〈〈Recurse!〉〉
Figure 1.4. A recursive algorithm to solve the Tower of Hanoi
Figure 1.2. The Tower of Hanoi algorithm; ignore everything but the bottom disk.
Let T (n) denote the number of moves required to transfer n disks—the
running time of our algorithm. Our vacuous base case implies that T (0) = 0,
So now all we have to figure out is how to—
and the more general recursive algorithm implies that T (n) = 2T (n − 1) + 1
NO!! STOP!! for any n ≥ 1. By writing out the first several values of T (n), we can easily
That’s it! We’re done! We’ve successfully reduced the n-disk Tower of Hanoi guess that T (n) = 2n − 1; a straightforward induction proof implies that this
problem to two instances of the (n − 1)-disk Tower of Hanoi problem, which guess is correct. In particular, moving a tower of 64 disks requires 264 − 1 =
we can gleefully hand off to the Recursion Fairy—or to carry Lucas’s metaphor 18,446,744,073,709,551,615 individual moves. Thus, even at the impressive rate
further, to the junior monks at the temple. Our job is finished. If we didn’t trust of one move per second, the monks at Benares will be at work for approximately
the junior monks, we wouldn’t have hired them; let them do their job in peace. 585 billion years (“plus de cinq milliards de siècles”) before tower, temple, and
Our reduction does make one subtle but extremely important assumption: Brahmins alike will crumble into dust, and with a thunderclap the world will
There is a largest disk. Our recursive algorithm works for any positive number vanish.
of disks, but it breaks down when n = 0. We must handle that case using a
different method. Fortunately, the monks at Benares, being good Buddhists, are
1.4 Mergesort
quite adept at moving zero disks from one peg to another in no time at all, by
doing nothing. Mergesort is one of the earliest algorithms designed for general-purpose stored-
program computers. The algorithm was developed by John von Neumann in
1945, and described in detail in a publication with Herman Goldstine in 1947, as
one of the first non-numerical programs for the EDVAC.5
5
Goldstine and von Neumann actually described an non-recursive variant now usually called
bottom-up mergesort. At the time, large data sets were sorted by special-purpose machines—
Figure 1.3. The vacuous base case for the Tower of Hanoi algorithm. There is no spoon. almost all built by IBM—that manipulated punched cards using variants of binary radix sort. Von

25 26
 1.4. Mergesort 1. RECURSION

1. Divide the input array into two subarrays of roughly equal size. Proof: Let A[1 .. n] be any array and m any integer such that the subarrays
2. Recursively mergesort each of the subarrays. A[1 .. m] and A[m + 1 .. n] are sorted. We prove that for all k from 0 to n, the last
n − k − 1 iterations of the main loop correctly merge A[i .. m] and A[ j .. n] into
3. Merge the newly-sorted subarrays into a single sorted array.
B[k .. n]. The proof proceeds by induction on n − k + 1, the number of elements
Input: S O R T I N G E X A M P L
remaining to be merged.
Divide: S O R T I N G E X A M P L If k > n, the algorithm correctly merges the two empty subarrays by doing
Recurse Left: I N O R S T G E X A M P L absolutely nothing. (This is the base case of the inductive proof.) Otherwise,
Recurse Right: I N O R S T A E G L M P X there are four cases to consider for the kth iteration of the main loop.
Merge: A E G I L M N O P R S T X

• If j > n, then subarray A[ j .. n] is empty, so min A[i .. m] ∪ A[ j .. n] = A[i].
Figure 1.5. A mergesort example.

• If i > m, then subarray A[i .. m] is empty, so min A[i .. m] ∪ A[ j .. n] = A[ j].


The first step is completely trivial—just divide the array size by two—and • Otherwise, if A[i] < A[ j], then min A[i .. m] ∪ A[ j .. n] = A[i].


we can delegate the second step to the Recursion Fairy. All the real work is • Otherwise, we must have A[i] ≥ A[ j], and min A[i .. m] ∪ A[ j .. n] = A[ j].
done in the final merge step. A complete description of the algorithm is given in
In all four cases, B[k] is correctly assigned the smallest element of A[i .. m] ∪
Figure 1.6; to keep the recursive structure clear, I’ve extracted the merge step
A[ j .. n]. In the two cases with the assignment B[k] ← A[i], the Recursion Fairy
into an independent subroutine. The merge algorithm is also recursive—identify
correctly merges—sorry, I mean the Induction Hypothesis implies that the last
the first element of the output array, and then recursively merge the rest of the
n − k iterations of the main loop correctly merge A[i + 1 .. m] and A[ j .. n] into
input arrays.
B[k + 1 .. n]. Similarly, in the other two cases, the Recursion Fairy also correctly
Merge(A[1 .. n], m): merges the rest of the subarrays. ƒ
i ← 1; j ← m + 1
for k ← 1 to n Theorem 1.2. MergeSort correctly sorts any input array A[1 .. n].
if j > n
MergeSort(A[1 .. n]):
B[k] ← A[i]; i ← i+1 Proof: We prove the theorem by induction on n. If n ≤ 1, the algorithm
if n > 1
else if i > m correctly does nothing. Otherwise, the Recursion Fairy correctly sorts—sorry, I
m ← bn/2c B[k] ← A[ j]; j ← j+1
MergeSort(A[1 .. m]) 〈〈Recurse!〉〉 mean the induction hypothesis implies that our algorithm correctly sorts the
else if A[i] < A[ j]
MergeSort(A[m + 1 .. n]) 〈〈Recurse!〉〉 B[k] ← A[i]; i ← i+1 two smaller subarrays A[1 .. m] and A[m + 1 .. n], after which they are correctly
Merge(A[1 .. n], m) else Merged into a single sorted array (by Lemma 1.1). ƒ
B[k] ← A[ j]; j ← j+1
for k ← 1 to n Analysis
A[k] ← B[k]
Figure 1.6. Mergesort Because the MergeSort algorithm is recursive, its running time is naturally
expressed as a recurrence. Merge clearly takes O(n) time, because it’s a simple
for-loop with constant work per iteration. We immediately obtain the following
Correctness recurrence for MergeSort:



To prove that this algorithm is correct, we apply our old friend induction twice, T (n) = T dn/2e + T bn/2c + O(n).
first to the Merge subroutine then to the top-level Mergesort algorithm. As in most divide-and-conquer recurrences, we can safely strip out the floors
and ceilings (using a technique called domain transformations described later
Lemma 1.1. Merge correctly merges the subarrays A[1 .. m] and A[m + 1 .. n], in this chapter), giving us the simpler recurrence T (n) = 2T (n/2) + O(n). The
assuming those subarrays are sorted in the input. “all levels equal” case of the recursion tree method (also described later in this
Neumann argued (successfully!) that because the EDVAC could sort faster than IBM’s dedicated
chapter) immediately implies the closed-form solution T (n) = O(n log n). Even
sorters, “without human intervention or need for additional equipment”, the EDVAC was an “all if you are not (yet) familiar with recursion trees, you can verify the solution
purpose” machine, and special-purpose sorting machines were no longer necessary. T (n) = O(n log n) by induction.

27 28
 1.5. Quicksort 1. RECURSION

1.5 Quicksort the other to prove that QuickSort correctly sorts assuming Partition is correct.
To prove Partition is correct, we need to prove the following loop invariant: At
Quicksort is another recursive sorting algorithm, discovered by Tony Hoare in the end of each iteration of the main loop, everything in the subarray A[1 .. `]
1959 and first published in 1961. In this algorithm, the hard work is splitting is `ess than A[n], and nothing in the subarray A[` + 1 .. i] is less than A[n].
the array into smaller subarrays before recursion, so that merging the sorted I’ll leave the remaining straightforward but tedious details as exercises for the
subarrays is trivial. reader.
1. Choose a pivot element from the array.
2. Partition the array into three subarrays containing the elements smaller Analysis
than the pivot, the pivot element itself, and the elements larger than the
pivot. The analysis of quicksort is also similar to that of mergesort. Partition clearly
runs in O(n) time, because it’s a simple for-loop with constant work per iteration.
3. Recursively quicksort the first and last subarrays.
For QuickSort, we get a recurrence that depends on r, the rank of the chosen
Input: S O R T I N G E X A M P L pivot element:
Choose a pivot: S O R T I N G E X A M P L T (n) = T (r − 1) + T (n − r) + O(n)
Partition: A G O E I N L M P T X S R
If we could somehow always magically choose the pivot to be the median element
Recurse Left: A E G I L M N O P T X S R
Recurse Right: A E G I L M N O P R S T X of the array A, we would have r = dn/2e, the two subproblems would be as close
to the same size as possible, the recurrence would become
Figure 1.7. A quicksort example.



More detailed pseudocode is given in Figure 1.8. In the Partition subroutine, T (n) = T dn/2e − 1 + T bn/2c + O(n) ≤ 2T (n/2) + O(n),
the input parameter p is the index of the pivot element in the unsorted array;
and we’d have T (n) = O(n log n) using either the recursion tree method or
the subroutine partitions the array and returns the new index of the pivot
the even simpler “Oh yeah, we already solved that recurrence for mergesort”
element. There are many different efficient partitioning algorithms; the one
method.
I’m presenting here is attributed to Nico Lomuto.6 The variable ` counts the
In fact, as we will see later in this chapter, we can actually locate the
number of items in the array that are `ess than the pivot element.
median element in an unsorted array in linear time, but the algorithm is fairly
Partition(A[1 .. n], p): complicated, and the hidden constant in the O(·) notation is large enough to
swap A[p] ↔ A[n]
QuickSort(A[1 .. n]): make the resulting sorting algorithm impractical. In practice, most programmers
`←0 〈〈#items < pivot〉〉
if (n > 1) settle for something simple, like choosing the first or last element of the array.
for i ← 1 to n − 1
Choose a pivot element A[p] In this case, r can take any value between 1 and n, so we have
if A[i] < A[n]
r ← Partition(A, p)
`←`+1
QuickSort(A[1 .. r − 1]) 〈〈Recurse!〉〉

swap A[`] ↔ A[i] T (n) = max T (r − 1) + T (n − r) + O(n) .
QuickSort(A[r + 1 .. n]) 〈〈Recurse!〉〉 1≤r≤n
swap A[n] ↔ A[` + 1]
return ` + 1
In the worst case, the two subproblems are completely unbalanced—either r = 1
Figure 1.8. Quicksort or r = n—and the recurrence becomes T (n) ≤ T (n − 1) + O(n). The solution is
T (n) = O(n 2 ).
Another common heuristic is called “median of three”—choose three el-
Correctness
ements (usually at the beginning, middle, and end of the array), and take
Just like mergesort, proving that QuickSort is correct requires two separate the median of those three elements as the pivot. Although this heuristic is
induction proofs: one to prove that Partition correctly partitions the array, and somewhat more efficient in practice than just choosing one element, especially
6
Hoare proposed a more complicated “two-way” partitioning algorithm that has some
when the array is already (nearly) sorted, we can still have r = 2 or r = n − 1
practical advantages over Lomuto’s algorithm. On the other hand, Hoare’s partitioning algorithm in the worst case. With the median-of-three heuristic, the recurrence becomes
is one of the places off-by-one errors go to die. T (n) ≤ T (1) + T (n − 2) + O(n), whose solution is still T (n) = O(n2 ).

29 30
 1.6. The Pattern 1. RECURSION

Intuitively, the pivot element should “usually” fall somewhere in the middle of calls, each on a problem of size n/c. Up to constant factors (which we can
the array, say with rank between n/10 and 9n/10. This observation suggests that hide in the O( ) notation), the running time of this algorithm is governed by the
the “average-case” running time should be O(n log n). Although this intuition recurrence
can be formalized, the most common formalization makes the completely T (n) = r T (n/c) + f (n).
unrealistic assumption that all permutations of the input array are equally likely.
Real world data may be random, but it is not random in any way that we can The root of the recursion tree for T (n) has value f (n) and r children,
predict in advance, and it is certainly not uniform!7 each of which is the root of a (recursively defined) recursion tree for T (n/c).
Occasionally people also consider “best case” running time for some reason. Equivalently, a recursion tree is a complete r-ary tree where each node at depth d
We won’t. contains the value f (n/c d ). (Feel free to assume that n is an integer power of c,
so that n/c d is always an integer, although in fact this doesn’t matter.)
In practice, I recommend drawing out the first two or three levels of the
1.6 The Pattern tree, as in Figure 1.9.
Both mergesort and quicksort follow a general three-step pattern called divide f(n) f(n)
and conquer: +
r
1. Divide the given instance of the problem into several independent smaller
f(n/c) f(n/c) f(n/c) f(n/c) r ⋅ f(n/c)
instances of exactly the same problem.
r r r r +
2. Delegate each smaller instance to the Recursion Fairy.
f(n/c²) f(n/c²) f(n/c²) f(n/c²) r² ⋅ f(n/c²)
f(n/c²) f(n/c²) f(n/c²) f(n/c²)
3. Combine the solutions for the smaller instances into the final solution f(n/c²) f(n/c²) f(n/c²) f(n/c²)
f(n/c²) f(n/c²) f(n/c²) f(n/c²) +
for the given instance.
If the size of any instance falls below some constant threshold, we abandon
recursion and solve the problem directly, by brute force, in constant time. +
Proving a divide-and-conquer algorithm correct almost always requires f(n/c
f(n/c
L)
L) f(n/c
f(n/c
L)
L) f(n/c
f(n/c
L)
L) f(n/c
f(n/c
L)
L) f(n/c
f(n/c
L)
L) f(n/c
f(n/c
L)
L) f(n/c
f(n/c
L)
L) f(n/c
f(n/c
L)
L) rL ⋅ f(n/cL)
f(n/c L) f(n/c L) f(n/c L) f(n/c L) f(n/c L) f(n/c L) f(n/c L) f(n/c L)
f(n/c L) f(n/c L) f(n/c L) f(n/c L) f(n/c L) f(n/c L) f(n/c L) f(n/c L)
f(n/c L) f(n/c L) f(n/c L) f(n/c L) f(n/c L) f(n/c L) f(n/c L) f(n/c L)
induction. Analyzing the running time requires setting up and solving a f(n/c L L L L L L L L
f(n/cL)) f(n/c
f(n/cL)) f(n/c
f(n/cL)) f(n/c
f(n/cL)) f(n/c
f(n/cL)) f(n/c
f(n/cL)) f(n/c
f(n/cL)) f(n/c
f(n/cL))
recurrence, which usually (but unfortunately not always!) can be solved using
recursion trees. Figure 1.9. A recursion tree for the recurrence T (n) = r T (n/c) + f (n)

The leaves of the recursion tree correspond to the base case(s) of the
1.7 Recursion Trees recurrence. Because we’re only looking for asymptotic bounds, the precise base
case doesn’t actually matter; we can safely assume T (n) = 1 for all n ≤ n0 ,
So what are these “recursion trees” I keep talking about? Recursion trees are where n0 is an arbitrary positive constant. In particular, we can choose whatever
a simple, general, pictorial tool for solving divide-and-conquer recurrences. A value of n0 is most convenient for our analysis. For this example, I’ll choose
recursion tree is a rooted tree with one node for each recursive subproblem. The n0 = 1.
value of each node is the amount of time spent on the corresponding subproblem Now T (n) is the sum of all values in the recursion tree; we can evaluate this
excluding recursive calls. Thus, the overall running time of the algorithm is the sum by considering the tree level-by-level. For each integer i, the ith level of
sum of the values of all nodes in the tree.
the tree has exactly r i nodes, each with value f (n/c i ). Thus,
To make this idea more concrete, imagine a divide-and-conquer algorithm
that spends O( f (n)) time on non-recursive work, and then makes r recursive L
X
7
On the other hand, if we choose the pivot index p uniformly at random, then Quicksort runs
T (n) = r i · f (n/c i ) (Σ)
in O(n log n) time with high probability, for every possible input array. The key difference is that i=0
the randomness is controlled by our algorithm, not by the All-Powerful Malicious Adversary who
gives us input data after reading our code. The analysis of randomized quicksort is unfortunately where L is the depth of the tree. Our base case n0 = 1 immediately implies
outside the scope of this book, but you can find relevant lecture notes at [Link] L = logc n, because n/c L = n0 = 1. It follows that the number of leaves in

31 32
 1.7. Recursion Trees 1. RECURSION

the recursion tree is exactly r L = r logc n = nlogc r . Thus, the last term in the tree is log3 n = Ω(log n), so this conservative analysis can be improved by at
level-by-level sum (Σ) is nlogc r · f (1) = O(nlogc r ), because f (1) = O(1). most a constant factor, which for our purposes means not at all.) The fact that
There are three common cases where the level-by-level series (Σ) is especially the recursion tree is unbalanced simply doesn’t matter.
easy to evaluate: As a more extreme example, the worst-case recurrence for quicksort T (n) =
• Decreasing: If the series decays exponentially—every term is a constant T (n − 1) + T (1) + O(n) gives us a completely unbalanced recursion tree, where
factor smaller than the previous term—then T (n) = O( f (n)). In this case, one child of each internal node is a leaf. The level-by-level sum doesn’t fall
the sum is dominated by the value at the root of the recursion tree. into any of our three default categories, but we can still derive the solution
T (n) = O(n2 ) by observing that every level value is at most n and there are at
• Equal: If all terms in the series are equal, we immediately have T (n) =
most n levels. (Again, this conservative analysis is tight, because n/2 levels each
O( f (n)· L) = O( f (n) log n). (The constant c vanishes into the O( ) notation.)
have value at least n/2.)
• Increasing: If the series grows exponentially—every term is a constant factor
n n
larger than the previous term—then T (n) = O(nlogc r ). In this case, the sum
is dominated by the number of leaves in the recursion tree.
n/3 2n/3 n–1 1
In the first and third cases, only the largest term in the geometric series matters;
all other terms are swallowed up by the O(·) notation. In the decreasing case, n/9 2n/9 2n/9 4n/9 n–2 1
we don’t even have to compute L; the asymptotic upper bound would still hold
if the recursion tree were infinite! n–3 1
As an elementary example, if we draw out the first few levels of the recursion
tree for the (simplified) mergesort recurrence T (n) = 2T (n/2) + O(n), we Figure 1.11. Recursion trees for quicksort with good pivots (left) and with worst-case pivots (right)
discover that all levels are equal, which immediately implies T (n) = O(n log n).
n
ªIgnoring Floors and Ceilings Is Okay, Honest

n/2 n/2 Careful readers might object that our analysis brushes an important detail under
the rug. The running time of mergesort doesn’t really obey the recurrence
n/4 n/4 n/4 n/4 T (n) = 2T (n/2) + O(n); after all, the input size n might be odd, and what could
it possibly mean to sort an array of size 42 21 or 17 78 ? The actual mergesort
n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8 recurrence is somewhat messier:



Figure 1.10. The recursion tree for mergesort T (n) = T dn/2e + T bn/2c + O(n).

The recursion tree technique can also be used for algorithms where the Sure, we could check that T (n) = O(n log n) using induction, but the necessary
recursive subproblems have different sizes. For example, if we could somehow calculations would be awful. Fortunately, there is a simple technique for
implement quicksort so that the pivot always lands in the middle third of the removing floors and ceilings from recurrences, called domain transformation.
sorted array, the worst-case running time would satisfy the recurrence • First, because we are deriving an upper bound, we can safely overestimate
T (n), once by pretending that the two subproblem sizes are equal, and
T (n) ≤ T (n/3) + T (2n/3) + O(n). again to eliminate the ceiling:8


This recurrence might look scary, but it’s actually pretty tame. If we draw T (n) ≤ 2T dn/2e + n ≤ 2T (n/2 + 1) + n.
out a few levels of the resulting recursion tree, we quickly realize that the 8
Formally, we are treating T as a function over the reals, not just over the integers, that
sum of values on any level is at most n—deeper levels might be missing some satisfies the given recurrence with the base case T (n) = C for all n ≤ n0 , for some real numbers
nodes—and the entire tree has depth log3/2 n = O(log n). It immediately follows C ≥ 0 and n0 > 0 whose values don’t matter. If n happens to be an integer, then T (n) coincides
that T (n) = O(n log n). (Moreover, the number of full levels in the recursion with the running time of an algorithm on an input of size n, but that doesn’t matter, either.

33 34
 ª1.8. Linear-Time Selection 1. RECURSION

• Second, we define a new function S(n) = T (n + α), choosing the constant α QuickSelect(A[1 .. n], k):
so that S(n) satisfies the simpler recurrence S(n) ≤ 2S(n/2) + O(n). To if n = 1
find the correct constant α, we derive a recurrence for S from our given return A[1]
else
recurrence for T : Choose a pivot element A[p]
r ← Partition(A[1 .. n], p)
S(n) = T (n + α) [definition of S]
if k < r
≤ 2T (n/2 + α/2 + 1) + n + α [recurrence for T ] return QuickSelect(A[1 .. r − 1], k)
= 2S(n/2 − α/2 + 1) + n + α [definition of S] else if k > r
return QuickSelect(A[r + 1 .. n], k − r)
Setting α = 2 simplifies this recurrence to S(n) ≤ 2S(n/2) + n + 2, which is else
exactly what we wanted. return A[r]
Figure 1.12. Quickselect, or one-armed quicksort
• Finally, the recursion tree method implies S(n) = O(n log n), and therefore

T (n) = S(n − 2) = O((n − 2) log(n − 2)) = O(n log n), This algorithm has two important features. First, just like quicksort, the
correctness of quickselect does not depend on how the pivot is chosen. Second,
exactly as promised. even if we really only care about selecting medians (the special case k = n/2),
Similar domain transformations can be used to remove floors, ceilings, and even Hoare’s recursive strategy requires us to consider the more general selection
lower order terms from any divide and conquer recurrence. But now that we problem; the median of the input array A[1 .. n] is almost never the median of
realize this, we don’t need to bother grinding through the details ever again! either of the two smaller subarrays A[1 .. r − 1] or A[r + 1 .. n].
From now on, faced with any divide-and-conquer recurrence, I will silently The worst-case running time of QuickSelect obeys a recurrence similar to
brush floors and ceilings and lower-order terms under the rug, and I encourage QuickSort. We don’t know the value of r, or which of the two subarrays we’ll
you to do the same. recursively search, so we have to assume the worst.

T (n) ≤ max max {T (r − 1), T (n − r)} + O(n)

ª1.8 1≤r≤n
Linear-Time Selection
We can simplify the recurrence slightly by letting ` denote the length of the
During our discussion of quicksort, I claimed in passing that we can find the
recursive subproblem:
median of an unsorted array in linear time. The first such algorithm was
discovered by Manuel Blum, Bob Floyd, Vaughan Pratt, Ron Rivest, and Bob
T (n) ≤ max T (`) + O(n)
Tarjan in the early 1970s. Their algorithm actually solves the more general 0≤`≤n−1
problem of selecting the kth smallest element in an n-element array, given the
array and the integer k as input, using a variant of an algorithm called quickselect If the chosen pivot element is always either the smallest or largest element in
or one-armed quicksort. Quickselect was first described by Tony Hoare in 1961, the array, the recurrence simplifies to T (n) = T (n − 1) + O(n), which implies
literally on the same page where he first published quicksort. T (n) = O(n2 ). (The recursion tree for this recurrence is just a simple path.)

Quickselect Good pivots

The generic quickselect algorithm chooses a pivot element, partitions the array We could avoid this quadratic worst-case behavior if we could somehow magically
using the same Partition subroutine as QuickSort, and then recursively choose a good pivot, meaning ` ≤ αn for some constant α < 1. In this case, the
searches only one of the two subarrays, specifically, the one that contains the recurrence would simplify to
kth smallest element of the original input array. Pseudocode for quickselect is
given in Figure 1.12. T (n) ≤ T (αn) + O(n).

35 36
 ª1.8. Linear-Time Selection 1. RECURSION

This recurrence expands into a decreasing geometric series, which is dominated We can visualize the algorithm’s behavior by drawing the input array as a
by its largest term, so T (n) = O(n). (Again, the recursion tree is just a simple 5 × dn/5e grid, which each column represents five consecutive elements. For
path. The constant in the O(n) running time depends on the constant α.) purposes of illustration, imagine that we sort every column from top down, and
In other words, if we could somehow quickly find an element that’s even then we sort the columns by their middle element. (Let me emphasize that the
close to the median in linear time, we could find the exact median in linear algorithm does not actually do this!) In this arrangement, the median-of-medians
time. So now all we need is an Approximate Median Fairy. The Blum-Floyd- is the element closest to the center of the grid.
Pratt-Rivest-Tarjan algorithm chooses a good quickselect pivot by recursively
computing the median of a carefully-chosen subset of the input array. The
Approximate Median Fairy is just the Recursion Fairy in disguise!
Specifically, we divide the input array into dn/5e blocks, each containing
exactly 5 elements, except possibly the last. (If the last block isn’t full, just throw
in a few ∞s.) We compute the median of each block by brute force, collect
those medians into a new array M [1 .. dn/5e], and then recursively compute
The left half of the first three rows of the grid contains 3n/10 elements, each
the median of this new array. Finally, we use the median of the block medians
of which is smaller than mom. If the element we’re looking for is larger than
(called “mom” in the pseudocode below) as the quickselect pivot.
mom, our algorithm will throw away everything smaller than mom, including
MomSelect(A[1 .. n], k): those 3n/10 elements, before recursing. Thus, the input to the recursive
if n ≤ 25 〈〈or whatever〉〉 subproblem contains at most 7n/10 elements. A symmetric argument implies
use brute force that if our target element is smaller than mom, we discard at least 3n/10
else elements larger than mom, so the input to our recursive subproblem has at most
m ← dn/5e
7n/10 elements.
for i ← 1 to m
M[i] ← MedianOfFive(A[5i − 4 .. 5i]) 〈〈Brute force!〉〉
mom ← MomSelect(M[1 .. m], bm/2c) 〈〈Recursion!〉〉
r ← Partition(A[1 .. n], mom)
if k < r
return MomSelect(A[1 .. r − 1], k) 〈〈Recursion!〉〉
else if k > r
return MomSelect(A[r + 1 .. n], k − r) 〈〈Recursion!〉〉
else Okay, so mom is a good pivot, but our algorithm still makes two recursive
return mom calls instead of just one; how do we prove linear time? The second key insight is
that the total size of the two recursive subproblems is a constant factor smaller
MomSelect uses recursion for two different purposes; the first time to than the size of the original input array. The worst-case running time of the
choose a pivot element (mom), and the second time to search through the algorithm obeys the recurrence
entries on one side of that pivot.
T (n) ≤ T (n/5) + T (7n/10) + O(n).
Analysis
If we draw out the recursion tree for this recurrence, we observe that the total
But why is this fast? The first key  is that the median of medians is a
 insight work at each level of the recursion tree is at most 9/10 the total work at the
good pivot. Mom is larger than dn/5e/2 − 1 ≈ n/10 block medians, and each
previous level. Thus, the level sums decay exponentially, giving us the solution
block median is larger than two other elements in its block. Thus, mom is bigger
T (n) = O(n). (Again, the fact that the recursion tree is unbalanced is completely
than at least 3n/10 elements in the input array; symmetrically, mom is smaller
immaterial.) Hooray! Thanks, Mom!
than at least 3n/10 elements. Thus, in the worst case, the second recursive call
searches an array of size at most 7n/10.

37 38
 ª1.8. Linear-Time Selection 1. RECURSION

n n 1.9 Fast Multiplication

n/5 7n/10 n/3 2n/3 In the previous chapter, we saw two ancient algorithms for multiplying two
n-digit numbers in O(n2 ) time: the grade-school lattice algorithm and the
n/25 7n/50 7n/50 49n/100 n/9 2n/9 2n/9 4n/9 Egyptian peasant algorithm.
Maybe we can get a more efficient algorithm by splitting the digit arrays in
Figure 1.13. The recursion trees for MomSelect and a similar selection algorithm with blocks of size 3
half and exploiting the following identity:

(10m a + b)(10m c + d) = 102m ac + 10m (bc + ad) + bd

Sanity Checking
This recurrence immediately suggests the following divide-and-conquer algo-
At this point, many students ask about that magic constant 5. Why did we
rithm to multiply two n-digit numbers x and y. Each of the four sub-products
choose that particular block size? The answer is that 5 is the smallest odd
ac, bc, ad, and bd is computed recursively, but the multiplications in the last
block size that gives us exponential decay in the recursion-tree analysis! (Even
line are not recursive, because we can multiply by a power of ten by shifting the
block sizes introduce additional complications.) If we had used blocks of size 3
digits to the left and filling in the correct number of zeros, all in O(n) time.
instead, the running-time recurrence would be
T (n) ≤ T (n/3) + T (2n/3) + O(n). SplitMultiply(x, y, n):
if n = 1
We’ve seen this recurrence before! Every level of the recursion tree has total return x · y
value at most n, and the depth of the recursion tree is log3/2 n = O(log n), so else
the solution to this recurrence is T (n) ≤ O(n log n). (Moreover, this analysis is m ← dn/2e
a ← bx/10m c; b ← x mod 10m 〈〈x = 10m a + b〉〉
tight, because the recursion tree has log3 n complete levels.) Median-of-medians
c ← b y/10m c; d ← y mod 10m 〈〈 y = 10m c + d〉〉
selection using 3-element blocks is no faster than sorting.
e ← SplitMultiply(a, c, m)
Finer analysis reveals that the constant hidden by the O( ) notation is quite f ← SplitMultiply(b, d, m)
large, even if we count only comparisons. Selecting the median of 5 elements g ← SplitMultiply(b, c, m)
requires at most 6 comparisons, so we need at most 6n/5 comparisons to set h ← SplitMultiply(a, d, m)
up the recursive subproblem. Naïvely partitioning the array after the recursive return 102m e + 10m (g + h) + f
call would require n − 1 comparisons, but we already know 3n/10 elements
Correctness of this algorithm follows easily by induction. The running time for
larger than the pivot and 3n/10 elements smaller than the pivot, so partitioning
this algorithm follows the recurrence
actually requires only 2n/5 additional comparisons. Thus, a more precise
recurrence for the worst-case number of comparisons is T (n) = 4T (dn/2e) + O(n).
T (n) ≤ T (n/5) + T (7n/10) + 8n/5.
The recursion tree method transforms this recurrence into an increasing geo-
The recursion tree method implies the upper bound metric series, which implies T (n) = O(nlog2 4 ) = O(n2 ). In fact, this algorithm
multiplies each digit of x with each digit of y, just like the lattice algorithm.
8n X 9 i 8n
 ‹
T (n) ≤ = · 10 = 16n. So I guess that didn’t work. Too bad. It was a nice idea.
5 i≥0 10 5
In the mid-1950s, Andrei Kolmogorov, one of the giants of 20th century
In practice, median-of-medians selection is not as slow as this worst-case analysis mathematics, publicly conjectured that there is no algorithm to multiply two
predicts—getting a worst-case pivot at every level of recursion is incredibly n-digit numbers in subquadratic time. Kolmogorov organized a seminar at
unlikely—but it is still slower than sorting for even moderately large arrays.9 Moscow University in 1960, where he restated his “n2 conjecture” and posed
9
In fact, the right way to choose the pivot element in practice is to choose it uniformly at
several related problems that he planned to discuss at future meetings. Almost
random. Then the expected number of comparisons required to find the median is at most 4n. exactly a week later, a 23-year-old student named Anatoliı̆ Karatsuba presented
See my randomized algorithms lecture notes at [Link] for more details. Kolmogorov with a remarkable counterexample. According to Karatsuba himself,

39 40
 1.9. Fast Multiplication 1. RECURSION

n Karatsuba’s algorithm arguably launched the design and analysis of algorithms

as a formal field of study.
n/2 n/2 n/2 n/2
n
n/4 n/4 n/4 n/4 n/4 n/4 n/4 n/4 n/4 n/4 n/4 n/4 n/4 n/4 n/4 n/4
n/2 n/2 n/2

Figure 1.14. The recursion tree for naïve divide-and-conquer multiplication

n/4 n/4 n/4 n/4 n/4 n/4 n/4 n/4 n/4

After the seminar I told Kolmogorov about the new algorithm and about the
disproof of the n2 conjecture. Kolmogorov was very agitated because this Figure 1.15. The recursion tree for Karatsuba’s divide-and-conquer multiplication algorithm
contradicted his very plausible conjecture. At the next meeting of the semi-
nar, Kolmogorov himself told the participants about my method, and at that We can take Karatsuba’s idea even further, splitting the numbers into
point the seminar was terminated. more pieces and combining them in more complicated ways, to obtain even
Karatsuba observed that the middle coefficient bc +ad can be computed from the faster multiplication algorithms. Andrei Toom discovered an infinite family
other two coefficients ac and bd using only one more recursive multiplication, of algorithms that split any integer into k parts, each with n/k digits, and
via the following algebraic identity: then compute the product using only 2k − 1 recursive multiplications; Toom’s
algorithms were further simplified by Stephen Cook in his PhD thesis. For any
ac + bd − (a − b)(c − d) = bc + ad
fixed k, the Toom-Cook algorithm runs in O(n1+1/(lg k) ) time, where the hidden
This trick lets us replace the four recursive calls in the previous algorithm with constant in the O(·) notation depends on k.
only three recursive calls, as shown below: Ultimately, this divide-and-conquer strategy led Gauss (yes, really) to the
FastMultiply(x, y, n): discovery of the Fast Fourier transform.11 The basic FFT algorithm itself
if n = 1 runs in O(n log n) time; however, using FFTs for integer multiplication incurs
return x · y some small additional overhead. The first FFT-based integer multiplication
else algorithm, published by Arnold Schönhage and Volker Strassen in 1971, runs
m ← dn/2e in O(n log n log log n) time. Schönhage-Strassen remained the theoretically
a ← bx/10m c; b ← x mod 10m 〈〈x = 10m a + b〉〉
fastest integer multiplication algorithm for several decades, before Martin Fürer
c ← b y/10m c; d ← y mod 10m 〈〈 y = 10m c + d〉〉
discovered the first of a long series of technical improvements. Finally, in 2019,
e ← FastMultiply(a, c, m)
David Harvey and Joris van der Hoeven published an algorithm that runs in
f ← FastMultiply(b, d, m)
g ← FastMultiply(a − b, c − d, m) O(n log n) time.12
return 102m e + 10m (e + f − g) + f

The running time of Karatsuba’s FastMultiply algorithm follows the recurrence 1.10 Exponentiation
T (n) ≤ 3T (dn/2e) + O(n)
Given a number a and a positive integer n, suppose we want to compute a n . The
Once again, the recursion tree method transforms this recurrence into an standard naïve method is a simple for-loop that performs n − 1 multiplications
increasing geometric series, but the new solution is only T (n) = O(nlog2 3 ) = by a:
O(n 1.58496 ), a significant improvement over our earlier quadratic time bound.10
10 11
My presentation simplifies the actual history slightly. In fact, Karatsuba proposed an See [Link] for lecture notes on Fast Fourier transforms.
algorithm based on the formula (a + b)(c + d) − ac − bd = bc + ad. This algorithm also runs 12
Schönhage-Strassen is actually the fastest algorithm in practice for multiplying integers with
in O(nlg 3 ) time, but the actual recurrence is slightly messier: a − b and c − d are still m-digit more than about 75000 digits; the more recent algorithms of Fürer, Harvey, van der Hoeven, and
numbers, but a + b and c + d might each have m + 1 digits. The simplification presented here is others would be faster “in practice” only for integers with more digits than there are particles in
due to Donald Knuth. the universe.

41 42
 1.10. Exponentiation 1. RECURSION

SlowPower(a, n): PeasantPower(a, n):

x←a if n = 1
for i ← 2 to n return a
x ← x ·a else if n is even
return x return PeasantPower(a2 , n/2)
else
This iterative algorithm requires n multiplications. return PeasantPower(a2 , bn/2c) · a
The input parameter a could be an integer, or a rational, or a floating point
number. In fact, it doesn’t need to be a number at all, as long as it’s something This algorithm—which might reasonably be called “squaring and mediation”—
that we know how to multiply. For example, the same algorithm can be used also performs only O(log n) multiplications.
to compute powers modulo some finite number (an operation commonly used Both of these algorithms are asymptotically optimal; any algorithm that
in cryptography algorithms) or to compute powers of matrices (an operation computes a n must perform at least Ω(log n) multiplications, because each
used to evaluate recurrences and to compute shortest paths in graphs). Because multiplication at most doubles the largest power computed so far. In fact,
we don’t know what kind of object we’re multiplying, we can’t know how much when n is a power of two, both of these algorithms require exactly log2 n
time a single multiplication requires, so we’re forced to analyze the running multiplications, which is exactly optimal. However, there are slightly faster
time in terms of the number of multiplications. methods for other values of n. For example, PiṅgalaPower and PeasantPower
There is a much faster divide-and-conquer method, originally proposed by each compute a15 using six multiplications, but in fact only five multiplications
the Indian prosodist Piṅgala in the 2nd century bce, which uses the following are necessary:
simple recursive formula: • Piṅgala: a → a2 → a3 → a6 → a7 → a14 → a15
• Peasant: a → a2 → a4 → a8 → a12 → a14 → a15

1
 if n = 0
• Optimal: a → a2 → a3 → a5 → a10 → a15
n
a = (a ) n/2 2
if n > 0 and n is even
(abn/2c )2 · a otherwise
 It is a long-standing open question whether the absolute minimum number of
multiplications for a given exponent n can be computed efficiently.
PiṅgalaPower(a, n):
if n = 1
return a Exercises
else
x ← PiṅgalaPower(a, bn/2c) Tower of Hanoi
if n is even
1. Prove that the original recursive Tower of Hanoi algorithm performs exactly
return x · x
else the same sequence of moves—the same disks, to and from the same pegs,
return x · x · a in the same order—as each of the following non-recursive algorithms. The
pegs are labeled 0, 1, and 2, and our problem is to move a stack of n disks
The total number of multiplications performed by this algorithm satisfies the from peg 0 to peg 2 (as shown on page 24).
recurrence T (n) ≤ T (n/2) + 2. The recursion-tree method immediately give us
the solution T (n) = O(log n). (a) If n is even, swap pegs 1 and 2. At the ith step, make the only legal
move that avoids peg i mod 3. If there is no legal move, then all disks
A nearly identical exponentiation algorithm can also be derived directly
from the Egyptian peasant multiplication algorithm from the previous chapter, are on peg i mod 3, and the puzzle is solved.
by replacing addition with multiplication (and in particular, replacing duplation (b) For the first move, move disk 1 to peg 1 if n is even and to peg 2 if n is
with squaring). odd. Then repeatedly make the only legal move that involves a different
 disk from the previous move. If no such move exists, the puzzle is solved.
1 if n = 0
(c) Pretend that disks n + 1, n + 2, and n + 3 are at the bottom of pegs 0, 1,

n
a = (a ) 2 n/2
if n > 0 and n is even and 2, respectively. Repeatedly make the only legal move that satisfies
(a2 )bn/2c · a otherwise

the following constraints, until no such move is possible.

43 44
 Exercises 1. RECURSION

• Do not place an odd disk directly on top of another odd disk. The Baguenaudier puzzle has many physical forms, but one of the most
• Do not place an even disk directly on top of another even disk. common consists of a long metal loop and several rings, which are connected
to a solid base by movable rods. The loop is initially threaded through the
• Do not undo the previous move.
rings as shown in Figure 1.16; the goal of the puzzle is to remove the loop.
(d) Let ρ(n) denote the smallest integer k such that n/2k is not an integer. More abstractly, we can model the puzzle as a sequence of bits, one
For example, ρ(42) = 2, because 42/21 is an integer but 42/22 is not. for each ring, where the ith bit is 1 if the loop passes through the ith ring
(Equivalently, ρ(n) is one more than the position of the least significant 1 and 0 otherwise. (Here we index the rings from right to left, as shown in
in the binary representation of n.) Because its behavior resembles the Figure 1.16.) The puzzle allows two legal moves:
marks on a ruler, ρ(n) is sometimes called the ruler function.
• You can always flip the 1st (= rightmost) bit.
RulerHanoi(n):
i←1 • If the bit string ends with exactly z 0s, you can flip the (z + 2)th bit.
while ρ(i) ≤ n The goal of the puzzle is to transform a string of n 1s into a string of n 0s.
if n − i is even For example, the following sequence of 21 moves solves the 5-ring puzzle:
move disk ρ(i) forward 〈〈0 → 1 → 2 → 0〉〉
1 3 1 2 1
else 11111 → 11110 → 11010 → 11011 → 11001 → 11000
move disk ρ(i) backward 〈〈0 → 2 → 1 → 0〉〉
5 1 2 1 3
i ← i+1 → 01000 → 01001 → 01011 → 01010 → 01110
1 2 1 4 1
2. The Tower of Hanoi is a relatively recent descendant of a much older → 01111 → 01101 → 01100 → 00100 → 00101
2 1 3 1 2 1
mechanical puzzle known as the Chinese linked rings, Baguenaudier, Car- → 00111 → 00110 → 00010 → 00011 → 00001 → 00000
dan’s Rings, Meleda, Patience, Tiring Irons, Prisoner’s Lock, Spin-Out, and
©
many other names. This puzzle was already well known in both China (a) Call a sequence of moves reduced if no move is the inverse of the previous
and Europe by the 16th century. The Italian mathematician Luca Pacioli move. Prove that for any non-negative integer n, there is exactly one
described the 7-ring puzzle and its solution in his unpublished treatise De reduced sequence of moves that solves the n-ring Baguenaudier puzzle.
Viribus Quantitatis, written between 1498 and 1506;13 only a few years later, [Hint: This problem is much easier if you’re already familiar with
the Ming-dynasty poet Yang Shen described the 9-ring puzzle as “a toy for graphs.]
women and children”. The puzzle is apocryphally attributed to a 2nd-century (b) Describe an algorithm to solve the Baguenaudier puzzle. Your input is
Chinese general, who gave the puzzle to his wife to occupy her time while the number of rings n; your algorithm should print a reduced sequence
he was away at war. of moves that solves the puzzle. For example, given the integer 5 as
input, your algorithm should print the sequence 1, 3, 1, 2, 1, 5, 1, 2, 1, 3,
1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1.
(c) Exactly how many moves does your algorithm perform, as a function
of n? Prove your answer is correct.

3. A less familiar chapter in the Tower of Hanoi’s history is its brief relocation
of the temple from Benares to Pisa in the early 13th century.14 The relocation
Figure 1.16. The 7-ring Baguenaudier, from Récréations Mathématiques by Édouard Lucas (1891) (See
was organized by the wealthy merchant-mathematician Leonardo Fibonacci,
Image Credits at the end of the book.) at the request of the Holy Roman Emperor Frederick II, who had heard
reports of the temple from soldiers returning from the Crusades. The Towers
13
De Viribus Quantitatis [On the Powers of Numbers] is an important early work on recreational of Pisa and their attendant monks became famous, helping to establish Pisa
mathematics and perhaps the oldest surviving treatise on magic. Pacioli is better known for as a dominant trading center on the Italian peninsula.
Summa de Aritmetica, a near-complete encyclopedia of late 15th-century mathematics, which
14
included the first description of double-entry bookkeeping. Portions of this story are actually true.

45 46
 Exercises 1. RECURSION

Unfortunately, almost as soon as the temple was moved, one of the

diamond needles began to lean to one side. To avoid the possibility of
the leaning tower falling over from too much use, Fibonacci convinced the
priests to adopt a more relaxed rule: Any number of disks on the leaning 0 1 2 3 4
needle can be moved together to another needle in a single move. It was
still forbidden to place a larger disk on top of a smaller disk, and disks had to
be moved one at a time onto the leaning needle or between the two vertical
needles.
5 6 7 8 9

Figure 1.18. The first several moves in a counterclockwise Towers of Hanoi solution.

¨ª
(c) Finally, suppose your only restriction is that you may never move a disk
directly from peg 0 to peg 2. Describe an algorithm to solve this version
of the puzzle in as few moves as possible. How many moves does your
Figure 1.17. The Towers of Pisa. In the fifth move, two disks are taken off the leaning needle.
algorithm make? [Hint: Matrices! This variant is considerably harder
to analyze than the other two.]
Thanks to Fibonacci’s new rule, the priests could bring about the end
of the universe somewhat faster from Pisa than they could from Benares.
5. Consider the following more complex variant of the Tower of Hanoi puzzle
Fortunately, the temple was moved from Pisa back to Benares after the
The puzzle has a row of k pegs, numbered from 1 to k. In a single turn, you
newly crowned Pope Gregory IX excommunicated Frederick II, making
are allowed to move the smallest disk on peg i to either peg i − 1 or peg i + 1,
the local priests less sympathetic to hosting foreign heretics with strange
for any index i; as usual, you are not allowed to place a bigger disk on a
mathematical habits. Soon afterward, a bell tower was erected on the spot
where the temple once stood; it too began to lean almost immediately. smaller disk. Your mission is to move a stack of n disks from peg 1 to peg k.

Describe an algorithm to transfer a stack of n disks from one vertical

(a) Describe a recursive algorithm for the case k = 3. Exactly how many
needle to the other vertical needle, using the smallest possible number of
moves does your algorithm make? (This is exactly the same as problem
moves. Exactly how many moves does your algorithm perform?
4(a).)
4. Consider the following restricted variants of the Tower of Hanoi puzzle In (b) Describe a recursive algorithm for the case k = n + 1 that requires at
each problem, the pegs are numbered 0, 1, and 2, and your task is to move most O(n3 ) moves. [Hint: Use part (a).]
a stack of n disks from peg 0 to peg 2, exactly as in problem 1.
ª
(c) Describe a recursive algorithm for the case k = n + 1 that requires at
(a) Suppose you are forbidden to move any disk directly between peg 1 and
most O(n2 ) moves. [Hint: Don’t use part (a).]
peg 2; every move must involve peg 0. Describe an algorithm to solve
this version of the puzzle in as few moves as possible. Exactly how many p
ª
(d) Describe a recursive algorithm for the case k = n that requires at most
moves does your algorithm make?
a polynomial number of moves. (Which polynomial??)
¨ª
(b) Suppose you are only allowed to move disks from peg 0 to peg 2, from
peg 2 to peg 1, or from peg 1 to peg 0. Equivalently, suppose the pegs ª(e) Describe and analyze a recursive algorithm for arbitrary n and k. How
are arranged in a circle and numbered in clockwise order, and you are small must k be (as a function of n) so that the number of moves is
only allowed to move disks counterclockwise. Describe an algorithm to bounded by a polynomial in n?
solve this version of the puzzle in as few moves as possible. How many
moves does your algorithm make?

47 48
 Exercises 1. RECURSION

Recursion Trees (b) For every positive integer n, describe a stack of n pancakes that requires
Ω(n) flips to sort.
6. Use recursion trees to solve each of the following recurrences.
(c) Now suppose one side of each pancake is burned. Describe an algorithm
p
A(n) = 2A(n/4) + n B(n) = 2B(n/4) + n C(n) = 2C(n/4) + n2 to sort an arbitrary stack of n pancakes, so that the burned side of every
p pancake is facing down, using O(n) flips. Exactly how many flips does
D(n) = 3D(n/3) + n E(n) = 3E(n/3) + n F (n) = 3F (n/3) + n2
p your algorithm perform in the worst case?
G(n) = 4G(n/2) + n H(n) = 4H(n/2) + n I(n) = 4I(n/2) + n2
10. Recall that the median-of-three heuristic examines the first, last, and middle
7. Use recursion trees to solve each of the following recurrences.
element of the array, and uses the median of those three elements as a
(j) J(n) = J(n/2) + J(n/3) + J(n/6) + n quicksort pivot. Prove that quicksort with the median-of-three heuristic
(k) K(n) = K(n/2) + 2K(n/3) + 3K(n/4) + n2 requires Ω(n2 ) time to sort an array of size n in the worst case. Specifically,
p for any integer n, describe a permutation of the integers 1 through n,
(l) L(n) = L(n/15) + L(n/10) + 2L(n/6) + n
such that in every recursive call to median-of-three-quicksort, the pivot is
ª always the second smallest element of the array. Designing this permutation
8. Use recursion trees to solve each of the following recurrences.
requires intimate knowledge of the Partition subroutine.
(m) M (n) = 2M (n/2) + O(n log n)
(a) As a warm-up exercise, assume that the Partition subroutine is stable,
(n) N (n) = 2N (n/2) + O(n/ log n)
p p meaning it preserves the existing order of all elements smaller than the
(p) P(n) = n P( n) + n pivot, and it preserves the existing order of all elements smaller than
p p p
(q) Q(n) = 2n Q( 2n) + n the pivot.
ª
(b) Assume that the Partition subroutine uses the specific algorithm listed
Sorting on page 29, which is not stable.
9. Suppose you are given a stack of n pancakes of different sizes. You want to 11. (a) Hey, Moe! Hey, Larry! Prove that the following algorithm actually sorts
sort the pancakes so that smaller pancakes are on top of larger pancakes. its input!
The only operation you can perform is a flip—insert a spatula under the
StoogeSort(A[0 .. n − 1]) :
top k pancakes, for some integer k between 1 and n, and flip them all over. if n = 2 and A[0] > A[1]
swap A[0] ↔ A[1]
else if n > 2
m = d2n/3e
StoogeSort(A[0 .. m − 1])
StoogeSort(A[n − m .. n − 1])
StoogeSort(A[0 .. m − 1])
(b) Would StoogeSort still sort correctly if we replaced m = d2n/3e with
m = b2n/3c? Justify your answer.
Figure 1.19. Flipping the top four pancakes. (c) State a recurrence (including the base case(s)) for the number of
comparisons executed by StoogeSort.
(a) Describe an algorithm to sort an arbitrary stack of n pancakes using (d) Solve the recurrence, and prove that your solution is correct. [Hint:
O(n) flips. Exactly how many flips does your algorithm perform in the Ignore the ceiling.]
worst case?15 [Hint: This problem has nothing to do with the Tower of n


(e) Prove that the number of swaps executed by StoogeSort is at most 2 .
Hanoi.]
15
The exact worst-case optimal number of flips required to sort n pancakes (either burned or 12. The following cruel and unusual sorting algorithm was proposed by Gary
unburned) is an long-standing open problem; just do the best you can. Miller:

49 50
 Exercises 1. RECURSION

Cruel(A[1 .. n]): point qi . Describe and analyze a divide-and-conquer algorithm to

if n > 1 determine how many pairs of these line segments intersect in O(n log2 n)
Cruel(A[1 .. n/2])
time. [Hint: Use your solution to part (a).]
Cruel(A[n/2 + 1 .. n])
ª
Unusual(A[1 .. n]) (c) Describe an algorithm for part (b) that runs in O(n log n) time. [Hint:
Unusual(A[1 .. n]): Use your solution from part (b)!]
if n = 2 p3
q7
if A[1] > A[2] 〈〈the only comparison!〉〉 p4
swap A[1] ↔ A[2] q5 q1 q2 q4 q7 q3 q6 q6
else
for i ← 1 to n/4 〈〈swap 2nd and 3rd quarters〉〉 q4
p1
swap A[i + n/4] ↔ A[i + n/2]
Unusual(A[1 .. n/2]) 〈〈recurse on left half 〉〉 p2
Unusual(A[n/2 + 1 .. n]) 〈〈recurse on right half 〉〉 p5
p1 p7 p4 p3 p6 p2 p5 q1
Unusual(A[n/4 + 1 .. 3n/4]) 〈〈recurse on middle half 〉〉
q2
p6
The comparisons performed by this algorithm do not depend at all on p7 q3 q5

the values in the input array; such a sorting algorithm is called oblivious. Figure 1.20. Eleven intersecting pairs of segments with endpoints on parallel lines, and ten intersecting
Assume for this problem that the input size n is always a power of 2. pairs of segments with endpoints on a circle.

(a) Prove by induction that Cruel correctly sorts any input array. [Hint:
Consider an array that contains n/4 1s, n/4 2s, n/4 3s, and n/4 4s. Why 15. (a) Describe an algorithm that sorts an input array A[1  .. n] by calling a
p 
is this special case enough?] subroutine SqrtSort(k), which sorts the subarray A k + 1 .. k + n in
p
(b) Prove that Cruel would not correctly sort if we removed the for-loop place, given an arbitrary integer k between 0 and n − n as input. (To
p
from Unusual. simplify the problem, assume that n is an integer.) Your algorithm is
(c) Prove that Cruel would not correctly sort if we swapped the last two only allowed to inspect or modify the input array by calling SqrtSort;
lines of Unusual. in particular, your algorithm must not directly compare, move, or copy
array elements. How many times does your algorithm call SqrtSort in
(d) What is the running time of Unusual? Justify your answer.
the worst case?
(e) What is the running time of Cruel? Justify your answer. ¨
(b) Prove that your algorithm from part (a) is optimal up to constant factors.
13. An inversion in an array A[1 .. n] is a pair of indices (i, j) such that i < j and In other words, if f (n) is the number of times your algorithm calls
A[i] > A[ j]. The number of inversions in an n-element array is between 0 SqrtSort, prove that no algorithm can sort using o( f (n)) calls to
n


(if the array is sorted) and 2 (if the array is sorted backward). Describe SqrtSort.
and analyze an algorithm to count the number of inversions in an n-element (c) Now suppose SqrtSort is implemented recursively, by calling your
array in O(n log n) time. [Hint: Modify mergesort.] sorting algorithm from part (a). For example, at the second level of
recursion, the algorithm is sorting arrays roughly of size n1/4 . What
14. (a) Suppose you are given two sets of n points, one set {p1 , p2 , . . . , pn } on the is the worst-case running time of the resulting sorting algorithm? (To
line y = 0 and the other set {q1 , q2 , . . . , qn } on the line y = 1. Create a set k
simplify the analysis, assume that the array size n has the form 22 , so
of n line segments by connect each point pi to the corresponding point qi . that repeated square roots are always integers.)
Describe and analyze a divide-and-conquer algorithm to determine how
many pairs of these line segments intersect, in O(n log n) time. [Hint:
See the previous problem.] Selection
(b) Now suppose you are given two sets {p1 , p2 , . . . , pn } and {q1 , q2 , . . . , qn } 16. Suppose we are given a set S of n items, each with a value and a weight. For
of n points on the unit circle. Connect each point pi to the corresponding any element x ∈ S, we define two subsets

51 52
 Exercises 1. RECURSION

• S<x is the set of elements of S whose value is less than the value of x. Mom b Select(A[1 .. n], k):
• S>x is the set of elements of S whose value is more than the value of x. if n ≤ b2
use brute force
For any subset R ⊆ S, let w(R) denote the sum of the weights of elements in R. else
The weighted median of R is any element x such that w(S<x ) ≤ w(S)/2 m ← dn/be
and w(S>x ) ≤ w(S)/2. for i ← 1 to m
M [i] ← MedianOfB(A[b(i − 1) + 1 .. bi])
Describe and analyze an algorithm to compute the weighted median
mom b ← Mom b Select(M [1 .. m], bm/2c)
of a given weighted set in O(n) time. Your input consists of two unsorted
arrays S[1 .. n] and W [1 .. n], where for each index i, the ith element has r ← Partition(A[1 .. n], mom b )
value S[i] and weight W [i]. You may assume that all values are distinct and if k < r
all weights are positive. return Mom b Select(A[1 .. r − 1], k)
else if k > r
return Mom b Select(A[r + 1 .. n], k − r)
17. (a) Describe an algorithm to determine in O(n) time whether an arbitrary else
array A[1 .. n] contains more than n/4 copies of any value. return mom b
(b) Describe and analyze an algorithm to determine, given an arbitrary Figure 1.22. A parametrized family of selection algorithms; see problem 19.
array A[1 .. n] and an integer k, whether A contains more than k copies
of any value. Express the running time of your algorithm as a function (a) State a recurrence for the running time of Mom b Select, assuming that b
of both n and k. is a constant (so the subroutine MedianOfB runs in O(1) time). In
Do not use hashing, or radix sort, or any other method that depends particular, how do the sizes of the recursive subproblems depend on the
on the precise input values, as opposed to their order. constant b? Consider even b and odd b separately.
(b) What is the worst-case running time of Mom1 Select? [Hint: This is a
18. Describe an algorithm to compute the median of an array A[1 .. 5] of distinct trick question.]
numbers using at most 6 comparisons. Instead of writing pseudocode, ¨ª
(c) What is the worst-case running time of Mom2 Select? [Hint: This is an
describe your algorithm using a decision tree: A binary tree where each
unfair question!]
internal node contains a comparison of the form “A[i] ≷ A[ j]?” and each ª
leaf contains an index into the array. (d) What is the worst-case running time of Mom3 Select? Finding an upper
bound on the running time is straightforward; the hard part is showing
A[1]:A[2] that this analysis is actually tight. [Hint: See problem 10.]
< > ª
(e) What is the worst-case running time of Mom4 Select? Again, the hard
A[1]:A[3] A[1]:A[3]
part is showing that the analysis cannot be improved.16
< > < >
(f) For any constants b ≥ 5, the algorithm Mom b Select runs in O(n) time,
A[2]:A[3] A[2]:A[3]
A[1] A[1] but different values of b lead to different constant factors. Let M (b)
< > < >
denote the minimum number of comparisons required to find the median
A[2] A[3] A[3] A[2] of b numbers. The exact value of M (b) is known only for b ≤ 13:

Figure 1.21. Finding the median of a 3-element array using at most 3 comparisons b 1 2 3 4 5 6 7 8 9 10 11 12 13
M (b) 0 1 3 4 6 8 10 12 14 16 18 20 23
16
19. Consider the generalization of the Blum-Floyd-Pratt-Rivest-Tarjan Mom- The median of four elements is either the second smallest or the second largest. In 2014,
Ke Chen and Adrian Dumitrescu proved that if we modify Mom4 Select to find second-smallest
Select algorithm shown in Figure 1.22, which partitions the input array into
elements when k < n/2 and second-largest elements when k > n/2, the resulting algorithm runs
dn/be blocks of size b, instead of dn/5e blocks of size 5, but is otherwise in O(n) time! See their paper “Select with Groups of 3 or 4 Takes Linear Time” (WADS 2015,
identical. arXiv:1409.3600) for details.

53 54
 Exercises 1. RECURSION

For each b between 5 and 13, find an upper bound on the running time (d) Finally, suppose we are given a two dimensional array A[1 .. m, 1 .. n] in
of Mom b Select of the form T (n) ≤ α b n for some explicit constant α b . which every row A[i, ·] is sorted, and an integer k. Describe an algorithm
(For example, on page 39 we showed that α5 ≤ 16.) to find the kth smallest element in A as quickly as possible. How does
(g) Which value of b yields the smallest constant α b ? [Hint: This is a trick the running time of your algorithm depend on m? [Hint: Solve problem
question!] 16 first.]

20. Prove that the variant of the Blum-Floyd-Pratt-Rivest-Tarjan Select algo- Arithmetic
rithm shown in Figure 1.23, which uses an extra layer of small medians to
choose the main pivot, runs in O(n) time. 22. In 1854, archaeologists discovered Sumerians clay tablets, carved around
2000bce, that list the squares of integers up to 59. This discovery led some
MomomSelect(A[1 .. n], k):
scholars to conjecture that ancient Sumerians performed multiplication by
if n ≤ 81
reduction to squaring, using an identity like x · y = (x 2 + y 2 − (x − y)2 )/2.
use brute force
else
Unfortunately, those same scholars are silent on how the Sumerians sup-
m ← dn/3e posedly squared larger numbers. Four thousand years later, we can finally
for i ← 1 to m rescue these Sumerian mathematicians from their lives of drudgery through
M [i] ← MedianOf3(A[3i − 2 .. 3i]) the power of recursion!
mm ← dm/3e
(a) Describe a variant of Karatsuba’s algorithm that squares any n-digit
for j ← 1 to mm
Mom[ j] ← MedianOf3(M [3 j − 2 .. 3 j])
number in O(nlg 3 ) time, by reducing to squaring three dn/2e-digit
numbers. (Karatsuba actually did this in 1960.)
momom ← MomomSelect(Mom[1 .. mm], bmm/2c)
r ← Partition(A[1 .. n], momom) (b) Describe a recursive algorithm that squares any n-digit number in
if k < r O(nlog3 6 ) time, by reducing to squaring six dn/3e-digit numbers.
return MomomSelect(A[1 .. r − 1], k) ª
(c) Describe a recursive algorithm that squares any n-digit number in
else if k > r
return MomomSelect(A[r + 1 .. n], k − r) O(nlog3 5 ) time, by reducing to squaring only five (n/3 + O(1))-digit
else numbers. [Hint: What is (a + b + c)2 + (a − b + c)2 ?]
return momom
Figure 1.23. Selection by median of moms; see problem 20). 23. (a) Describe and analyze a variant of Karatsuba’s algorithm that multi-
plies any m-digit number and any n-digit number, for any n ≥ m, in
O(nmlg 3−1 ) time.
21. (a) Suppose we are given two sorted arrays A[1 .. n] and B[1 .. n]. Describe
an algorithm to find the median element in the union of A and B in (b) Describe an algorithm to compute the decimal representation of 2n in
Θ(log n) time. You can assume that the arrays contain no duplicate O(nlg 3 ) time, using the algorithm from part (a) as a subroutine. (The
elements. standard algorithm that computes one digit at a time requires Θ(n2 )
time.)
(b) Suppose we are given two sorted arrays A[1 .. m] and B[1 .. n] and an
integer k. Describe an algorithm to find the kth smallest element in (c) Describe a divide-and-conquer algorithm to compute the decimal rep-
A ∪ B in Θ(log(m + n)) time. For example, if k = 1, your algorithm resentation of an arbitrary n-bit binary number in O(nlg 3 ) time. [Hint:
should return the smallest element of A ∪ B.) [Hint: Use your solution Watch out for an extra log factor in the running time.]
to part (a).] ª
(d) Suppose we can multiply two n-digit numbers in O(M (n)) time. Describe
ª
(c) Now suppose we are given three sorted arrays A[1 .. n], B[1 .. n], and an algorithm to compute the decimal representation of an arbitrary n-bit
C[1 .. n], and an integer k. Describe an algorithm to find the kth smallest binary number in O(M (n) log n) time. [Hint: The analysis is the hard
element in A ∪ B ∪ C in O(log n) time. part; use a domain transformation.]

55 56
 Exercises 1. RECURSION

24. Consider the following classical recursive algorithm for computing the EuclidGCD(x, y):
factorial n! of a non-negative integer n: if x = y
return x
Factorial(n): else if x > y
if n = 0 return EuclidGCD(x − y, y)
return 1 else
else return EuclidGCD(x, y − x)
return n · Factorial(n − 1)
(a) Prove that EuclidGCD correctly computes gcd(x, y).18 Specifically:
(a) How many multiplications does this algorithm perform?
i. Prove that EuclidGCD(x, y) divides both x and y.
(b) How many bits are required to write n! in binary? Express your answer
ii. Prove that every divisor of x and y is a divisor of EuclidGCD(x, y).
in the form Θ( f (n)), for some familiar function f (n). [Hint: (n/2)n/2 <
n! < nn .] (b) What is the worst-case running time of EuclidGCD(x, y), as a function
of x and y? (Assume that computing x − y requires O(log x + log y)
(c) Your answer to (b) should convince you that the number of multiplications
time.)
is not a good estimate of the actual running time of Factorial. We
can multiply any k-digit number and any l-digit number in O(k · l) time (c) Prove that the following algorithm also computes gcd(x, y):
using either the lattice algorithm or duplation and mediation. What is FastEuclidGCD(x, y):
if y = 0
the running time of Factorial if we use this multiplication algorithm as
return x
a subroutine? else if x > y
(d) The following recursive algorithm also computes the factorial function, return FastEuclidGCD( y, x mod y)
but using a different grouping of the multiplications: else
return FastEuclidGCD(x, y mod x)
Falling(n, m): 〈〈Compute n!/(n − m)!〉〉
if m = 0 (d) What is the worst-case running time of FastEuclidGCD(x, y), as a
return 1 function of x and y? (Assume that computing x mod y takes O(log x ·
else if m = 1 log y) time.)
return n
(e) Prove that the following algorithm also computes gcd(x, y):
else
return Falling(n, bm/2c) · Falling(n − bm/2c, dm/2e) BinaryGCD(x, y):
if x = y
What is the running time of Falling(n, n) if we use grade-school multi- return x
plication? [Hint: As usual, ignore the floors and ceilings.] else if x and y are both even
(e) Describe and analyze a variant of Karatsuba’s algorithm that multiplies return 2 · BinaryGCD(x/2, y/2)
any k-digit number and any l-digit number, for any k ≥ l, in O(k · else if x is even
return BinaryGCD(x/2, y)
l lg 3−1 ) = O(k · l 0.585 ) time.
else if y is even
ª
(f) What are the running times of Factorial(n) and Falling(n, n) if we return BinaryGCD(x, y/2)
use the modified Karatsuba multiplication from part (e)? else if x > y
return BinaryGCD((x − y)/2, y)
25. The greatest common divisor of two positive integer x and y, denoted else
gcd(x , y), is the largest integer d such that both x/d and y/d are integers. return BinaryGCD(x, ( y − x)/2)
Euclid’s Elements, written around 300bce, describes the following recursive 18
Euclid did not do this. Proposition 1 in Elements Book VII states that if EuclidGCD(x, y) = 1,
algorithm to compute gcd(x, y): 17 then x and y are relatively prime (that is, gcd(x, y) = 1), but the proof only considers the special
case x mod ( y mod (x mod y)) = 1. Proposition 2 states that if x and y are not relatively prime,
17
Euclid’s algorithm is sometimes incorrectly described as the oldest recursive algorithm, then EuclidGCD(x, y) = gcd(x, y), but the proof only considers the special cases gcd(x, y) = y
or even the oldest nontrivial algorithm, even though the Egyptian duplation and mediation and gcd(x, y) = y mod (x mod y). Finally, these two Propositions do not make a complete proof
algorithm—which is both nontrivial and recursive—predates Euclid by at least 1500 years. that EuclidGCD is correct. Don’t be like Euclid.

57 58
 Exercises 1. RECURSION

(f) What is the worst-case running time of BinaryGCD(x, y), as a function • If X is a knight, then X will respond with Y ’s correct type.
of x and y? (Assume that computing x − y takes O(log x + log y) time, • If X is a knave, then X could respond with either of the types that Y is
and computing z/2 requires O(log z) time.) not.
• If X is a normal, then X could respond with any of the three types.
Arrays The inhabitants will ignore any questions not of this precise form; in
n n
26. Suppose you are given a 2 × 2 checkerboard with one (arbitrarily chosen) particular, you may not ask an inhabitant about their own type. Asking the
square removed. Describe and analyze an algorithm to compute a tiling of same inhabitant the same question multiple times always yields the same
the board by without gaps or overlaps by L-shaped tiles, each composed of 3 answer, so there’s no point in asking any question more than once.
squares. Your input is the integer n and two n-bit integers representing the (a) Suppose you know that a strict majority of inhabitants are knights.
row and column of the missing square. The output is a list of the positions Describe an efficient algorithm to identify the type of every inhabitant.
and orientations of (4n − 1)/3 tiles. Your algorithm should run in O(4n ) (b) Prove that if at most half the inhabitants are knights, it is impossible to
time. [Hint: First prove that such a tiling always exists.] determine the type of every inhabitant.

27. You are a visitor at a political convention (or perhaps a faculty meeting) 29. Most graphics hardware includes support for a low-level operation called blit,
with n delegates; each delegate is a member of exactly one political party. or block transfer, which quickly copies a rectangular chunk of a pixel map
It is impossible to tell which political party any delegate belongs to; in (a two-dimensional array of pixel values) from one location to another. This
particular, you will be summarily ejected from the convention if you ask. is a two-dimensional version of the standard C library function memcpy().
However, you can determine whether any pair of delegates belong to the Suppose we want to rotate an n × n pixel map 90◦ clockwise. One way to
same party by introducing them to each other. Members of the same political do this, at least when n is a power of two, is to split the pixel map into four
party always greet each other with smiles and friendly handshakes; members n/2 × n/2 blocks, move each block to its proper position using a sequence of
of different parties always greet each other with angry stares and insults.19 five blits, and then recursively rotate each block. (Why five? For the same
reason the Tower of Hanoi puzzle needs a third peg.) Alternately, we could
(a) Suppose more than half of the delegates belong to the same political
first recursively rotate the blocks and then blit them into place.
party. Describe an efficient algorithm that identifies all members of this
majority party. A B C A A B

A B

A C

A B
C D

C D
B D
5 blits recurse recurse 5 blits
(b) Now suppose there are more than two parties, but one party has a C D D B C D
plurality: more people belong to that party than to any other party. Figure 1.24. Two algorithms for rotating a pixel map.
Present a practical procedure to precisely pick the people from the
plurality political party as parsimoniously as possible, presuming the (a) Prove that both versions of the algorithm are correct when n is a power
plurality party is composed of at least p people. Pretty please. of 2.
(b) Exactly how many blits does the algorithm perform when n is a power
28. Smullyan Island has three types of inhabitants: knights always speak the of 2?
truth; knaves always lie; and normals sometimes speak the truth and
(c) Describe how to modify the algorithm so that it works for arbitrary n,
sometimes don’t. Everyone on the island knows everyone else’s name and
not just powers of 2. How many blits does your modified algorithm
type (knight, knave, or normal). You want to learn the type of every
perform?
inhabitant.
(d) What is your algorithm’s running time if a k × k blit takes O(k2 ) time?
You can ask any inhabitant to tell you the type of any other inhabitant.
Specifically, if you ask “Hey X , what is Y ’s type?” then X will respond as (e) What if a k × k blit takes only O(k) time?
follows:
30. An array A[0 .. n − 1] of n distinct numbers is bitonic if there are unique
19
Real-world politics is much messier than this simplified model, but this is a theory book! indices i and j such that A[(i − 1) mod n] < A[i] > A[(i + 1) mod n] and

59 60
 Exercises 1. RECURSION

We can obviously find a local minimum in O(n) time by scanning through

the array. Describe and analyze an algorithm that finds a local minimum in
O(log n) time. [Hint: With the given boundary conditions, the array must
have at least one local minimum. Why?]

33. Suppose you are given a sorted array of n distinct numbers that has been
rotated k steps, for some unknown integer k between 1 and n − 1. That is,
you are given an array A[1 .. n] such that some prefix A[1 .. k] is sorted in
increasing order, the corresponding suffix A[k + 1 .. n] is sorted in increasing
order, and A[n] < A[1].
For example, you might be given the following 16-element array (where
Figure 1.25. The first rotation algorithm (blit then recurse) in action. (See Image Credits at the end of
the book.) k = 10):

9 13 16 18 19 23 28 31 37 42 1 3 4 5 7 8
A[( j − 1) mod n] > A[ j] < A[( j + 1) mod n]. In other words, a bitonic
sequence either consists of an increasing sequence followed by a decreasing (a) Describe and analyze an algorithm to compute the unknown integer k.
sequence, or can be circularly shifted to become so. For example,
(b) Describe and analyze an algorithm to determine if the given array
contains a given number x.
4 6 9 8 7 5 1 2 3 is bitonic, but
3 6 9 8 7 5 1 2 4 is not bitonic. 34. At the end of the second act of the action blockbuster Fast and Impossible
XIII¾: The Last Guardians of Expendable Justice Reloaded,the villainous
Describe and analyze an algorithm to find the smallest element in an n- Dr. Metaphor hypnotizes the entire Hero League/Force/Squad, arranges
element bitonic array in O(log n) time. You may assume that the numbers them in a long line at the edge of a cliff, and instructs each hero to shoot
in the input array are distinct. the closest taller heroes to their left and right, at a prearranged signal.
Suppose we are given the heights of all n heroes, in order from left
31. Suppose we are given an array A[1 .. n] of n distinct integers, which could be to right, in an array Ht[1 .. n]. (To avoid salary arguments, the producers
positive, negative, or zero, sorted in increasing order so that A[1] < A[2] < insisted that no two heroes have the same height.) Then we can compute
· · · < A[n]. the Left and Right targets of each hero in O(n2 ) time using the following
(a) Describe a fast algorithm that either computes an index i such that brute-force algorithm.
A[i] = i or correctly reports that no such index exists. WhoTargetsWhom(Ht[1 .. n]):
for j ← 1 to n
(b) Suppose we know in advance that A[1] > 0. Describe an even faster
algorithm that either computes an index i such that A[i] = i or correctly 〈〈Find the left target L[ j] for hero j〉〉
L[ j] ← None
reports that no such index exists. [Hint: This is really easy.]
for i ← 1 to j − 1
if Ht[i] > Ht[ j]
32. Suppose we are given an array A[1 .. n] with the special property that L[ j] ← i
A[1] ≥ A[2] and A[n − 1] ≤ A[n]. We say that an element A[x] is a local 〈〈Find the right target R[ j] for hero j〉〉
minimum if it is less than or equal to both its neighbors, or more formally, R[ j] ← None
if A[x − 1] ≥ A[x] and A[x] ≤ A[x + 1]. For example, there are six local for k ← n down to j + 1
minima in the following array: if Ht[k] > Ht[ j]
R[ j] ← k
9 7 7 2 1 3 7 5 4 7 3 3 4 8 6 9 return L[1 .. n], R[1 .. n]
Î Î Î Î Î Î
61 62
 Exercises 1. RECURSION

(a) Describe a divide-and-conquer algorithm that computes the output of ª

(b) Now suppose n = 2` − k for some positive integers k and `, and again we
WhoTargetsWhom in O(n log n) time. are given an array A[1 .. n] of distinct `-bit strings. Describe an algorithm
(b) Prove that at least bn/2c of the n heroes are targets. That is, prove that to find the k strings that are missing from A using only O(n log k) calls
the output arrays R[0 .. n − 1] and L[0 .. n − 1] contain at least bn/2c to FetchBit.
distinct values (other than None).
(c) Alas, Dr. Metaphor’s diabolical plan is successful. At the prearranged Trees
signal, all the heroes simultaneously shoot their targets, and all targets
37. For this problem, a subtree of a binary tree means any connected subgraph.
fall over the cliff, apparently dead. Metaphor repeats his dastardly
A binary tree is complete if every internal node has two children, and every
experiment over and over; after each massacre, he forces the remaining
leaf has exactly the same depth. Describe and analyze a recursive algorithm
heroes to choose new targets, following the same algorithm, and then
to compute the largest complete subtree of a given binary tree. Your algorithm
shoot their targets at the next signal. Eventually, only the shortest
should return both the root and the depth of this subtree. See Figure 1.26
member of the Hero Crew/Alliance/Posse is left alive.20
for an example.
Describe and analyze an algorithm to compute the number of rounds
before Dr. Metaphor’s deadly process finally ends. For full credit, your
algorithm should run in O(n) time.

35. You are a contestant on the hit game show “Beat Your Neighbors!” You are
presented with an m × n grid of boxes, each containing a unique number. It
costs $100 to open a box. Your goal is to find a box whose number is larger
than its neighbors in the grid (above, below, left, and right). If you spend
less money than any of your opponents, you win a week-long trip for two to
Las Vegas and a year’s supply of Rice-A-Ronitm , to which you are hopelessly Figure 1.26. The largest complete subtree of this binary tree has depth 3.
addicted.
(a) Suppose m = 1. Describe an algorithm that finds a number that is bigger 38. Let T be a binary tree with n vertices. Deleting any vertex v splits T into at
than either of its neighbors. How many boxes does your algorithm open most three subtrees, containing the left child of v (if any), the right child
in the worst case? of v (if any), and the parent of v (if any). We call v a central vertex if
ª
(b) Suppose m = n. Describe an algorithm that finds a number that is bigger each of these smaller trees has at most n/2 vertices. See Figure 1.27 for an
than any of its neighbors. How many boxes does your algorithm open in example.
the worst case? Describe and analyze an algorithm to find a central vertex in an arbitrary
¨ª given binary tree. [Hint: First prove that every tree has a central vertex.]
(c) Prove that your solution to part (b) is optimal up to a constant factor.
34 14
36. (a) Let n = 2` − 1 for some positive integer `. Suppose someone claims to
hold an unsorted array A[1 .. n] of distinct `-bit strings; thus, exactly one
`-bit string does not appear in A. Suppose further that the only way we 7 12

can access A is by calling the function FetchBit(i, j), which returns the
jth bit of the string A[i] in O(1) time. Describe an algorithm to find the
missing string in A using only O(n) calls to FetchBit.
20
In the thrilling final act, Retcon the Squirrel, the last surviving member of the Hero
Team/Group/Society, saves everyone by traveling back in time and retroactively replacing the Figure 1.27. Deleting a central vertex in a 34-node binary tree, leaving subtrees with 14, 7, and 12 nodes.
other n − 1 heroes with lifelike balloon sculptures. So, yeah, basically it’s Avengers: Endgame.

63 64
 Exercises 1. RECURSION

39. (a) Professor George O’Jungle has a 27-node binary tree, in which every
node is labeled with a unique letter of the Roman alphabet or the
character &. Preorder and postorder traversals of the tree visit the nodes
in the following order:
• Preorder: I Q J H L E M V O T S B R G Y Z K C A & F P N U D W X
• Postorder: H E M L J V Q S G Y R Z B T C P U D N F W & X A K O I
Draw George’s binary tree.
(b) Recall that a binary tree is full if every non-leaf node has exactly two
children.
i. Describe and analyze a recursive algorithm to reconstruct an arbitrary
full binary tree, given its preorder and postorder node sequences as Figure 1.28. A kd-tree for 15 points. The dashed line crosses the four shaded cells.
input.
ii. Prove that there is no algorithm to reconstruct an arbitrary binary (a) How many cells are there, as a function of n? Prove your answer is
tree from its preorder and postorder node sequences. correct.
(c) Describe and analyze a recursive algorithm to reconstruct an arbitrary (b) In the worst case, exactly how many cells can a horizontal line cross, as
binary tree, given its preorder and inorder node sequences as input. a function of n? Prove your answer is correct. Assume that n = 2k − 1
for some integer k. [Hint: There is more than one function f such that
(d) Describe and analyze a recursive algorithm to reconstruct an arbitrary
f (16) = 4.]
binary search tree, given only its preorder node sequence.
(c) Suppose we are given n points stored in a kd-tree. Describe and analyze
ª
(e) Describe and analyze a recursive algorithm to reconstruct an arbitrary an algorithm that counts the number of points above a horizontal line
binary search tree, given only its preorder node sequence, in O(n) time. (such as the dashed line in the figure) as quickly as possible. [Hint: Use
In parts (b)–(e), assume that all keys are distinct and that the input is part (b).]
consistent with at least one binary tree. (d) Describe an analyze an efficient algorithm that counts, given a kd-tree
containing n points, the number of points that lie inside a rectangle R
40. Suppose we have n points scattered inside a two-dimensional box. A kd- with horizontal and vertical sides. [Hint: Use part (c).]
tree21 recursively subdivides the points as follows. If the box contains no
points in its interior, we are done. Otherwise, we split the box into two ª
41. Bob Ratenbur, a new student in CS 225, is trying to write code to perform
smaller boxes with a vertical line, through a median point inside the box preorder, inorder, and postorder traversals of binary trees. Bob sort-of
(not on its boundary), partitioning the points as evenly as possible. Then understands the basic idea behind the traversal algorithms, but whenever
we recursively build a kd-tree for the points in each of the two smaller he actually tries to implement them, he keeps mixing up the recursive calls.
boxes, after rotating them 90 degrees. Thus, we alternate between splitting Five minutes before the deadline, Bob frantically submits code with the
vertically and splitting horizontally at each level of recursion. The final following structure:
empty boxes are called cells.
PreOrder(v): InOrder(v): PostOrder(v):
21 if v = Null if v = Null if v = Null
The term “kd-tree” (pronounced “kay dee tree”) was originally an abbreviation for “k-
return return return
dimensional tree”, but modern usage ignores this etymology, in part because nobody in their else else else
right mind would ever use the letter k to denote dimension instead of the obviously superior d. print label(v) Order(left(v)) Order(left(v))
Etymological consistency would require calling the data structure in this problem a “2d-tree” Order(left(v)) print label(v) Order(right(v))
(or perhaps a “2-d tree”), but the standard nomenclature is now “two-dimensional kd-tree”. Order(right(v)) Order(right(v)) print label(v)
See also: B-tree (maybe), alpha shape, beta skeleton, epsilon net, Potomac River, Mississippi
River, Lake Michigan, Lake Tahoe, Manhattan Island, La Brea Tar Pits, Sahara Desert, Mount
Each in this pseudocode hides one of the prefixes Pre, In, or Post.
Kilimanjaro, South Vietnam, East Timor, the Milky Way Galaxy, the City of Townsville, and Moreover, each of the following function calls appears exactly once in Bob’s
self-driving automobiles. submitted code:

65 66
 Exercises 1. RECURSION

PreOrder(left(v)) PreOrder(right(v)) • The left subtree of T is a binary search tree.

InOrder(left(v)) InOrder(right(v)) • All values in the left subtree are smaller than the value at the root.
PostOrder(left(v)) PostOrder(right(v)) • The right subtree of T is a binary search tree.
Thus, there are precisely 36 possibilities for Bob’s code. Unfortunately, Bob • All values in the right subtree are larger than the value at the root.
accidentally deleted his source code after submitting the executable, so
Consider the following pair of operations on binary trees:
neither you nor he knows which functions were called where.
Now suppose you are given the output of Bob’s traversal algorithms, • Rotate an arbitrary node upward.22
executed on some unknown binary tree T . Bob’s output has been helpfully y x
x y
parsed into three arrays Pre[1 .. n], In[1 .. n], and Post[1 .. n]. You may
assume that these traversal sequences are consistent with exactly one binary C A
tree T ; in particular, the vertex labels of the unknown tree T are distinct, A B B C

and every internal node in T has exactly two children. • Swap the left and right subtrees of an arbitrary node.
(a) Describe an algorithm to reconstruct the unknown tree T from the given x x

traversal sequences.
(b) Describe an algorithm that either reconstructs Bob’s code from the given A B B A

traversal sequences, or correctly reports that the traversal sequences are In both of these operations, some, all, or none of the subtrees A, B, and C
consistent with more than one set of algorithms. could be empty.
For example, given the input
(a) Describe an algorithm to transform an arbitrary n-node binary tree
Pre[1 .. n] = [H A E C B I F G D] with distinct node values into a binary search tree, using at most O(n2 )
rotations and swaps. Figure 1.29 shows a sequence of eight operations
In[1 .. n] = [A H D C E I F B G]
that transforms a five-node binary tree into a binary search tree.
Post[1 .. n] = [A E I B F C D G H]
3 3 2 2 3 4 4 4 4

your first algorithm should return the following tree: 1 4 1 2 3 3 4 2 5 3 5 3 5 2 2 5

H 5 2 4 1 4 4 1 5 1 2 2 1 3 1 3

5 5 5 1 1
A D
Figure 1.29. “Sorting” a binary tree: rotate 2, rotate 2, swap 3, rotate 3, rotate 4, swap 3, rotate 2, swap 4.
C G

E B Your algorithm is not allowed to directly modify parent or child

pointers, create new nodes, or delete old nodes; the only way to modify
I F the tree is through rotations and swaps.
and your second algorithm should reconstruct the following code: On the other hand, you may compute anything you like for free, as
PreOrder(v): InOrder(v): PostOrder(v): long as that computation does not modify the tree; the running time of
if v = Null if v = Null if v = Null your algorithm is defined to be the number of rotations and swaps that it
return return return
else else else performs.
print label(v) PostOrder(left(v)) InOrder(left(v)) ª
PreOrder(left(v)) print label(v) InOrder(right(v))
(b) Describe an algorithm to transform an arbitrary n-node binary tree into
PostOrder(right(v)) PreOrder(right(v)) print label(v) a binary search tree, using at most O(n log n) rotations and swaps.
22
ª Rotations preserve the inorder sequence of nodes in a binary tree. Partly for this reason,
42. Let T be a binary tree whose nodes store distinct numerical values. Recall rotations are used to maintain several types of balanced binary search trees, including AVL trees,
that T is a binary search tree if and only if either (1) T is empty, or (2) T red-black trees, splay trees, scapegoat trees, and treaps. See [Link] for lecture
satisfies the following recursive conditions: notes on most of these data structures.

67 68
 Exercises

(c) Prove that any n-node binary search tree can be transformed into any
other binary search tree with the same node values, using only O(n)
rotations (and no swaps).
ª(d) Open problem: Either describe an algorithm to transform an arbitrary
n-node binary tree into a binary search tree using only O(n) rotations
and swaps, or prove that no such algorithm is possible. [Hint: I don’t
think it’s possible.]

69
 2. BACKTRACKING
Where, however, the ambiguity cannot be cleared up, either by the rule of faith or by
the context, there is nothing to hinder us to point the sentence according to any
method we choose of those that suggest themselves. For readers not familiar with the rules of chess, this means that no two queens
— Augustine of Hippo, De doctrina Christiana (397CE) are in the same row, the same column, or the same diagonal.
Translated by Marcus Dods (1892)
I dropped my dinner, and ran back to the laboratory. There, in my excitement, ♕
I tasted the contents of every beaker and evaporating dish on the table. Luckily for ♕
♛
me, none contained any corrosive or poisonous liquid.
♕
— Constantine Fahlberg on his discovery of saccharin,
Scientific American (1886)
♕
The greatest challenge to any thinker is stating the problem
♕
♛
in a way that will allow a solution. ♕
— attributed to Bertrand Russell ♕
♛
When you come to a fork in the road, take it. ♕
♛
— Yogi Berra (giving directions to his house)
Figure 2.1. Gauss’s first solution to the 8 queens problem, represented by the array [5, 7, 1, 4, 2, 8, 6, 3]

In a letter written to his friend Heinrich Schumacher in 1850, the eminent

mathematician Carl Friedrich Gauss wrote that one could easily confirm Franz
Nauck’s claim that the Eight Queens problem has 92 solutions by trial and

2 error in a few hours. (“Schwer ist es übrigens nicht, durch ein methodisches
Tatonniren sich diese Gewissheit zu verschaffen, wenn man 1 oder ein paar Stunden
daran wenden will.”) His description Tatonniren comes from the French tâtonner,
meaning to feel, grope, or fumble around blindly, as if in the dark.
Gauss’s letter described the following recursive strategy for solving the
n-queens problem; the same strategy was described in 1882 by the French
Backtracking recreational mathematician Édouard Lucas, who attributed the method to
Emmanuel Laquière. We place queens on the board one row at a time, starting
with the top row. To place the rth queen, we methodically try all n squares in
row r from left to right in a simple for loop. If a particular square is attacked by
an earlier queen, we ignore that square; otherwise, we tentatively place a queen
on that square and recursively grope for consistent placements of the queens in
This chapter describes another important recursive strategy called backtracking. later rows.
A backtracking algorithm tries to construct a solution to a computational problem Figure 2.2 shows the resulting algorithm, which recursively enumerates all
incrementally, one small piece at a time. Whenever the algorithm needs to complete n-queens solutions that are consistent with a given partial solution.
decide between multiple alternatives to the next component of the solution, it Following Gauss, we represent the positions of the queens using an array
recursively evaluates every alternative and then chooses the best one. Q[1 .. n], where Q[i] indicates which square in row i contains a queen. When
PlaceQueens is called, the input parameter r is the index of the first empty row,
and the prefix Q[1 .. r − 1] contains the positions of the first r − 1 queens. In
2.1 N Queens particular, to compute all n-queens solutions with no restrictions, we would call
PlaceQueens(Q[1 .. n], 1). The outer for-loop considers all possible placements
The prototypical backtracking problem is the classical n Queens Problem, first of a queen on row r; the inner for-loop checks whether a candidate placement
proposed by German chess enthusiast Max Bezzel in 1848 (under his pseudonym of row r is consistent with the queens that are already on the first r − 1 rows.
“Schachfreund”) for the standard 8 × 8 board and by François-Joseph Eustache The execution of PlaceQueens can be illustrated using a recursion tree.
Lionnet in 1869 for the more general n × n board. The problem is to place n Each node in this tree corresponds to a recursive subproblem, and thus to a
queens on an n × n chessboard, so that no two queens are attacking each other. legal partial solution; in particular, the root corresponds to the empty board

71 72