Algorithms and Complexity

CONTENTS
Chapter 0: What This Book Is About
0.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
0.2 Hard vs. easy problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
0.3 A preview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Chapter 1: Mathematical Preliminaries
1.1 Orders of magnitude . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Positional number systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3 Manipulations with series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4 Recurrence relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.5 Counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.6 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
Chapter 2: Recursive Algorithms
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.2 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.3 Recursive graph algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.4 Fast matrix multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.5 The discrete Fourier transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.6 Applications of the FFT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
2.7 A review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
Chapter 3: The Network Flow Problem
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.2 Algorithms for the network flow problem . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.3 The algorithm of Ford and Fulkerson . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.4 The max-flow min-cut theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.5 The complexity of the Ford-Fulkerson algorithm . . . . . . . . . . . . . . . . . . . . . 70
3.6 Layered networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
3.7 The MPM Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
3.8 Applications of network flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
Chapter 4: Algorithms in the Theory of Numbers
4.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
4.2 The greatest common divisor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
4.3 The extended Euclidean algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
4.4 Primality testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
4.5 Interlude: the ring of integers modulo n . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.6 Pseudoprimality tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4.7 Proof of goodness of the strong pseudoprimality test . . . . . . . . . . . . . . . . . . . . 94
4.8 Factoring and cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
4.9 Factoring large integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
4.10 Proving primality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
Chapter 5: NP-completeness
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
5.2 Turing machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
5.3 Cook’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
5.4 Some other NP-complete problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
5.5 Half a loaf ... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
5.6 Backtracking (I): independent sets . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
5.7 Backtracking (II): graph coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
5.8 Approximate algorithms for hard problems . . . . . . . . . . . . . . . . . . . . . . . . 128

Another Algorithm Books
Download