Algorithms and Complexity

Herbert S. Wilf

"[The examples] are selected with great care and enable the reader to concentrate directly on the main features of the demonstrated topics. . . . The book can be warmly recommended to those willing to learn (or teach) basic ideas of computational mathematics." -EMS Newsletter, March 2004

• Preface, Preface to the Second Edition, 0 What this Book Is About, 0.1 Background, 0.2 Hard versus Easy Problems, 0.3 A Preview, 1 Mathematical Preliminaries, 1.1 Orders of Magnitude, 1.2 Positional Number Systems, 1.3 Manipulations with Series, 1.4 Recurrence Relations, 1.5 Counting, 1.6 Graphs, 2 Recursive Algorithms, 2.1 Introduction, 2.2 Quicksort, 2.3 Recursive Graph Algorithms, 2.4 Fast Matrix Multiplication, 2.5 The Discrete Fourier Transform, 2.6 Applications of the FFT, 2.7 A Review, 2.8 Bibliography, 3 The Network Flow Problem, 3.1 Introduction, 3.2 Algorithms for the Network Flow Problem, 3.3 The Algorithm of Ford and Fulkerson, 3.4 The Max-Flow Min-Cut Theorem, 3.5 The Complexity of the Ford-Fulkerson Algorithm, 3.6 Layered Networks, 3.7 The MPM Algorithm, 3.8 Applications of Network Flow, Bibliography, 4 Algorithms in the Theory of Numbers, 4.1 Preliminaries, 4.2 The Greatest Common Divisor, 4.3 The Extended Euclidean Algorithm, 4.4 Primality Testing, 4.5 Interlude: The Ring of Integers Modulo, 4.6 Pseudoprimality Tests, 4.7 Proof of Goodness of the Strong Pseudoprimality Test, 4.8 Factoring and Cryptography, 4.9 Factoring Large Integers, 4.10 Proving Primality, Bibliography, 5 NP-Completeness, 5.1 Introduction, 5.2 Turing Machines, 5.3 Cook’s Theorem, 5.4 Some Other NP-Complete Problems, 5.5 Half a Loaf, 5.6 Backtracking (I): Independent Sets, 5.7 Backtracking (II): Graph Coloring, 5.8 Approximate Algorithms for Hard Problems, Bibliography, Hints and Solutions for Selected Problems, Index