What Is an Algorithm?

1.1An algorithm is a recipe

An algorithm is a finite list of clear instructions that turns some input into some output. That is the whole definition. Making tea is an algorithm. Long division is an algorithm. The instructions for assembling a bookshelf are an algorithm — a bad one, but an algorithm.

Four things make a list of instructions count:

• Input — what you start with (tea leaves, a number, a list of names).
• Definite steps — each step is unambiguous. "Add salt to taste" is a human instruction; "add 2 grams of salt" is an algorithmic one.
• Finite — it ends. A recipe that says "stir until you feel it is right" may never end.
• Output — something comes out: a cup of tea, an answer, a sorted pile.

A second picture, if the kitchen one does not land: think of giving someone directions. "Head towards the tall building" depends on which building they are looking at; "turn left after 300 metres onto Mill Road" does not. Good directions and good algorithms share the same virtue — the person following them never has to guess what you meant. A computer is the most literal follower you will ever meet: it does exactly what you wrote, never what you intended.

1.2The dictionary, and the whole course in one example

Suppose you have a paper dictionary of 1000 pages and you want the word "quokka". Here are two correct methods.

Method A — page by page

1. Open page 1. Is "quokka" here? No.
2. Open page 2. Is it here? No.
3. … keep going until you find it.

This works. It always works. For "quokka", sitting somewhere around page 700, it costs about 700 page-opens.

Method B — open in the middle

1. Open the middle page. Are we past "quokka" alphabetically? If yes, throw away the right half; if no, throw away the left half.
2. Open the middle of what is left. Throw away half again.
3. Repeat until you land on the word.

Each step halves the problem: 1000 → 500 → 250 → 125 → 63 → 32 → 16 → 8 → 4 → 2 → 1. That is about 10 page-opens.

Look at the right-hand column again. The dictionary grew a million times bigger and method B needed ten extra looks. That is not a small improvement, it is a different category of solution. Noticing which category a method belongs to — before you write it, and confirmed by measurement afterwards — is what "algorithm analysis" means.

1.3A first look at how work grows

Drag the slider below. Each row is a different kind of method — one that ignores the input size, one that halves like our dictionary trick, one that looks at everything once, and one that compares every item with every other item.

You do not need the names yet. The only thing to take away today: the gaps between these rows are not "a bit slower". At n = 1000 the bottom rows are already thousands of times more expensive, and they get worse from there.

1.4Correct is the floor, not the goal

When we judge a piece of code in this course, we ask three questions in order:

1. Is it correct? Does it give the right answer for every input, including the empty and the weird ones? If not, nothing else matters.
2. Can a human read it? Code is read far more often than it is written — by other people, and by you in three months.
3. What does it cost? How much time does it use as the input grows, and how much memory?

Weeks 1–6 are mostly about the first two. From week 7 on, the third question takes over — and it is the one that separates a program that works on your ten test rows from one that still works on the real ten million.

1.5Counting steps by hand: a worked trace

Before a computer counts anything for us, we should be able to count by hand. Here is the number-guessing game — a friend thinks of a number from 1 to 100, and after each guess they tell you "higher", "lower" or "correct". Watch the halving method play it, step by step, when the secret number is 73.

Six looks, and the worst any number could take is seven. Every look throws away half of what is left: 100 → 50 → 25 → 13 → 7 → 4 → 2 → 1. The counting-up method, by contrast, could take all 100 guesses. Notice how we did the analysis: we did not run anything, we did not time anything — we simply followed the rules on paper and counted the looks. That is the same move we will automate with a computer in week 3, and it is the backbone of everything after.

1.6Setting up: Google Colab in four steps

You will not install anything. Colab is Python running on someone else's computer, displayed in your browser tab.

1. Go to colab.research.google.com and sign in with a Google account.
2. Choose File → New notebook.
3. Click the grey box (a "cell") and type the line below.
4. Press Shift + Enter to run it.

print("Hello, algorithms!")

If you see that line under the cell, you are done: you have a working Python environment and you never have to think about installation again. Rename the notebook AA_Week01.ipynb (click the title at the top left) and keep it — every week you will start a new one and keep them all in one Drive folder.

One cell can do more than one thing. Type these three lines into a new cell and run it — print shows text, but it can also do arithmetic and narrate a plan:

print("Step 1: open the middle page")
print("Halving 1000 pages needs about", 10, "looks")
print(1000 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2)

That last line halved 1000 ten times in a row and landed just below 1 — the arithmetic behind "ten looks", done by the machine. We are not writing real programs yet; we are just checking that the tool obeys us. From week 2 we build up properly.

1.7Common mistakes when you describe a method

Most first attempts at writing an algorithm fail in one of three ways. All three come from the same root — assuming the follower knows what you know. Learn to spot them on paper now and you will spot them in your code for the rest of the course.

Here is the same idea as a tiny story. You tell a friend: "To find the largest of these ten cards, look through them and pick the biggest." It sounds complete. But a truly literal follower asks: pick the biggest compared with what? The reliable version keeps a "biggest so far", starts it at the first card, and updates it only when a bigger card appears. Spelling out that hidden "so far" is the difference between a method a person can guess and one a computer can run.

1.8Try it yourself

1.9Self-check

1.10Homework

1.11Words from this week