Algorithmic Problem Solving - Backhouse, Roland

. .

Résumé :

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