Preface xi
PART I Algorithmic Problem Solving 1
CHAPTER 1 ¢" Introduction 3
1.1 Algorithms 3
1.2 Algorithmic Problem Solving 4
1.3 Overview 5
1.4 Bibliographic Remarks 6
CHAPTER 2 ¢" Invariants 7
2.1 Chocolate Bars 10
2.1.1 The Solution 10
2.1.2 The Mathematical Solution 11
2.2 Empty Boxes 16
2.2.1 Review 19
2.3 The Tumbler Problem 22
2.3.1 Non-deterministic Choice 23
2.4 Tetrominoes 24
2.5 Summary 30
2.6 Bibliographic Remarks 34
CHAPTER 3 ¢" Crossing a River 35
3.1 Problems 36
3.2 Brute Force 37
3.2.1 Goat, Cabbage and Wolf 37
3.2.2 State-Space Explosion 39
3.2.3 Abstraction 41
3.3 Nervous Couples 42
3.3.1 What Is the Problem? 42
3.3.2 Problem Structure 43
3.3.3 Denoting States and Transitions 44
3.3.4 Problem Decomposition 45
3.3.5 A Review 48
3.4 Rule of Sequential Composition 50
3.5 The Bridge Problem 54
3.6 Conditional Statements 63
3.7 Summary 65
3.8 Bibliographic Remarks 65
CHAPTER 4 ¢" Games 67
4.1 Matchstick Games 67
4.2 Winning Strategies 69
4.2.1 Assumptions 69
4.2.2 Labelling Positions 70
4.2.3 Formulating Requirements 72
4.3 Subtraction-Set Games 74
4.4 Sums of Games 78
4.4.1 A Simple Sum Game 79
4.4.2 Maintain Symmetry! 81
4.4.3 More Simple Sums 82
4.4.4 Evaluating Positions 83
4.4.5 Using the Mex Function 87
4.5 Summary 91
4.6 Bibliographic Remarks 92
CHAPTER 5 ¢" Knights and Knaves 95
5.1 Logic Puzzles 95
5.2 Calculational Logic 96
5.2.1 Propositions 96
5.2.2 Knights and Knaves 97
5.2.3 Boolean Equality 98
5.2.4 Hidden Treasures 100
5.2.5 Equals for Equals 101
5.3 Equivalence and Continued Equalities 102
5.3.1 Examples of the Associativity of Equivalence 104
5.3.2 On Natural Language 105
5.4 Negation 106
5.4.1 Contraposition 109
5.4.2 Handshake Problems 112
5.4.3 Inequivalence 113
5.5 Summary 117
5.6 Bibliographic Remarks 117
CHAPTER 6 ¢" Induction 119
6.1 Example Problems 120
6.2 Cutting the Plane 123
6.3 Triominoes 126
6.4 Looking for Patterns 128
6.5 The Need for Proof 129
6.6 From Verification to Construction 130
6.7 Summary 134
6.8 Bibliographic Remarks 134
CHAPTER 7 ¢" Fake-Coin Detection 137
7.1 Problem Formulation 137
7.2 Problem Solution 139
7.2.1 The Basis 139
7.2.2 Induction Step 139
7.2.3 The Marked-Coin Problem 140
7.2.4 The Complete Solution 141
7.3 Summary 146
7.4 Bibliographic Remarks 146
CHAPTER 8 ¢" The Tower of Hanoi 147
8.1 Specification and Solution 147
8.1.1 The End of the World! 147
8.1.2 Iterative Solution 148
8.1.3 Why? 149
8.2 Inductive Solution 149
8.3 The Iterative Solution 153
8.4 Summary 156
8.5 Bibliographic Remarks 156
CHAPTER 9 ¢" Principles of Algorithm Design 157
9.1 Iteration, Invariants and Making Progress 158
9.2 A Simple Sorting Problem 160
9.3 Binary Search 163
9.4 Sam Loyd¢s Chicken-Chasing Problem 166
9.4.1 Cornering the Prey 170
9.4.2 Catching the Prey 174
9.4.3 Optimality 176
9.5 Projects 177
9.6 Summary 178
9.7 Bibliographic Remarks 180
CHAPTER 10 ¢" The Bridge Problem 183
10.1 Lower and Upper Bounds 183
10.2 Outline Strategy 185
10.3 Regular Sequences 187
10.4 Sequencing Forward Trips 189
10.5 Choosing Settlers and Nomads 193
10.6 The Algorithm 196
10.7 Summary 199
10.8 Bibliographic Remarks 200
CHAPTER 11 ¢" Knight¢s Circuit 201
11.1 Straight-Move Circuits 202
11.2 Supersquares 206
11.3 Partitioning the Board 209
11.4 Summary 216
11.5 Bibliographic Remarks 218
PART II Mathematical Techniques 219
CHAPTER 12 ¢" The Language of Mathematics 221
12.1 Variables, Expressions and Laws 222
12.2 Sets 224
12.2.1 The Membership Relation 224
12.2.2 The Empty Set 224
12.2.3 Types/Universes 224
12.2.4 Union and Intersection 225
12.2.5 Set Comprehension 225
12.2.6 Bags 227
12.3 Functions 227
12.3.1 Function Application 228
12.3.2 Binary Operators 230
12.3.3 Operator Precedence 230
12.4 Types and Type Checking 232
12.4.1 Cartesian Product and Disjoint Sum 233
12.4.2 Function Types 235
12.5 Algebraic Properties 236
12.5.1 Symmetry 237
12.5.2 Zero and Unit 238
12.5.3 Idempotence 239
12.5.4 Associativity 240
12.5.5 Distributivity/Factorisation 241
12.5.6 Algebras 243
12.6 Boolean Operators 244
12.7 Binary Relations 246
12.7.1 Reflexivity 247
12.7.2 Symmetry 248
12.7.3 Converse 249
12.7.4 Transitivity 249
12.7.5 Anti-symmetry 251
12.7.6 Orderings 252
12.7.7 Equality 255
12.7.8 Equivalence Relations 256
12.8 Calculations 257
12.8.1 Steps in a Calculation 259
12.8.2 Relations between Steps 260
12.8.3 ¢¢If¢¢ and ¢¢Only If¢¢ 262
12.9 Exercises 264
CHAPTER 13 ¢" Boolean Algebra 267
13.1 Boolean Equality 267
13.2 Negation 269
13.3 Disjunction 270
13.4 Conjunction 271
13.5 Implication 274
13.5.1 Definitions and Basic Properties 275
13.5.2 Replacement Rules 276
13.6 Set Calculus 279
13.7 Exercises 281
CHAPTER 14 ¢" Quantifiers 285
14.1 DotDotDot and Sigmas 285
14.2 Introducing Quantifier Notation 286
14.2.1 Summation 287
14.2.2 Free and Bound Variables 289
14.2.3 Properties of Summation 291
14.2.4 Warning 297
14.3 Universal and Existential Quantification 297
14.3.1 Universal Quantification 298
14.3.2 Existential Quantification 300
14.4 Quantifier Rules 301
14.4.1 The Notation 302
14.4.2 Free and Bound Variables 303
14.4.3 Dummies 303
14.4.4 Range Part 303
14.4.5 Trading 304
14.4.6 Term Part 304
14.4.7 Distributivity Properties 304
14.5 Exercises 306
CHAPTER 15 ¢" Elements of Number Theory 309
15.1 Inequalities 309
15.2 Minimum and Maximum 312
15.3 The Divides Relation 315
15.4 Modular Arithmetic 316
15.4.1 Integer Division 316
15.4.2 Remainders and Modulo Arithmetic 320
15.5 Exercises 322
CHAPTER 16 ¢" Relations, Graphs and Path Algebras 325
16.1 Paths in a Directed Graph 325
16.2 Graphs and Relations 328
16.2.1 Relation Composition 330
16.2.2 Union of Relations 332
16.2.3 Transitive Closure 334
16.2.4 Reflexive Transitive Closure 338
16.3 Functional and Total Relations 339
16.4 Path-Finding Problems 341
16.4.1 Counting Paths 341
16.4.2 Frequencies 343
16.4.3 Shortest Distances 344
16.4.4 All Paths 345
16.4.5 Semirings and Operations on Graphs 347
16.5 Matrices 351
16.6 Closure Operators 353
16.7 Acyclic Graphs 354
16.7.1 Topological Ordering 355
16.8 Combinatorics 357
16.8.1 Basic Laws 358
16.8.2 Counting Choices 359
16.8.3 Counting Paths 361
16.9 Exercises 366
Solutions to Exercises 369
References 405
Index 407
