Algorithmic Problem Solving

Algorithmic Problem Solving

by
Released December 2011
Publisher(s): Wiley
ISBN: 9780470684535

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to live online training experiences, plus books, videos, and digital content from O’Reilly and nearly 200 trusted publishing partners.

Start your free trial

Book description

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

  1. Coverpage
  2. Titlepage
  3. Copyright
  4. Contents
  5. Preface
  6. PART I: Algorithmic Problem Solving
    1. CHAPTER 1: Introduction
      1. 1.1 Algorithms
      2. 1.2 Algorithmic Problem Solving
      3. 1.3 Overview
      4. 1.4 Bibliographic Remarks
    2. CHAPTER 2: Invariants
      1. 2.1 Chocolate Bars
      2. 2.2 Empty Boxes
      3. 2.3 The Tumbler Problem
      4. 2.4 Tetrominoes
      5. 2.5 Summary
      6. 2.6 Bibliographic Remarks
    3. CHAPTER 3: Crossing a River
      1. 3.1 Problems
      2. 3.2 Brute Force
      3. 3.3 Nervous Couples
      4. 3.4 Rule of Sequential Composition
      5. 3.5 The Bridge Problem
      6. 3.6 Conditional Statements
      7. 3.7 Summary
      8. 3.8 Bibliographic Remarks
    4. CHAPTER 4: Games
      1. 4.1 Matchstick Games
      2. 4.2 Winning Strategies
      3. 4.3 Subtraction-Set Games
      4. 4.4 Sums of Games
      5. 4.5 Summary
      6. 4.6 Bibliographic Remarks
    5. CHAPTER 5: Knights and Knaves
      1. 5.1 Logic Puzzles
      2. 5.2 Calculational Logic
      3. 5.3 Equivalence and Continued Equalities
      4. 5.4 Negation
      5. 5.5 Summary
      6. 5.6 Bibliographic Remarks
    6. CHAPTER 6: Induction
      1. 6.1 Example Problems
      2. 6.2 Cutting the Plane
      3. 6.3 Triominoes
      4. 6.4 Looking for Patterns
      5. 6.5 The Need for Proof
      6. 6.6 From Verification to Construction
      7. 6.7 Summary
      8. 6.8 Bibliographic Remarks
    7. CHAPTER 7: Fake-Coin Detection
      1. 7.1 Problem Formulation
      2. 7.2 Problem Solution
      3. 7.3 Summary
      4. 7.4 Bibliographic Remarks
    8. CHAPTER 8: The Tower of Hanoi
      1. 8.1 Specification and Solution
      2. 8.2 Inductive Solution
      3. 8.3 The Iterative Solution
      4. 8.4 Summary
      5. 8.5 Bibliographic Remarks
    9. CHAPTER 9: Principles of Algorithm Design
      1. 9.1 Iteration, Invariants and Making Progress
      2. 9.2 A Simple Sorting Problem
      3. 9.3 Binary Search
      4. 9.4 Sam Loyd’s Chicken-Chasing Problem
      5. 9.5 Projects
      6. 9.6 Summary
      7. 9.7 Bibliographic Remarks
    10. CHAPTER 10: The Bridge Problem
      1. 10.1 Lower and Upper Bounds
      2. 10.2 Outline Strategy
      3. 10.3 Regular Sequences
      4. 10.4 Sequencing Forward Trips
      5. 10.5 Choosing Settlers and Nomads
      6. 10.6 The Algorithm
      7. 10.7 Summary
      8. 10.8 Bibliographic Remarks
    11. CHAPTER 11: Knight’s Circuit
      1. 11.1 Straight-Move Circuits
      2. 11.2 Supersquares
      3. 11.3 Partitioning the Board
      4. 11.4 Summary
      5. 11.5 Bibliographic Remarks
  7. PART II: Mathematical Techniques
    1. CHAPTER 12: The Language of Mathematics
      1. 12.1 Variables, Expressions and Laws
      2. 12.2 Sets
      3. 12.3 Functions
      4. 12.4 Types and Type Checking
      5. 12.5 Algebraic Properties
      6. 12.6 Boolean Operators
      7. 12.7 Binary Relations
      8. 12.8 Calculations
      9. 12.9 Exercises
    2. CHAPTER 13: Boolean Algebra
      1. 13.1 Boolean Equality
      2. 13.2 Negation
      3. 13.3 Disjunction
      4. 13.4 Conjunction
      5. 13.5 Implication
      6. 13.6 Set Calculus
      7. 13.7 Exercises
    3. CHAPTER 14: Quantifiers
      1. 14.1 DotDotDot and Sigmas
      2. 14.2 Introducing Quantifier Notation
      3. 14.3 Universal and Existential Quantification
      4. 14.4 Quantifier Rules
      5. 14.5 Exercises
    4. CHAPTER 15: Elements of Number Theory
      1. 15.1 Inequalities
      2. 15.2 Minimum and Maximum
      3. 15.3 The Divides Relation
      4. 15.4 Modular Arithmetic
      5. 15.5 Exercises
    5. CHAPTER 16: Relations, Graphs and Path Algebras
      1. 16.1 Paths in a Directed Graph
      2. 16.2 Graphs and Relations
      3. 16.3 Functional and Total Relations
      4. 16.4 Path-Finding Problems
      5. 16.5 Matrices
      6. 16.6 Closure Operators
      7. 16.7 Acyclic Graphs
      8. 16.8 Combinatorics
      9. 16.9 Exercises
  8. Solutions to Exercises
  9. References
  10. Index

Product information

  • Title: Algorithmic Problem Solving
  • Author(s):
  • Release date: December 2011
  • Publisher(s): Wiley
  • ISBN: 9780470684535