Representing Algorithms
AQA pseudo-code written the way AQA writes it, the six flowchart symbols and what each one is for, and a method for trace tables that does not fall apart under time pressure.
AQA pseudo-code
Pseudo-code is a way of writing an algorithm that has the structure of a program without the fussy punctuation of a real language. AQA publishes its own version and every algorithm printed in an exam paper uses it, so being able to read it fluently is worth marks on every paper.
The single most important thing to notice is the assignment arrow. AQA never uses = for assignment. It uses a left arrow, so = only ever means "is equal to".
score ← 0
score ← score + 10
name ← USERINPUT
OUTPUT 'Hello ' + nameSelection
IF mark > 79 THEN
grade ← 9
ELSE IF mark > 69 THEN
grade ← 8
ELSE
grade ← 7
ENDIFNote ELSE IF as two words, and ENDIF as one. Every AQA block structure closes with an END keyword: ENDIF, ENDWHILE, ENDFOR, ENDSUBROUTINE. The one exception is REPEAT, which is closed by UNTIL.
Iteration
# definite iteration: you know how many times before you start
FOR i ← 1 TO 10
OUTPUT i
ENDFOR
# indefinite iteration: condition tested before the body runs
WHILE guess ≠ answer
guess ← USERINPUT
ENDWHILE
# indefinite iteration: condition tested after the body runs
REPEAT
guess ← USERINPUT
UNTIL guess = answerThe difference between the last two is examined constantly. A WHILE loop may run zero times, because the condition is checked first. A REPEAT loop always runs at least once, because the condition is checked at the end.
Arrays, subroutines and strings
scores ← [4, 8, 15, 16, 23, 42]
OUTPUT scores[0]
OUTPUT LEN(scores)
SUBROUTINE average(values)
total ← 0
FOR i ← 0 TO LEN(values) - 1
total ← total + values[i]
ENDFOR
RETURN total / LEN(values)
ENDSUBROUTINE
mean ← average(scores)AQA arrays and strings are indexed from 0. Three string routines appear repeatedly:
| Routine | What it does | Example | Result |
|---|---|---|---|
LEN(s) | Number of characters, including spaces | LEN('computer') | 8 |
POSITION(s, c) | Index of the first occurrence of a character | POSITION('computer', 'm') | 2 |
SUBSTRING(a, b, s) | Characters from index a to index b inclusive | SUBSTRING(2, 4, 'computer') | 'mpu' |
This is the trap AQA sets most often. SUBSTRING(2, 4, 'computer') returns three characters, indexes 2, 3 and 4, because both ends are included. If you read the second number as a length you get the wrong answer every time.
DIV is integer division, so 17 DIV 5 is 3. MOD gives the remainder, so 17 MOD 5 is 2. Ordinary / gives the real answer 3.4.
Flowcharts
A flowchart shows the same algorithm as a diagram. AQA can ask you to complete one, to read one, or to convert between a flowchart and pseudo-code, so you need the symbols exactly.
| Symbol | Shape | Used for |
|---|---|---|
| Terminal | Rounded rectangle | Start and Stop, one of each |
| Process | Rectangle | A calculation or an assignment, such as total ← total + 1 |
| Input or output | Parallelogram | Reading a value from the user or displaying one |
| Decision | Diamond | A question with exactly two labelled exits, Yes and No |
| Subroutine | Rectangle with two extra vertical lines | A call to a named subroutine defined elsewhere |
| Flow line | Arrow | The order the steps are carried out in |
Reading one properly
Loops in a flowchart are drawn as an arrow going backwards from somewhere below a decision to somewhere above it. That is the only way a loop can appear, so if you see a backward arrow you are looking at iteration, and the decision it returns to is the loop condition.
The decision diamond is where marks are lost. Every diamond must contain a question that can only be answered Yes or No, and both exits must be labelled. A diamond containing total is wrong. A diamond containing total > 100 is right.
Work out first whether the decision is a loop or an IF. If an arrow comes back to it from below, it is a loop, so write WHILE or REPEAT. If both exits carry on downwards and meet again lower down, it is an IF.
A flowchart with two Stop terminals is usually a sign that you have drawn an IF where the two branches never rejoin. It is not automatically wrong, but check the logic before you leave it.
- Each shape has one meaning: terminals start and stop, parallelograms are input or output, rectangles are processes, diamonds are decisions.
- Flow lines show the order, and every chart starts and stops with a terminal.
- A decision has two exits, labelled Yes and No, and the two routes join up again.
- The flowchart: ovals for start and end, slanted boxes for input and output, a diamond for a decision with a yes branch and a no branch.
- The Python version has the same steps, matched by colour.
- The pseudocode is the same algorithm again. Only the notation changes.
Trace tables
A trace table records the value of every variable after every step of an algorithm. AQA uses them to test whether you can execute code in your head, and there are marks available for a table that has been filled in mechanically and correctly even if you have no idea what the algorithm is for.
The method that works under pressure has four rules.
- Draw one column per variable, plus a column for any output. Get the columns from the code, not from the question.
- Write a new row every time any variable changes. Do not overwrite. The examiner is marking the history, not the final state.
- Leave a cell blank if that variable did not change on that line. Repeating the old value is not wrong, but blanks make errors much easier to spot.
- Evaluate the condition out loud before you follow a branch. Most trace table errors are loop control errors, not arithmetic errors.
Worked example
a ← 12
b ← 8
WHILE b ≠ 0
temp ← b
b ← a MOD b
a ← temp
ENDWHILE
OUTPUT a| a | b | temp | Output |
|---|---|---|---|
| 12 | 8 | ||
| 4 | 8 | ||
| 8 | |||
| 0 | 4 | ||
| 4 | |||
| 4 |
Reading the table back: 12 MOD 8 is 4, so b becomes 4 and a becomes 8. Then 8 MOD 4 is 0, so b becomes 0 and a becomes 4. The condition b ≠ 0 is now false, the loop ends and 4 is output. The algorithm finds the highest common factor of 12 and 8, which is indeed 4, but you did not need to know that to fill the table in correctly.
Never try to guess the purpose of an algorithm before tracing it. Trace it mechanically, then look at the output column and ask what that output is. That is how the "state the purpose of this algorithm" mark is earned.
The commonest single error is running the loop one extra time. Before you write a new row, check the condition against the values in the row above, not the values you are about to write.
Trace table trainer
Fill in a trace table row by row and have it marked as you type. This tool needs JavaScript, so turn it on to use it. Everything you need to answer the exam question is explained in the text above.
- Run the program by hand, one line at a time. Line 3 is the one that repeats.
- Follow four rules: one line at a time, one column per variable, a new row for each change, and check the last row.
- Each time the loop runs, i goes up by one and total grows: 0, 1, 3, 6.
- The output is written when print runs. Here it is 6.
Key terms you must be able to define
- Pseudo-code
- A way of writing an algorithm that has the structure of program code but is not tied to any one programming language.
- Assignment
- Storing a value in a variable, written in AQA pseudo-code with a left arrow.
- Flowchart
- A diagram that represents an algorithm using standard symbols joined by flow lines.
- Decision
- A flowchart symbol, drawn as a diamond, containing a question with exactly two exits labelled Yes and No.
- Trace table
- A table that records the value of every variable after each step of an algorithm so that its behaviour can be checked by hand.
- Definite iteration
- A loop that repeats a known number of times, written in AQA pseudo-code with FOR and ENDFOR.
- Indefinite iteration
- A loop that repeats until a condition is met, written with WHILE or REPEAT.
- DIV
- The integer division operator, which gives the whole number of times one value divides into another.
- MOD
- The modulus operator, which gives the remainder after integer division.
- SUBSTRING
- An AQA string routine that returns the characters between two given index positions inclusive.
Flashcards
Say the definition out loud before you flip the card. Retrieving it from memory is what builds recall, reading it again is not.
Reach the top grade on this topic
Two things separate top answers here, and both are habits rather than knowledge.
Read AQA pseudo-code as AQA wrote it. The arrow means assignment, = means comparison, indexes start at 0 and SUBSTRING takes a finishing index rather than a length. Candidates who quietly translate the code into Python in their heads lose marks on exactly these four points, because Python does the opposite on two of them.
Trace mechanically, interpret afterwards. Strong candidates fill in the whole table without thinking about meaning, then read the output column and describe what the algorithm does. Weak candidates decide what the algorithm probably does, then fill the table in to match, and get both parts wrong together.
Say what changed and when. In a "describe what this algorithm does" question, the marks are for the effect, not for a line by line commentary. "It counts how many values in the array are greater than the average" is worth more than six lines of "then it adds one to i".
- Read and write all four AQA loop and selection structures without checking
- State the difference between WHILE and REPEAT in one sentence, including the zero times point
- Work out LEN, POSITION and SUBSTRING results for a given string with no hesitation
- Complete a trace table for a nested loop without losing track of the inner counter
Mistakes that cost marks here
- Using = for assignment in AQA pseudo-code. AQA uses a left arrow, and = only ever means equal to.
- Reading the second argument of SUBSTRING as a length. It is the index of the last character, and it is included.
- Starting array or string indexing at 1. AQA indexes from 0.
- Filling in only the final value of each variable in a trace table instead of a row per change, which throws away most of the marks.
- Putting a variable name rather than a condition inside a decision diamond, so the two exits cannot be labelled Yes and No.
- Saying a WHILE loop always runs at least once. That is REPEAT. A WHILE loop can run zero times.
AQA publishes its own pseudo-code guide and uses it in every exam paper, so the pseudo-code you read in a question is guaranteed to follow it. You are not required to answer in AQA pseudo-code, but you are required to be able to read it.
Knowledge check
SUBSTRING(1, 3, 'binary')?POSITION('computer', 'm')?17 DIV 5?17 MOD 5?Exam-style questions
Five written questions in the style of the real paper. Write a full answer, then let the marker check it against the mark scheme.
- LA WHILE loop tests its condition before the body runs, so it may run zero times
- LA REPEAT loop tests its condition after the body runs, so it always runs at least once
A WHILE loop tests its condition before the body is executed, so if the condition is false at the start the body never runs at all. A REPEAT UNTIL loop tests its condition after the body has been executed, so the body always runs at least once whatever the condition.
- LA trace table records the value of each variable at each step of the algorithm
- LThe algorithm is executed by hand rather than run on a computer
- LThe recorded values are compared with the values that were expected
- LThe first row where the value differs identifies the line containing the error
A trace table is a table with one column for each variable, and one for any output, in which the value of every variable is written down after each step of the algorithm. The algorithm is executed by hand rather than run on a computer, so the programmer can see exactly what happens inside it. Each recorded value is then compared with what was expected at that point, and the first row in which the actual value differs from the expected value shows precisely where the algorithm first goes wrong. That narrows a fault down to a single line, which is far quicker than reading the whole algorithm and guessing.
- LThe diamond represents a decision
- LIt contains a condition that evaluates to either true or false
- LExactly two paths leave it and both must be labelled
The diamond is the decision symbol and it contains a condition that can only evaluate to true or false, such as whether a total is greater than one hundred. Exactly two flow lines leave the symbol, one followed when the condition is true and one when it is false, and both must be clearly labelled Yes and No so that the reader can tell which path is which. If a backward flow line returns to the diamond from below then the decision is controlling a loop rather than a simple selection.
- LPseudo-code is not tied to one programming language
- LSo the same design can be implemented in Python, C# or VB.NET
- LThe logic can be checked before any code is written
- LWhich saves time because errors in the method are corrected on paper rather than debugged in code
The first advantage is that pseudo-code is not tied to any one programming language, so the designer does not have to worry about the exact syntax of Python or C# while working out the method. The same pseudo-code can then be handed to any programmer and implemented in whichever language the project uses. The second advantage is that the logic of the solution can be checked, for example with a trace table, before a single line of real code exists. A mistake in the method costs a couple of minutes to fix while it is still pseudo-code, but once it has been built into working code it has to be found by debugging, which takes far longer.
- LThe output is 120
- LThe algorithm repeatedly multiplies the running total by n while decreasing n
- LIt calculates the factorial of the starting value of n
The loop multiplies total by 5, then by 4, then by 3, then by 2, stopping when n reaches 1, so total becomes 120. The algorithm therefore calculates the factorial of the starting value of n, that is the product of every whole number from n down to 1. Tracing it row by row confirms this: total takes the values 5, 20, 60 and 120 as n falls from 5 to 1.