Algorithmic Problem Solving

Contents

Preface

PART  I   Algorithmic Problem Solving

C H A P T E R 1 – Introduction

1.1     Algorithms

1.2     Algorithmic Problem Solving

1.3     Overview

1.4     Bibliographic Remarks

C H A P T E R 2 – Invariants

2.1     Chocolate Bars

2.1.1     The Solution

2.1.2     The Mathematical Solution

2.2     Empty Boxes

2.2.1     Review

2.3     The Tumbler Problem

2.3.1     Non-deterministic Choice

2.4     Tetrominoes

2.5     Summary

2.6     Bibliographic Remarks

C H A P T E R 3 – Crossing a River

3.1     Problems

3.2     Brute Force

3.2.1     Goat, Cabbage and Wolf

3.2.2     State-Space Explosion

3.2.3     Abstraction

3.3     Nervous Couples

3.3.1     What Is the Problem?

3.3.2     Problem Structure

3.3.3     Denoting States and Transitions

3.3.4     Problem Decomposition

3.3.5     A Review

3.4     Rule of Sequential Composition

3.5     The Bridge Problem

3.6     Conditional Statements

3.7     Summary

3.8     Bibliographic Remarks

C H A P T E R 4 – Games

4.1     Matchstick Games

4.2     Winning Strategies

4.2.1     Assumptions

4.2.2     Labelling Positions

4.2.3     Formulating Requirements

4.3     Subtraction-Set Games

4.4     Sums of Games

4.4.1     A Simple Sum Game

4.4.2     Maintain Symmetry!

4.4.3     More Simple Sums

4.4.4     Evaluating Positions

4.4.5     Using the Mex Function

4.5     Summary

4.6     Bibliographic Remarks

C H A P T E R 5 – Knights and Knaves

5.1     Logic Puzzles

5.2     Calculational Logic

5.2.1     Propositions

5.2.2     Knights and Knaves

5.2.3     Boolean ...