Algorithmic Problem Solving

Roland Backhouse leads the Foundations of Programming research group at the University of Nottingham. He returned to the UK in 1999 after spending 13 years in the Netherlands, 9 of which as professor at Eindhoven University of Technology (the institution that pioneered the style of reasoning and construction of programs that forms the basis for this book).

• Preface xiPART I Algorithmic Problem Solving 1CHAPTER 1 – Introduction 31.1 Algorithms 31.2 Algorithmic Problem Solving 41.3 Overview 51.4 Bibliographic Remarks 6CHAPTER 2 – Invariants 72.1 Chocolate Bars 102.1.1 The Solution 102.1.2 The Mathematical Solution 112.2 Empty Boxes 162.2.1 Review 192.3 The Tumbler Problem 222.3.1 Non-deterministic Choice 232.4 Tetrominoes 242.5 Summary 302.6 Bibliographic Remarks 34CHAPTER 3 – Crossing a River 353.1 Problems 363.2 Brute Force 373.2.1 Goat, Cabbage and Wolf 373.2.2 State-Space Explosion 393.2.3 Abstraction 413.3 Nervous Couples 423.3.1 What Is the Problem? 423.3.2 Problem Structure 433.3.3 Denoting States and Transitions 443.3.4 Problem Decomposition 453.3.5 A Review 483.4 Rule of Sequential Composition 503.5 The Bridge Problem 543.6 Conditional Statements 633.7 Summary 653.8 Bibliographic Remarks 65CHAPTER 4 – Games 674.1 Matchstick Games 674.2 Winning Strategies 694.2.1 Assumptions 694.2.2 Labelling Positions 704.2.3 Formulating Requirements 724.3 Subtraction-Set Games 744.4 Sums of Games 784.4.1 A Simple Sum Game 794.4.2 Maintain Symmetry! 814.4.3 More Simple Sums 824.4.4 Evaluating Positions 834.4.5 Using the Mex Function 874.5 Summary 914.6 Bibliographic Remarks 92CHAPTER 5 – Knights and Knaves 955.1 Logic Puzzles 955.2 Calculational Logic 965.2.1 Propositions 965.2.2 Knights and Knaves 975.2.3 Boolean Equality 985.2.4 Hidden Treasures 1005.2.5 Equals for Equals 1015.3 Equivalence and Continued Equalities 1025.3.1 Examples of the Associativity of Equivalence 1045.3.2 On Natural Language 1055.4 Negation 1065.4.1 Contraposition 1095.4.2 Handshake Problems 1125.4.3 Inequivalence 1135.5 Summary 1175.6 Bibliographic Remarks 117CHAPTER 6 – Induction 1196.1 Example Problems 1206.2 Cutting the Plane 1236.3 Triominoes 1266.4 Looking for Patterns 1286.5 The Need for Proof 1296.6 From Verification to Construction 1306.7 Summary 1346.8 Bibliographic Remarks 134CHAPTER 7 – Fake-Coin Detection 1377.1 Problem Formulation 1377.2 Problem Solution 1397.2.1 The Basis 1397.2.2 Induction Step 1397.2.3 The Marked-Coin Problem 1407.2.4 The Complete Solution 1417.3 Summary 1467.4 Bibliographic Remarks 146CHAPTER 8 – The Tower of Hanoi 1478.1 Specification and Solution 1478.1.1 The End of the World! 1478.1.2 Iterative Solution 1488.1.3 Why? 1498.2 Inductive Solution 1498.3 The Iterative Solution 1538.4 Summary 1568.5 Bibliographic Remarks 156CHAPTER 9 – Principles of Algorithm Design 1579.1 Iteration, Invariants and Making Progress 1589.2 A Simple Sorting Problem 1609.3 Binary Search 1639.4 Sam Loyd’s Chicken-Chasing Problem 1669.4.1 Cornering the Prey 1709.4.2 Catching the Prey 1749.4.3 Optimality 1769.5 Projects 1779.6 Summary 1789.7 Bibliographic Remarks 180CHAPTER 10 – The Bridge Problem 18310.1 Lower and Upper Bounds 18310.2 Outline Strategy 18510.3 Regular Sequences 18710.4 Sequencing Forward Trips 18910.5 Choosing Settlers and Nomads 19310.6 The Algorithm 19610.7 Summary 19910.8 Bibliographic Remarks 200CHAPTER 11 – Knight’s Circuit 20111.1 Straight-Move Circuits 20211.2 Supersquares 20611.3 Partitioning the Board 20911.4 Summary 21611.5 Bibliographic Remarks 218PART II Mathematical Techniques 219CHAPTER 12 – The Language of Mathematics 22112.1 Variables, Expressions and Laws 22212.2 Sets 22412.2.1 The Membership Relation 22412.2.2 The Empty Set 22412.2.3 Types/Universes 22412.2.4 Union and Intersection 22512.2.5 Set Comprehension 22512.2.6 Bags 22712.3 Functions 22712.3.1 Function Application 22812.3.2 Binary Operators 23012.3.3 Operator Precedence 23012.4 Types and Type Checking 23212.4.1 Cartesian Product and Disjoint Sum 23312.4.2 Function Types 23512.5 Algebraic Properties 23612.5.1 Symmetry 23712.5.2 Zero and Unit 23812.5.3 Idempotence 23912.5.4 Associativity 24012.5.5 Distributivity/Factorisation 24112.5.6 Algebras 24312.6 Boolean Operators 24412.7 Binary Relations 24612.7.1 Reflexivity 24712.7.2 Symmetry 24812.7.3 Converse 24912.7.4 Transitivity 24912.7.5 Anti-symmetry 25112.7.6 Orderings 25212.7.7 Equality 25512.7.8 Equivalence Relations 25612.8 Calculations 25712.8.1 Steps in a Calculation 25912.8.2 Relations between Steps 26012.8.3 ‘‘If’’ and ‘‘Only If’’ 26212.9 Exercises 264CHAPTER 13 – Boolean Algebra 26713.1 Boolean Equality 26713.2 Negation 26913.3 Disjunction 27013.4 Conjunction 27113.5 Implication 27413.5.1 Definitions and Basic Properties 27513.5.2 Replacement Rules 27613.6 Set Calculus 27913.7 Exercises 281CHAPTER 14 – Quantifiers 28514.1 DotDotDot and Sigmas 28514.2 Introducing Quantifier Notation 28614.2.1 Summation 28714.2.2 Free and Bound Variables 28914.2.3 Properties of Summation 29114.2.4 Warning 29714.3 Universal and Existential Quantification 29714.3.1 Universal Quantification 29814.3.2 Existential Quantification 30014.4 Quantifier Rules 30114.4.1 The Notation 30214.4.2 Free and Bound Variables 30314.4.3 Dummies 30314.4.4 Range Part 30314.4.5 Trading 30414.4.6 Term Part 30414.4.7 Distributivity Properties 30414.5 Exercises 306CHAPTER 15 – Elements of Number Theory 30915.1 Inequalities 30915.2 Minimum and Maximum 31215.3 The Divides Relation 31515.4 Modular Arithmetic 31615.4.1 Integer Division 31615.4.2 Remainders and Modulo Arithmetic 32015.5 Exercises 322CHAPTER 16 – Relations, Graphs and Path Algebras 32516.1 Paths in a Directed Graph 32516.2 Graphs and Relations 32816.2.1 Relation Composition 33016.2.2 Union of Relations 33216.2.3 Transitive Closure 33416.2.4 Reflexive Transitive Closure 33816.3 Functional and Total Relations 33916.4 Path-Finding Problems 34116.4.1 Counting Paths 34116.4.2 Frequencies 34316.4.3 Shortest Distances 34416.4.4 All Paths 34516.4.5 Semirings and Operations on Graphs 34716.5 Matrices 35116.6 Closure Operators 35316.7 Acyclic Graphs 35416.7.1 Topological Ordering 35516.8 Combinatorics 35716.8.1 Basic Laws 35816.8.2 Counting Choices 35916.8.3 Counting Paths 36116.9 Exercises 366Solutions to Exercises 369References 405Index 407