What an algorithm is

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

F5.1AlgorithmsGCSE12 min

Covers OCR J277 2.1.2 Designing, creating and refining algorithms · AQA 8525 3.1.1 Representing algorithms · Edexcel 1CP2 1.2.1 Following and writing algorithms

Do this lesson in the simulator

Print it: worksheet (PDF) · answers (PDF) · as a web page

Guide: Big O notation explained

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 shape algorithm followed for 3, 4 and 6 sides: the turn at each corner is 360 divided by the sides, and the turns always add up to 360 degreesstart120°3 sidesturn 360 ÷ 3 = 120°3 turns of 120° = 360°90°4 sidesturn 360 ÷ 4 = 90°4 turns of 90° = 360°60°6 sidesturn 360 ÷ 6 = 60°6 turns of 60° = 360°
One algorithm, three answers. Every side is 20 cm, and only the turn changes: 360 divided by the number of sides. The green arc is the turn at the first corner, away from the dashed way the robot was going. However many sides, the turns add up to one full turn, 360 degrees, which is why the shape closes.

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:

Inputs Processes Outputs
the number of sides work out the angle; repeat the drive and turn the shape driven; the message

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 of 9 or less, which you would already have tried. Both are correct; the second does 8 divisions instead of 95, less than a tenth of the work. Much of this module is about comparing algorithms like that.

Testing 97 for a factor: 95 divisions from 2 to 96, or only the 8 from 2 to 9, each leaving a remainderevery number from 2 to 96: 95 divisions2996only up to 9: 8 divisions÷ 2rem 1÷ 3rem 1÷ 4rem 1÷ 5rem 2÷ 6rem 1÷ 7rem 6÷ 8rem 1÷ 9rem 7No remainder is 0, so nothing from 2 to 9 divides 97.Stop at 9: 9 × 9 = 81, but 10 × 10 = 100, more than 97.
Both ways give the same answer, prime, but the green 8 are all the work the second way does. If 97 had a factor of 10 or more, its partner would be less than 10, and that partner has already been tried.

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.

Past paper questions on this

Real exam questions that test this, each worked through with a program you can run.