Table of Contents
Preface vii
1 Preliminaries 1
1.1 What is correctness? 1
1.1.1 Complexity 3
1.1.2 Division 4
1.1.3 Euclid 5
1.1.4 Palindromes 7
1.1.5 Further examples 9
1.2 Ranking algorithms 11
1.2.1 PageRank 11
1.2.2 A stable marriage 14
1.2.3 Pairwise Comparisons 17
1.3 Answers to selected problems 19
1.4 Notes 26
2 Greedy Algorithms 29
2.1 Minimum cost spanning trees 29
2.2 Jobs with deadlines and profits 37
2.3 Further examples and problems 40
2.3.1 Make-change 40
2.3.2 Maximum weight matching 41
2.3.3 Shortest path 41
2.3.4 Huffman codes 45
2.4 Answers to selected problems 47
2.5 Notes 54
3 Divide and Conquer 57
3.1 Mergesort 58
3.2 Multiplying numbers in binary 59
3.3 Savitch's algorithm 62
3.4 Further examples and problems 64
3.4.1 Extended Euclid's algorithm 64
3.4.2 Quicksort 65
3.4.3 Git bisect 66
3.5 Answers to selected problems 66
3.6 Notes 68
4 Dynamic Programming 71
4.1 Longest monotone subsequence problem 71
4.2 All pairs shortest path problem 73
4.2.1 Bellman-Ford algorithm 74
4.3 Simple knapsack problem 75
4.3.1 Dispersed knapsack problem 78
4.3.2 General knapsack problem 79
4.4 Activity selection problem 80
4.5 Jobs with deadlines, durations and profits 82
4.6 Further examples and problems 84
4.6.1 Consecutive subsequence sum problem 84
4.6.2 Shuffle 85
4.7 Answers to selected problems 87
4.8 Notes 92
5 Online Algorithms 95
5.1 List accessing problem 96
5.2 Paging 100
5.2.1 Demand paging 101
5.2.2 FIFO 104
5.2.3 LRU 104
5.2.4 Marking algorithms 108
5.2.5 FWF 109
5.2.6 LFD 110
5.3 Answers to selected problems 114
5.4 Notes 118
6 Randomized Algorithms 119
6.1 Perfect matching 120
6.2 Pattern matching 124
6.3 Primality testing 126
6.4 Public key cryptography 129
6.4.1 Diffie-Hellman key exchange 130
6.4.2 ElGamal 133
6.4.3 RSA 135
6.5 Further problems 137
6.6 Answers to selected problems 138
6.7 Notes 144
7 Algorithms in Linear Algebra 149
7.1 Introduction 149
7.2 Gaussian Elimination 150
7.2.1 Formal proofs of correctness over Z2 153
7.3 Gram-Schmidt 156
7.4 Gaussian lattice reduction 157
7.5 Computing the characteristic polynomial 157
7.5.1 Csanky's algorithm 158
7.5.2 Berkowitz's algorithm 158
7.5.3 Proving properties of the characteristic polynomial 159
7.6 Answers to selected problems 166
7.7 Notes 169
8 Computational Foundations 171
8.1 Introduction 171
8.2 Alphabets, strings and languages 172
8.3 Regular languages 173
8.3.1 Deterministic Finite Automaton 173
8.3.2 Nondeterministic Finite Automata 176
8.3.3 Regular Expressions 179
8.3.4 Algebraic laws for Regular Expressions 182
8.3.5 Closure properties of regular languages 184
8.3.6 Complexity of transformations and decisions 184
8.3.7 Equivalence and minimization of automata 185
8.3.8 Languages that are not regular 186
8.3.9 Automata on terms 189
8.4 Context-free languages 190
8.4.1 Context-free grammars 190
8.4.2 Pushdown automata 192
8.4.3 Chomsky Normal Form 195
8.4.4 CYK algorithm 197
8.4.5 Pumping Lemma for CFLs 198
8.4.6 Further observations about CFL 199
8.4.7 Other grammars 200
8.5 Turing machines 201
8.5.1 Nondeterministic TMs 202
8.5.2 Encodings 203
8.5.3 Decidability 204
8.5.4 Church-Turing thesis 205
8.5.5 Undecidability 206
8.5.6 Reductions 208
8.5.7 Rice's theorem 209
8.5.8 Post's Correspondence Problem 209
8.5.9 Undecidable properties of CFLs 215
8.6 Answers to selected problems 217
8.7 Notes 229
9 Mathematical Foundations 231
9.1 Induction and Invariance 231
9.1.1 Induction 231
9.1.2 Invariance 234
9.2 Number Theory 236
9.2.1 Prime numbers 236
9.2.2 Modular arithmetic 237
9.2.3 Group theory 239
9.2.4 Applications of group theory to number theory 240
9.3 Relations 242
9.3.1 Closure 243
9.3.2 Equivalence relation 244
9.3.3 Partial orders 246
9.3.4 Lattices 248
9.3.5 Fixed point theory 250
9.3.6 Recursion and fixed points 254
9.4 Logic 256
9.4.1 Propositional logic 256
9.4.2 First Order Logic 262
9.4.3 Pcano Arithmetic 267
9.4.4 Formal verification 268
9.5 Answers to selected problems 271
9.6 Notes 292
Bibliography 295
Index 303
