A First Taste of Algorithms

Chapter 1: Two Questions

✦ ✦ ✦

In which a guessing game turns out to contain most of this book

The game

Here is a game you have probably played. I think of a whole number between 1 and 100. You ask yes-or-no questions; I answer honestly; you win when you name the number.

You could ask “Is it 1?” — “Is it 2?” — “Is it 3?” and grind your way up. You will win eventually. If you are unlucky, it takes a hundred questions.

Or you could ask: “Is it bigger than 50?”

Stop and feel what that question does. Whatever I answer — yes or no — half the numbers die. One question, fifty suspects eliminated, no matter what. The grinding strategy eliminates one suspect per question on a bad day. This question eliminates fifty on its worst day.

Ask it again on whatever half survives: “bigger than 75?” or “bigger than 25?” Each question halves the survivors. From 100: down to 50, 25, 13, 7, 4, 2, 1. Seven questions and you have me cornered, guaranteed, no luck required.

Play it once with someone before reading on — really. Pick the range 1 to 1000 and see whether ten questions suffice. (They do. By the end of this chapter you will be able to say exactly why, and exactly how many questions a range of a trillion would need. The answer will be smaller than you think.)

This game, taken seriously, contains the two questions this entire book asks, over and over, of every procedure we meet:

Does it work? — not “did it work that time,” but: does it always work, for every number I might have picked?
What does it cost? — counted in questions, in steps, in moves; counted, not guessed.

A procedure precise enough to be followed without judgment, together with answers to those two questions, is what this book means by an algorithm. The word comes from a person — al-Khwārizmī, a ninth-century scholar in Baghdad whose textbook on calculation was so widely followed that his name became the name for following a recipe exactly. We will be choosy, though: a recipe is only interesting to us once we can say what it promises and what it charges.

All 32 chapters of A First Taste of Algorithms · Foundations · All courses