■
Contents
x
If You’re Curious ��� ��������������������������������������������������������������������������������������������������������������������
112
Exercises �����������������������������������������������������������������������������������������������������������������������������������
112
References ��������������������������������������������������������������������������������������������������������������������������������
113
Chapter 6
■
:
Divide, Combine, and Conquer ���������������������������������������������������������������������
115
Tree-Shaped Problems: All About the Balance ��������������������������������������������������������������������������
115
The Canonical D&C Algorithm ���������������������������������������������������������������������������������������������������
117
Searching by Halves ������������������������������������������������������������������������������������������������������������������
118
Traversing Search Trees ��� with Pruning �����������������������������������������������������������������������������������������������������������
120
Selection ������������������������������������������������������������������������������������������������������������������������������������������������������������
123
Sorting by Halves ����������������������������������������������������������������������������������������������������������������������
125
How Fast Can We Sort? �������������������������������������������������������������������������������������������������������������������������������������
127
Three More Examples ����������������������������������������������������������������������������������������������������������������
127
Closest Pair ��������������������������������������������������������������������������������������������������������������������������������������������������������
127
Convex Hull ��������������������������������������������������������������������������������������������������������������������������������������������������������
129
Greatest Slice ����������������������������������������������������������������������������������������������������������������������������������������������������
130
Tree Balance ��� and
Balancing
*
�������������������������������������������������������������������������������������������������
131
Summary �����������������������������������������������������������������������������������������������������������������������������������
136
If You’re Curious ��� ��������������������������������������������������������������������������������������������������������������������
137
Exercises �����������������������������������������������������������������������������������������������������������������������������������
137
References ��������������������������������������������������������������������������������������������������������������������������������
138
Chapter 7
■
:
Greed Is Good? Prove It! �����������������������������������������������������������������������������
139
Staying Safe, Step by Step ��������������������������������������������������������������������������������������������������������
139
The Knapsack Problem ��������������������������������������������������������������������������������������������������������������
143
Fractional Knapsack ������������������������������������������������������������������������������������������������������������������������������������������
143
Integer Knapsack �����������������������������������������������������������������������������������������������������������������������������������������������
143
Huffman’s Algorithm ������������������������������������������������������������������������������������������������������������������
144
The Algorithm ����������������������������������������������������������������������������������������������������������������������������������������������������
145
The First Greedy Choice �������������������������������������������������������������������������������������������������������������������������������������
147
Going the Rest of the Way����������������������������������������������������������������������������������������������������������������������������������
147
Optimal Merging ������������������������������������������������������������������������������������������������������������������������������������������������
148
■
Contents
xii
Far-Fetched Subproblems ���������������������������������������������������������������������������������������������������������
198
Meeting in the Middle ���������������������������������������������������������������������������������������������������������������
201
Knowing Where You’re Going ����������������������������������������������������������������������������������������������������
203
Summary �����������������������������������������������������������������������������������������������������������������������������������
206
If You’re Curious ��� ��������������������������������������������������������������������������������������������������������������������
207
Exercises �����������������������������������������������������������������������������������������������������������������������������������
207
References ��������������������������������������������������������������������������������������������������������������������������������
208
Chapter 10
■
:
Matchings, Cuts, and Flows ����������������������������������������������������������������������
209
Bipartite Matching ���������������������������������������������������������������������������������������������������������������������
210
Disjoint Paths ����������������������������������������������������������������������������������������������������������������������������
212
Maximum Flow ��������������������������������������������������������������������������������������������������������������������������
215
Minimum Cut �����������������������������������������������������������������������������������������������������������������������������
218
Cheapest Flow
and the Assignment Problem
*
���������������������������������������������������������������������������
219
Some Applications ���������������������������������������������������������������������������������������������������������������������
221
Summary �����������������������������������������������������������������������������������������������������������������������������������
224
If You’re Curious … �������������������������������������������������������������������������������������������������������������������
224
Exercises �����������������������������������������������������������������������������������������������������������������������������������
224
References ��������������������������������������������������������������������������������������������������������������������������������
225
Chapter 11
■
:
Hard Problems and (Limited) Sloppiness ��������������������������������������������������
227
Reduction Redux �����������������������������������������������������������������������������������������������������������������������
228
Not in Kansas Anymore? �����������������������������������������������������������������������������������������������������������
230
Meanwhile, Back in Kansas … �������������������������������������������������������������������������������������������������
232
But Where Do You Start? And Where Do You Go from There? ����������������������������������������������������
235
A Ménagerie of Monsters ����������������������������������������������������������������������������������������������������������
239
Return of the Knapsack �������������������������������������������������������������������������������������������������������������������������������������
239
Cliques and Colorings ����������������������������������������������������������������������������������������������������������������������������������������
240
Paths and Circuits ����������������������������������������������������������������������������������������������������������������������������������������������
242
When
the Going Gets Tough, the Smart Get Sloppy �������������������������������������������������������������������
245
Desperately Seeking Solutions ��������������������������������������������������������������������������������������������������
247