In this blog, 25.000 books will be uploaded, so far more than 1400 books are available. Books, will be added daily, please check this blog daily.
Thursday, November 24, 2011
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
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment