Every program starts as a list of steps
An algorithm is a list of steps that solves a problem, and every program starts as one. If you can write the steps in plain words and follow them by hand, you can write the program.
Take a teacher who wants the average of three test marks. She does not need a computer to see the steps: add the marks, then divide by three.
By the end of this lesson
Note
I can break a problem into steps and trace what a program does.
Key words
| Word | What it means | Example |
|---|---|---|
| Algorithm | a list of steps, in order, that solves a problem | |
| Decomposition | splitting a big problem into small ones | |
| Pseudocode | steps written in plain words that look a little like code | |
| Variable | a name that holds a value | total |
| Program | steps written in a language a computer can follow | |
| Trace table | a table that records each variable after each step |
The cells students fill in are left blank in this preview.
An algorithm is steps in a fixed order
An algorithm has three features. Each step is clear enough that anyone can follow it. The steps come in a fixed order. And the list ends with an answer.
"Make it better" is not a step. "Add 1 to the total" is a step. A computer cannot guess what you mean, so every step must be exact.
Worked example: an algorithm for an average
| Step | What you do | With the marks 7, 5 and 9 |
|---|---|---|
| 1 | Start the total at 0 | total is 0 |
| 2 | Add the first mark | total is 7 |
| 3 | Add the second mark | total is 12 |
| 4 | Add the third mark | total is 21 |
| 5 | Divide by the number of marks | 21 divided by 3 is 7 |
The cells students fill in are left blank in this preview.
Check the answer with Python
python3 -c "print((7 + 5 + 9) / 3)"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Decomposition splits a big problem into small ones
Most real problems are too big to solve in one go. Decomposition means cutting a problem into smaller parts, and then solving each part alone.
A results report is one example. The parts are: read the marks, add them up, count them, divide, and show the answer. Each part is easy.
Pseudocode is a plan written in plain words
Pseudocode is a plan between a sentence and a program. It uses short, exact lines, but it does not follow the rules of any language, so no computer can run it.
Writing pseudocode first lets you check the steps before you worry about spelling and symbols.
The average as pseudocode and as Python
| Pseudocode | Python |
|---|---|
| set total to 0 | total = 0 |
| add 7 to total | total = total + 7 |
| add 5 to total | total = total + 5 |
| show total divided by 3 | print(total / 3) |
The cells students fill in are left blank in this preview.
A trace table follows each line
A trace table is how you work out what a program does without running it. Draw a column for each variable. Then go down the program one line at a time and write the new value after every line.
Finding a bug is the most useful job for a trace table. The row where the value goes wrong shows you the faulty line.
Worked example: trace the program
| After this line | mark | total |
|---|---|---|
| total = 0 | no value yet | 0 |
| mark = 7 | 7 | 0 |
| total = total + mark | 7 | 7 |
| mark = 5 | 5 | 7 |
| total = total + mark | 5 | 12 |
| mark = 9, then total = total + mark | 9 | 21 |
The cells students fill in are left blank in this preview.
The same trace, printed by Python
# Three marks, added one at a time. Read it like a trace table.
total = 0
mark = 7
total = total + mark
print("after 7:", total)
mark = 5
total = total + mark
print("after 5:", total)
mark = 9
total = total + mark
print("after 9:", total)
print("average:", total / 3)
# Change the last mark from 9 to 12, then run it again.
A common mistake
Warning
Many people fill in a trace table from what the program is meant to do. A trace follows the lines exactly, even when the program is wrong. Read one line, write one row, and ignore what you hope will happen.
Going further
On paper, write an algorithm for finding the largest of three numbers. Use pseudocode, and keep each line to one action.
Then trace it with the numbers 4, 9 and 6. Draw a column for each variable and write a row after every line. Say what the answer should be before you start.