Designing, Creating and Refining Algorithms

Flowcharts

A flowchart is a diagram showing an algorithm as a series of connected symbols.

Reading a flowchart

The rule is simple: follow the arrows. At a diamond there are always exactly two ways out, one for yes and one for no, and they must be labelled.

A loop appears as an arrow that goes back to an earlier point in the diagram.

Pseudocode and the OCR reference language

Pseudocode describes an algorithm in structured English, without the strict syntax of a real language. OCR provides its own reference language, and you should use it in written answers because the mark schemes are written around it.

The core constructs

// Variables and assignment
name = "Sam"
score = 0
global highScore = 0

// Input and output
name = input("What is your name?")
print("Hello " + name)

// Selection
if score > 50 then
    print("Pass")
elseif score = 50 then
    print("Borderline")
else
    print("Fail")
endif

// Case selection
switch grade:
    case "A":
        print("Excellent")
    case "B":
        print("Good")
    default:
        print("See teacher")
endswitch

// Count controlled loop
for i = 0 to 9
    print(i)
next i

// Condition controlled loops
while answer != "quit"
    answer = input("Enter a command")
endwhile

do
    guess = input("Guess the number")
until guess == 7

Subroutines

function addTax(amount)
    return amount * 1.2
endfunction

procedure greet(name)
    print("Hello " + name)
endprocedure

total = addTax(100)
greet("Sam")

A function returns a value. A procedure does not. This distinction is examined regularly.

Arrays and strings

array scores[5]
scores[0] = 42
print(scores[0])

array board[3,3]        // 2D array
board[1,2] = "X"

name = "Computer"
print(name.length)              // 8
print(name.substring(0,4))      // Comp
print(name.upper)               // COMPUTER

File handling

myFile = open("scores.txt")
line = myFile.readLine()
myFile.writeLine("New score")
myFile.close()

Trace tables

A trace table records the value of every variable after each step of an algorithm. It is how you work out what an algorithm actually does, rather than what you assume it does.

How to complete one

1. Draw a column for every variable and one for any output.
2. Work through the algorithm one line at a time.
3. Write a new row every time a value changes.
4. Do not skip iterations of a loop. Errors hide in the second and third pass.

Worked example

total = 0
for i = 1 to 4
    total = total + i
    if total > 5 then
        print(total)
    endif
next i

Finding and correcting errors

Paper 2 regularly gives you an algorithm containing deliberate errors and asks you to find and fix them. Work through this checklist.

The checklist

1. Off by one in loops. for i = 1 to 10 runs ten times starting at 1. for i = 0 to 10 runs eleven times. Check against what the question requires.
2. Array index out of range. An array of size n has indexes 0 to n-1.
3. Assignment against comparison. = assigns in most pseudocode, == compares. In OCR reference language both are used, so read carefully.
4. Wrong comparison operator. > instead of >= changes behaviour exactly at the boundary, which is where exam questions target.
5. Variable used before it is initialised, for example adding to a total that was never set to 0.
6. Infinite loop, where the condition can never become false because the variable inside the loop is never changed.
7. Wrong data type, for example comparing the string "5" with the integer 5.
8. Logic in the wrong order, such as printing the average before calculating it.

Refining an algorithm

Making an algorithm more efficient or more robust:

• Replace repeated code with a loop or a subroutine
• Stop searching as soon as the item is found rather than checking the whole list
• Validate input before it is used, rather than letting the program crash
• Remove calculations from inside a loop when the value never changes
• Use a more efficient algorithm, for example binary search instead of linear search on sorted data

Key terms you must be able to define

Algorithm

A sequence of unambiguous, ordered steps that solves a problem or completes a task.

Pseudocode

A structured description of an algorithm in English-like statements, independent of any programming language.

Flowchart

A diagram representing an algorithm using standard symbols connected by arrows.

Trace table

A table recording the value of each variable after every step of an algorithm.

Function

A subroutine that returns a value to the code that called it.

Procedure

A subroutine that carries out a task but does not return a value.

Efficiency

How well an algorithm uses resources, usually measured in the number of steps or the memory required.

Off by one error

A mistake where a loop runs one time too many or too few, or an array index is one out.

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

Paper 2 is dominated by this topic, and the difference between grades is almost entirely discipline.

Fill in the whole trace table. Every row, every iteration. Method marks are real marks.

Use OCR reference language, not Python, in written answers. Both are accepted, but the mark schemes are written in reference language, so matching it removes any chance of ambiguity. Whichever you choose, be consistent within one answer.

When correcting an error, say three things: where it is, what is wrong, and what it should be. "Line 4 uses > but should use >=, because a score of exactly 50 should count as a pass."

Check boundaries automatically. If a condition involves a number, ask what happens when the value is exactly that number. That is where the examiner has put the error.

• Complete a trace table for a nested loop without losing track
• Convert a flowchart into pseudocode and back
• Write a function and a procedure correctly and explain the difference
• Find three deliberate errors in a twelve line algorithm in under five minutes

Mistakes that cost marks here