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