Preface
This book evolved over the past ten years from a set of lecture notes developed while teaching the undergraduate Algorithms course at Berkeley and U.C. San Diego. Our way of teaching this course evolved tremendously over these years in a number of directions, partly to address our students' background (undeveloped formal skills outside of programming), and partly to reflect the maturing of the field in general, as we have come to see it. The notes increasingly crystallized into a narrative, and we progressively structured the course to emphasize the "story line" implicit in the progression of the material. As a result, the topics were carefully selected and clustered. No attempt was made to be encyclopedic, and this freed us to include topics traditionally de-emphasized or omitted from most Algorithms books.
Preface 9
0 Prologue 11
0.1 Books and algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
0.2 Enter Fibonacci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
0.3 Big-O notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1 Algorithms with numbers 21
1.1 Basic arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.2 Modular arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.3 Primality testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.4 Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
1.5 Universal hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Randomized algorithms: a virtual chapter 38
2 Divide-and-conquer algorithms 51
2.1 Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.2 Recurrence relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.3 Mergesort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
2.4 Medians . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
2.5 Matrix multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
2.6 The fast Fourier transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
3 Decompositions of graphs 87
3.1 Why graphs? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.2 Depth-first search in undirected graphs . . . . . . . . . . . . . . . . . . . . . . . . 89
3.3 Depth-first search in directed graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 94
3.4 Strongly connected components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4 Paths in graphs 109
4.1 Distances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
4.2 Breadth-first search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
4.3 Lengths on edges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
4.4 Dijkstra's algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
4.5 Priority queue implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
4.6 Shortest paths in the presence of negative edges . . . . . . . . . . . . . . . . . . . 122
4.7 Shortest paths in dags . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
5 Greedy algorithms 133
5.1 Minimum spanning trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
5.2 Huffman encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
5.3 Horn formulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
5.4 Set cover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
6 Dynamic programming 161
6.1 Shortest paths in dags, revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
6.2 Longest increasing subsequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
6.3 Edit distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
6.4 Knapsack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
6.5 Chain matrix multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
6.6 Shortest paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
6.7 Independent sets in trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
7 Linear programming and reductions 189
7.1 An introduction to linear programming . . . . . . . . . . . . . . . . . . . . . . . . 189
7.2 Flows in networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
7.3 Bipartite matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
7.4 Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
7.5 Zero-sum games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
7.6 The simplex algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
7.7 Postscript: circuit evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
8 NP-complete problems 233
8.1 Search problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
8.2 NP-complete problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
8.3 The reductions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
9 Coping with NP-completeness 269
9.1 Intelligent exhaustive search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
9.2 Approximation algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275
9.3 Local search heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
10 Quantum algorithms 295
10.1 Qubits, superposition, and measurement . . . . . . . . . . . . . . . . . . . . . . . 295
10.2 The plan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
10.3 The quantum Fourier transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
10.4 Periodicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302
10.5 Quantum circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304
10.6 Factoring as periodicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
10.7 The quantum algorithm for factoring . . . . . . . . . . . . . . . . . . . . . . . . . . 308
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
Historical notes and further reading 313
Index 315
List of boxes
Bases and logs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Two's complement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
Is your social security number a prime? . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
Hey, that was group theory! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
Carmichael numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
Randomized algorithms: a virtual chapter . . . . . . . . . . . . . . . . . . . . . . . . . . 37
An application of number theory? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
Binary search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
An n log n lower bound for sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
The Unix sort command . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
Why multiply polynomials? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
The slow spread of a fast algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
How big is your graph? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
Crawling fast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
Which heap is best? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
A randomized algorithm for minimum cut . . . . . . . . . . . . . . . . . . . . . . . . . . 143
Entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
Recursion? No, thanks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
Programming? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
Common subproblems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
Of mice and men . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
Memoization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
On time and memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
A magic trick called duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
Reductions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
Matrix-vector notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
Visualizing duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
Gaussian elimination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
Linear programming in polynomial time . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
The story of Sissa and Moore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
Why P and NP? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
The two ways to use reductions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
Unsolvable problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262
Entanglement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
The Fourier transform of a periodic vector . . . . . . . . . . . . . . . . . . . . . . . . . . 303
Setting up a periodic superposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
Quantum physics meets computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
Download attached file: You must be Loged in to download file