Programming Algorithms
Senior 4 · ICT
Programming Algorithms
Lesson 1 of 5
22 min
A teacher has 168 exercise books and 120 pens to share into identical prize packs, with nothing left over. What is the largest number of packs she can make? One student tries numbers at random: 10 packs? 12? 20? Another lists every divisor of both numbers. A third uses a method that is more than 2 300 years old, from Euclid's Elements, and has the answer, 24 packs, in three short steps. The third student did not guess. She followed an algorithm: a method that is guaranteed to work, every time, for any two numbers.
Computers can only follow algorithms. Before anyone writes a program, someone has to find the steps. This unit is about finding and writing those steps; the next unit turns them into Python.
Definition
Algorithm: a finite sequence of precise, unambiguous instructions that solves a problem or completes a task, starting from given inputs and producing an output.
Program: an algorithm written in a programming language so that a computer can carry it out.
Trace (dry run): working through an algorithm by hand, step by step, writing down the value of every quantity, to check that it gives the right output.
The computer scientist Donald Knuth listed five properties that every algorithm must have.
| Property | Meaning | Fails if… |
|---|---|---|
| Finiteness | It always stops after a finite number of steps. | "Keep adding 1 to the number" never ends. |
| Definiteness | Each step is precise and has only one meaning. | "Add a little water" (how much?) |
| Input | It takes zero or more values to work on. | It needs a value it never asks for. |
| Output | It produces at least one result. | It works something out but never gives it. |
| Effectiveness | Every step can actually be done, exactly, in finite time. | "Write down every digit of π." |
Algorithms can be written in several ways: in natural language (numbered steps in English or Kinyarwanda), in pseudocode (structured English close to code), as a flowchart (a diagram), or as a program. Lessons 2 to 5 use pseudocode and flowcharts.
Step 3 is the one beginners skip. Tracing an algorithm on paper with real numbers finds most mistakes before a single line of code exists, when they are cheapest to fix.
Worked example 1: Euclid's algorithm for the highest common factor
Input: two whole numbers . Output: their highest common factor (HCF).
Trace with , :
| Pass | a | b | r (remainder of a ÷ b) | Action |
|---|---|---|---|---|
| 1 | 168 | 120 | 48 (since ) | r ≠ 0: a ← 120, b ← 48 |
| 2 | 120 | 48 | 24 (since ) | r ≠ 0: a ← 48, b ← 24 |
| 3 | 48 | 24 | 0 (since ) | r = 0: output 24 |
So 24 packs, each with books and pens. All five properties hold: it stops (the remainder gets smaller every pass and cannot go below 0), every step is exact, it takes two inputs, gives one output, and each step is a simple division.
Worked example 2: make a vague method precise
A student writes: "To find the biggest mark, look through the marks and pick the biggest." For 40 marks a person can do this, but it is not definite: how do you look? A precise version:
Trace with the marks 56, 71, 64, 88, 49: biggest becomes 56, then 71, stays 71, becomes 88, stays 88. Output 88. The same steps work for 5 marks or 5 000.
Euclid's algorithm written in pseudocode, the form used in the rest of this unit. MOD gives the remainder, ← means "becomes", and the indented lines inside WHILE … ENDWHILE repeat as long as \( r \ne 0 \). You will learn each of these in lessons 2 to 5.
Press Run: it prints Highest common factor: 24. Change the two numbers on the first lines, for example to 1071 and 462, and run it again. The algorithm does not change; only the inputs do.
TED-Ed, David J. Malan: What's an algorithm? Watch the example of counting the people in a room, and notice how a better algorithm solves the same problem in far fewer steps.
Warning
An algorithm must stop. A list of steps that can go round for ever (for example, "keep halving the number until it reaches 0", which never happens for a positive number) is not an algorithm. Always ask: what makes it finish?
"Obvious" steps are not precise. A person fills gaps with common sense; a computer cannot. Write every step as if for someone who will do exactly what you say and nothing more.
Tip
Trace with small, awkward numbers. Test an algorithm with ordinary inputs, with the smallest allowed inputs, and with a case that might break it (equal numbers, a zero, a negative). Most mistakes show up in the awkward cases.
Practice
Key points
Sources and credits
This lesson adapts CC BY-SA material and is shared under CC BY-SA 4.0.
BEGIN
INPUT a, b
r ← a MOD b
WHILE r ≠ 0 DO
a ← b
b ← r
r ← a MOD b
ENDWHILE
OUTPUT b
END# Euclid's algorithm in Python: the same steps as the pseudocode.
a = 168
b = 120
r = a % b
while r != 0:
a = b
b = r
r = a % b
print("Highest common factor:", b)Quick check
"Keep adding 2 to the number" is not an algorithm. Which property does it fail?