Algorithmic Problem Solving

An entertaining and captivating way to learn the fundamentals of using algorithms to solve problems The algorithmic approach to solving problems in computer technology is an essential tool. With this unique book, algorithm guru Roland Backhouse shares his four decades of experience to teach the fundamental principles of using algorithms to solve problems. Using fun and well-known puzzles to gradually introduce different aspects of algorithms in mathematics and computing. Backhouse presents you with a readable, entertaining, and energetic book that will motivate and challenge you to open your mind to the algorithmic nature of problem solving. Provides a novel approach to the mathematics of problem solving focusing on the algorithmic nature of problem solving Uses popular and entertaining puzzles to teach you different aspects of using algorithms to solve mathematical and computing challenges Features a theory section that supports each of the puzzles presented throughout the book Assumes only an elementary understanding of mathematics Let Roland Backhouse and his four decades of experience show you how you can solve challenging problems with algorithms!

Table of Contents:
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