Table of Contents for

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 Equality

5.2.4     Hidden Treasures

5.2.5     Equals for Equals

5.3     Equivalence and Continued Equalities

5.3.1     Examples of the Associativity of Equivalence

5.3.2     On Natural Language

5.4     Negation

5.4.1     Contraposition

5.4.2     Handshake Problems

5.4.3     Inequivalence

5.5     Summary

5.6     Bibliographic Remarks

C H A P T E R 6 – Induction

6.1     Example Problems

6.2     Cutting the Plane

6.3     Triominoes

6.4     Looking for Patterns

6.5     The Need for Proof

6.6     From Verification to Construction

6.7     Summary

6.8     Bibliographic Remarks

C H A P T E R 7 – Fake-Coin Detection

7.1     Problem Formulation

7.2     Problem Solution

7.2.1     The Basis

7.2.2     Induction Step

7.2.3     The Marked-Coin Problem

7.2.4     The Complete Solution

7.3     Summary

7.4     Bibliographic Remarks

C H A P T E R 8 – The Tower of Hanoi

8.1     Specification and Solution

8.1.1     The End of the World!

8.1.2     Iterative Solution

8.1.3     Why?

8.2     Inductive Solution

8.3     The Iterative Solution

8.4     Summary

8.5     Bibliographic Remarks

C H A P T E R 9 – Principles of Algorithm Design

9.1     Iteration, Invariants and Making Progress

9.2     A Simple Sorting Problem

9.3     Binary Search

9.4     Sam Loyd’s Chicken-Chasing Problem

9.4.1     Cornering the Prey

9.4.2     Catching the Prey

9.4.3     Optimality

9.5     Projects

9.6     Summary

9.7     Bibliographic Remarks

C H A P T E R 10 – The Bridge Problem

10.1   Lower and Upper Bounds

10.2   Outline Strategy

10.3   Regular Sequences

10.4   Sequencing Forward Trips

10.5   Choosing Settlers and Nomads

10.6   The Algorithm

10.7   Summary

10.8   Bibliographic Remarks

C H A P T E R 11 – Knight’s Circuit

11.1   Straight-Move Circuits

11.2   Supersquares

11.3   Partitioning the Board

11.4   Summary

11.5   Bibliographic Remarks

PART II   Mathematical Techniques

C H A P T E R 12 – The Language of Mathematics

12.1   Variables, Expressions and Laws

12.2   Sets

12.2.1   The Membership Relation

12.2.2   The Empty Set

12.2.3   Types/Universes

12.2.4   Union and Intersection

12.2.5   Set Comprehension

12.2.6   Bags

12.3   Functions

12.3.1   Function Application

12.3.2   Binary Operators

12.3.3   Operator Precedence

12.4   Types and Type Checking

12.4.1   Cartesian Product and Disjoint Sum

12.4.2   Function Types

12.5   Algebraic Properties

12.5.1   Symmetry

12.5.2   Zero and Unit

12.5.3   Idempotence

12.5.4   Associativity

12.5.5   Distributivity/Factorisation

12.5.6   Algebras

12.6   Boolean Operators

12.7   Binary Relations

12.7.1   Reflexivity

12.7.2   Symmetry

12.7.3   Converse

12.7.4   Transitivity

12.7.5   Anti-symmetry

12.7.6   Orderings

12.7.7   Equality

12.7.8   Equivalence Relations

12.8   Calculations

12.8.1   Steps in a Calculation

12.8.2   Relations between Steps

12.8.3   “If” and “Only If”

12.9   Exercises

C H A P T E R 13 – Boolean Algebra

13.1   Boolean Equality

13.2   Negation

13.3   Disjunction

13.4   Conjunction

13.5   Implication

13.5.1   Definitions and Basic Properties

13.5.2   Replacement Rules

13.6   Set Calculus

13.7   Exercises

C H A P T E R 14 – Quantifiers

14.1   DotDotDot and Sigmas

14.2   Introducing Quantifier Notation

14.2.1   Summation

14.2.2   Free and Bound Variables

14.2.3   Properties of Summation

14.2.4   Warning

14.3   Universal and Existential Quantification

14.3.1   Universal Quantification

14.3.2   Existential Quantification

14.4   Quantifier Rules

14.4.1   The Notation

14.4.2   Free and Bound Variables

14.4.3   Dummies

14.4.4   Range Part

14.4.5   Trading

14.4.6   Term Part

14.4.7   Distributivity Properties

14.5   Exercises

C H A P T E R 15 – Elements of Number Theory

15.1   Inequalities

15.2   Minimum and Maximum

15.3   The Divides Relation

15.4   Modular Arithmetic

15.4.1   Integer Division

15.4.2   Remainders and Modulo Arithmetic

15.5   Exercises

C H A P T E R 16 – Relations, Graphs and Path Algebras

16.1   Paths in a Directed Graph

16.2   Graphs and Relations

16.2.1   Relation Composition

16.2.2   Union of Relations

16.2.3   Transitive Closure

16.2.4   Reflexive Transitive Closure

16.3   Functional and Total Relations

16.4   Path-Finding Problems

16.4.1   Counting Paths

16.4.2   Frequencies

16.4.3   Shortest Distances

16.4.4   All Paths

16.4.5   Semirings and Operations on Graphs

16.5   Matrices

16.6   Closure Operators

16.7   Acyclic Graphs

16.7.1   Topological Ordering

16.8   Combinatorics

16.8.1   Basic Laws

16.8.2   Counting Choices

16.8.3   Counting Paths

16.9   Exercises

Solutions to Exercises

References

Index