Algorithms: Step by Step

Think of making chiya. You don’t do it any old way: water and milk in the pot, tea leaves, sugar, boil, strain into a cup. Anyone who follows those steps, in that order, gets chiya.

A list of steps like that, which does a job or solves a problem, is called an algorithm. Each step is an instruction. A good algorithm has three things:

• every step is clear and exact, with only one meaning;
• the steps are in the right order;
• it comes to an end, and when it ends, the job is done.

You follow algorithms every day. A recipe is one. So are the steps to wash your hands properly, to tie a shoelace, to pay a bill on a phone, and the way a bus conductor collects fares, stop after stop. Your teacher follows one to do a long division on the board.

Computers follow algorithms too. In Unit 1 you saw that a computer follows a program: a program is an algorithm written in a way a computer can carry out. Every app on a phone is built from them: the steps that put a photo on the screen, find a word in a message, or work out the shortest way across a city. A computer is very fast and never gets tired, but it only follows its algorithms; it can’t make one up for itself. People write them.

Here is how a grandmother might tell you to make chiya:

Boil some water and milk, put in the tea, add sugar, and let it boil till it’s done.

You could follow that, because you have seen chiya made. You would guess how much water, how much tea, and when it is “done”. But give it to someone who has never made chiya, and they would have to ask a lot of questions. How much is “some”? Which tea, leaves or a tea bag? How much sugar? How long is “till it’s done”?

A computer can’t ask and can’t guess. So an algorithm for a computer has to answer every one of those questions before it is asked:

1. Pour 1 cup of water and 1 cup of milk into the pot.
2. Turn the stove on.
3. Add 2 spoons of tea leaves and 2 spoons of sugar.
4. Boil for 3 minutes.
5. Turn the stove off.
6. Strain the chiya into 2 cups.

Every amount is a number, every step is one action, and nothing is left for the reader to work out. Being precise means being exact like this: each instruction has only one meaning.

The steps of an algorithm are done one after another, in order, from the first to the last. This is called sequence. The order matters: “strain the chiya, then boil it” uses the same two steps as “boil the chiya, then strain it”, but only one of them gives you hot chiya.

Some steps can swap places without any harm: it doesn’t matter whether the tea leaves or the sugar go into the pot first. Others can’t: the boiling must come after everything is in the pot, and the straining after the boiling.

Directions are an algorithm too. To give them exactly, you need words that mean the same thing every time. “Forward one block”, “turn left” and “turn right” are good ones.

But be careful: left and right depend on the way you are facing. If you face north, your left is west. If you turn round and face south, your left is east. So an instruction like “turn left” only makes sense if the person following it knows which way they are facing, and an algorithm must keep track of that, one step at a time.

Look at those directions again: “forward, forward, forward”. When a step is done again and again, it is shorter and clearer to say so once: forward 3 times. Doing the same steps again is called repetition.

There are two kinds:

• Repeat a number of times, when you know how many times before you start: “Fold 40 momos: repeat 40 times: put a spoon of filling on a wrapper, then fold and pinch it shut.”
• Repeat until something happens, when you don’t know how many times: “Stir until the sugar has dissolved.” “Keep walking forward until you reach Taumadhi Square.” After each time round, you check: has it happened yet? If not, go round again.

Repetition makes algorithms shorter, and easier to change: to fold 60 momos instead of 40, you change one number, instead of writing the steps out twenty more times.

Not every step should be done every time. You take an umbrella if it is raining. You add sugar to someone’s chiya if they like it sweet. A step like that, which happens only when something is true, is a choice.

A choice asks a question that has only two answers, yes or no. The question is called the condition. Then:

• If the answer is yes, do these steps.
• Otherwise, do those steps (or nothing).

Choices let one algorithm handle different situations. In the spring festival of Bisket Jatra, the great chariot of Bhairab is pulled in Taumadhi Square, beside Nyatapola, and the square is full of people. Your directions could say: “If the chariot is in the square, go round by the next street; otherwise, walk straight across.”

Sequence, repetition and choices are the three ways of putting steps together. Computer scientists have shown that these three, with a way to remember things (the next section), are enough to write any algorithm there is, from chiya to the programs on a phone. In Unit 4 you will meet them again, as blocks a computer can run.

Watch the scorer at a cricket match. After every ball, the scorer writes down a few things: how many runs the team has, how many wickets have fallen, the name of the batter facing the next ball, and whether it is the last over yet. The numbers change all through the match, but the scorer always knows where to find them.

An algorithm needs to remember things in the same way. A named place that holds one piece of information, which can change while the algorithm runs, is called a variable. Think of it as a box with a name written on it: you can look at what is inside, and you can take it out and put something new in.

Different variables hold different kinds of information, called data types. The three you will use most are:

The type matters because of what you can do with it. You can add two numbers; you can’t add two names. A yes/no variable is just right for a condition: “if raining is yes, take an umbrella”.

A variable makes an algorithm work for everyone, not only for one person. Here is an algorithm a tea shop could use for any customer’s bill:

1. Ask the customer’s name. Keep it in name (text).
2. Ask how many cups. Keep the number in cups (number).
3. Ask “Milk tea?” Keep the answer in milk (yes/no).
4. If milk is yes, price = 30. Otherwise, price = 20.
5. bill = cups × price.
6. Say: “name, please pay Rs bill.”

The same six lines work for Hari with 2 cups of milk tea and for Maya with 5 cups of black tea. Only what is inside the boxes changes. (The prices here are made up for a pretend shop.) Hari’s name, 2 cups and “yes” are the algorithm’s input, the information it is given to work on; “Hari, please pay Rs 60” is its output. These are the same input and output you met in Unit 1: a computer running this algorithm would take the input from a keyboard or a touchscreen and show the output on a screen.

In Grade 7 you will make variables in a block program, and build a quiz that keeps your score in one.

How do you know an algorithm is right? Not by reading it and feeling sure. You check it, by following it exactly for some inputs, and comparing what it gives with the answer you know is right.

Following an algorithm by hand, step by step, exactly as a computer would, is called tracing it. As you trace, you write down the value of every variable after each step in a table, called a trace table. Each row is one step; each column is one variable. Here is the tea shop’s algorithm traced for Hari, who wants 2 cups of milk tea:

Milk tea is Rs 30 a cup, so 2 cups should be Rs 60. The algorithm gives Rs 60: it is right, for this input. Trying an algorithm with an input whose right answer you already know is called a test.

Now the shop adds a rule: buy 5 cups or more and get Rs 10 off. Someone adds a line to the algorithm. Is the new line right? Trace it and see.

Notice which test found the bug: Maya’s, with exactly 5 cups, right at the edge of the rule. Hari and Ram both passed, so with only those two tests the bug would have stayed hidden. Choose tests that try every part of an algorithm: each answer of every choice, and the values right at the edges.

A mistake in an algorithm is called a bug. (Unit 4 tells the story of where that name came from.) Finding a bug and fixing it is called debugging. Bugs are normal. Everyone who writes algorithms writes bugs; good algorithm writers are good at finding them.

You have already met the most common kinds of bug:

• a missing step: the stove left on, the chiya never strained;
• steps in the wrong order: straining before boiling;
• a step that isn’t exact: “some sugar”, “boil until it’s ready”;
• a wrong choice: “more than 5” where it should be “5 or more”;
• a repeat that never ends: “stir until the chiya turns blue”.

To debug an algorithm:

1. Find a test that fails: an input where the result isn’t what it should be.
2. Trace it and find the first step where things go wrong. Everything after that may go wrong too, but the bug is usually at, or just before, the first wrong step.
3. Fix that one thing, and only that.
4. Test again, with the test that failed and with all the others.