What an algorithm is

Inputs, processes and outputs; what makes an algorithm precise; programs implement algorithms.

F5.1AlgorithmsGCSE12 min

Before anyone writes a program, someone has to work out the steps. A set of steps that solves a problem is an algorithm. Algorithms are older than computers: a recipe is one, and so is the method you learned for long division. This module is about designing, describing, checking and comparing them, starting with what makes a good one.

An algorithm is not a program

Here is an algorithm for drawing any regular shape with the robot, written in plain English:

1. Ask how many sides the shape should have.
2. Work out the turn at each corner: 360 degrees divided by the number of sides.
3. Repeat once for each side: drive forward 20 cm, then turn by the corner angle.
4. Say how many sides were drawn.

No Python there, and no robot commands. Anyone could follow it with a pen and paper. Here is the same algorithm as a program:

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

sides = int(input("How many sides? "))
angle = 360 / sides
for i in range(sides):
    forward(60, distance=20)
    turn_right(30, angle=angle)
print("drew a shape with", sides, "sides")

Run this in the simulator

The algorithm is the method. The program is that method written in one particular language, for one particular machine. The same algorithm could become a program in C, in Scratch, or in exam pseudocode, and it would still be the same algorithm.

Inputs, processes and outputs

Every algorithm takes something in, does something with it, and gives something out:

Listing these first is often the easiest way into a problem. If you cannot say what the inputs and outputs are, you do not understand the problem yet.

What makes a good algorithm

Try following these instructions exactly as written:

1. Drive towards the wall.
2. Stop when you are close.

A person can do it. A computer cannot, because towards and close are not precise. How fast? How close is close? When do you check? A good algorithm is:

• Unambiguous: every step means exactly one thing.
• Finite: it always finishes, it does not run forever.
• Correct: it gives the right output for every valid input, not just the one you tried.

Here is the wall algorithm made precise, and its program:

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

# 1. While the distance ahead is more than 25 cm:
#    1a. drive forward 5 cm.
# 2. Output the distance left.
while distance() > 25:
    forward(50, distance=5)
print("stopped", distance(), "cm from the wall")

Run this in the simulator

Writing the algorithm as comments first, then the code under each step, is a habit worth keeping.

Many algorithms, one problem

There is usually more than one algorithm for a problem, and some are better than others. To find out whether the number 97 is prime, you could try dividing by every number from 2 to 96, or only up to 9, because a factor bigger than 9 would need a partner smaller than 9. Both are correct; the second does about a tenth of the work. Much of this module is about comparing algorithms like that.

Task: any shape from an answer

Turn the shape algorithm into a program. Ask How many sides?, work out the corner angle, drive the shape with 20 cm sides, and print drew a shape with <n> sides. The task answers 5. Work the angle out; do not type it.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

# 1. Ask how many sides.
# 2. Work out the angle.
# 3. Repeat for each side: drive 20 cm, turn.
# 4. Say how many sides were drawn.

Challenges

1. Write an algorithm in plain English for making a cup of tea, precise enough for a robot. Swap with a partner and find the ambiguous steps.
2. Write the inputs, processes and outputs for a program that tells you whether a number is even.
3. Write an algorithm, then a program, that finds out whether a number is prime by trying divisors only up to its square root.