Algorithmic Problem Solving

Contents v
Preface xi
@=16
1 \em Introduction 3
-  1.1 Algorithms 3
-  1.2 Algorithmic Problem Solving 4
-  1.3 Overview 5
-  1.4 Bibliographic Remarks 6
2 \em 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
3 \em 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
4 \em 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
5 \em 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
6 \em 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
7 \em 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
8 \em 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
9 \em 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
10 \em 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
11 \em 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
12 \em 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 \l"If\r" and \l"Only If\r" 262
-  12.9 Exercises 264
13 \em 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
14 \em 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
15 \em 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
16 \em 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