Algorithms and Complexity

Cover......Page 1
Title page......Page 2
Contents......Page 4
Preface......Page 6
Preface to the Second Edition......Page 8
0.1 Background......Page 10
0.2 Hard versus Easy Problems......Page 12
0.3 A Preview......Page 15
1.1 Orders of Magnitude......Page 18
1.2 Positional Number Systems......Page 28
1.3 Manipulations with Series......Page 32
1.4 Recurrence Relations......Page 36
1.5 Counting......Page 43
1.6 Graphs......Page 48
2.1 Introduction......Page 58
2.2 Quicksort......Page 60
2.3 Recursive Graph Algorithms......Page 70
2.4 Fast Matrix Multiplication......Page 85
2.5 The Discrete Fourier Transform......Page 89
2.6 Applications of the FFT......Page 100
2.7 A Review......Page 103
2.8 Bibliography......Page 107
3.1 Introduction......Page 108
3.2 Algorithms for the Network Flow Problem......Page 110
3.3 The Algorithm of Ford and Fulkerson......Page 111
3.4 The Max-Flow Min-Cut Theorem......Page 117
3.5 The Complexity of the Ford-Fulkerson Algorithm......Page 119
3.6 Layered Networks......Page 122
3.7 The MPM Algorithm......Page 128
3.8 Applications of Network Flow......Page 130
4.1 Preliminaries......Page 136
4.2 The Greatest Common Divisor......Page 139
4.3 The Extended Euclidean Algorithm......Page 143
4.4 Primality Testing......Page 147
4.5 Interlude: The Ring of Integers Modulo n......Page 150
4.6 Pseudoprimality Tests......Page 155
4.7 Proof of Goodness of the Strong Pseudoprimality Test......Page 159
4.8 Factoring and Cryptography......Page 163
4.9 Factoring Large Integers......Page 166
4.10 Proving Primality......Page 168
5.1 Introduction......Page 174
5.2 Turing Machines......Page 183
5.3 Cook\'s Theorem......Page 188
5.4 Some Other NP-Complete Problems......Page 195
5.5 Half a Loaf......Page 200
5.6 Backtracking (I): Independent Sets......Page 204
5.7 Backtracking (II): Graph Coloring......Page 208
5.8 Approximate Algorithms for Hard Problems......Page 212
Hints and Solutions for Selected Problems......Page 218
Index......Page 226