An Introduction to the Analysis of Algorithms

Contents......Page 12
Preface......Page 8
1.1 Induction......Page 15
1.2 Invariance......Page 18
1.3 Correctness of algorithms......Page 20
1.3.1 Division algorithm......Page 21
1.3.2 Euclid's algorithm......Page 22
1.3.3 Palindromes algorithm......Page 24
1.3.4 Further examples......Page 26
1.3.5 Recursion and fixed points......Page 29
1.3.6 Formal verification......Page 32
1.4 Stable marriage......Page 35
1.5 Answers to selected problems......Page 38
1.6 Notes......Page 51
2.1 Minimum cost spanning trees......Page 53
2.2 Jobs with deadlines and profits......Page 60
2.3.1 Make change......Page 63
2.3.2 Maximum weight matching......Page 64
2.3.3 Shortest path......Page 65
2.3.4 Huffman codes......Page 68
2.4 Answers to selected problems......Page 70
2.5 Notes......Page 74
3. Divide and Conquer......Page 77
3.1 Mergesort......Page 78
3.2 Multiplying numbers in binary......Page 79
3.3 Savitch's algorithm......Page 82
3.4.1 Extended Euclid's algorithm......Page 84
3.4.2 Finite automata......Page 85
3.5 Answers to selected problems......Page 88
3.6 Notes......Page 89
4.1 Longest monotone subsequence problem......Page 91
4.2 All pairs shortest path problem......Page 93
4.2.1 Bellman-Ford algorithm......Page 94
4.3 Simple knapsack problem......Page 95
4.3.1 Dispersed knapsack problem......Page 98
4.3.2 General knapsack problem......Page 99
4.4 Activity selection problem......Page 100
4.5 Jobs with deadlines, durations and profits......Page 102
4.6.1 Consecutive subsequence sum problem......Page 104
4.6.2 Regular expressions......Page 105
4.6.3 Context free grammars......Page 107
4.7 Answers to selected problems......Page 110
4.8 Notes......Page 114
5. Online Algorithms......Page 115
5.1 List accessing problem......Page 116
5.2 Paging......Page 120
5.2.1 Demand paging......Page 121
5.2.3 LRU......Page 124
5.2.4 Marking algorithms......Page 128
5.2.5 FWF......Page 129
5.2.6 LFD......Page 130
5.3 Answers to selected problems......Page 134
5.4 Notes......Page 136
6. Randomized Algorithms......Page 137
6.1 Perfect matching......Page 138
6.2 Pattern matching......Page 142
6.3 Primality testing......Page 143
6.4 Public key cryptography......Page 147
6.4.1 Diffie-Hellman key exchange......Page 148
6.4.2 ElGamal......Page 150
6.4.3 RSA......Page 153
6.5 Further exercises......Page 154
6.6 Answers to selected problems......Page 156
6.7 Notes......Page 162
Appendix A Number Theory and Group Theory......Page 165
A.2 Notes......Page 170
Appendix B Relations......Page 171
B.1 Closure......Page 172
B.2 Equivalence relation......Page 174
B.3 Partial orders......Page 175
B.4 Lattices......Page 177
B.5 Fixed point theory......Page 179
B.6 Answers to selected problems......Page 183
B.7 Notes......Page 185
C.1 Propositional Logic......Page 187
C.2 First Order Logic......Page 192
C.3 Peano Arithmetic......Page 197
C.4 Answers to selected problems......Page 198
C.5 Notes......Page 200
Bibliography......Page 201
Index......Page 205