Algorithms & Pseudocode

Before you write a single line of pseudocode, Paper 2 expects you to be able to talk about how you got there. That is what section 9 of the syllabus is really testing: not "can you code", but "can you take a messy real-world problem and turn it into a precise, ordered set of steps".

Abstraction

Abstraction is the process of removing detail that is not relevant to the problem you are solving, so you are left with a simplified model that only contains what matters. A school attendance system does not need to model the colour of a student's bag or what they had for breakfast, it only needs a student ID, a name, and whether they were present. Abstraction exists because real-world problems are full of irrelevant detail, and trying to model all of it makes a solution slower to design, harder to code, and harder to get right. A good abstraction keeps the essential data and behaviour and discards the rest.

Decomposition

Decomposition is breaking a large problem down into smaller sub-problems that are easier to solve individually. Each sub-problem typically becomes a module in the final program, in pseudocode terms a procedure or a function (see section 10). A "library loan system", for example, decomposes naturally into smaller jobs: check whether a student is allowed to borrow, register a new loan, process a return, and count a student's current loans. Section 11 of this page builds exactly that system, one sub-problem at a time.

What is an algorithm?

An algorithm is a solution to a problem expressed as a sequence of precisely defined steps that, if followed exactly, always produce the correct result. Every algorithm can be built from just three basic constructs, combined and nested in any order:

Identifier names and identifier tables

Every variable in an algorithm needs a name (an identifier) that is meaningful and describes what it stores, StudentCount rather than x. Before writing pseudocode for a non-trivial problem, it is good practice, and sometimes explicitly asked for in an exam question, to document the identifiers you plan to use in an identifier table: the name, its data type, and what it represents.

Documenting an algorithm: structured English, flowcharts, pseudocode

The same algorithm can be documented in three different ways, and Paper 2 can ask you to convert between any of them:

• Structured English: a numbered, indented list of steps written in plain but precise language, close to pseudocode but without strict syntax.
• Flowchart: a diagram using standard symbols (rounded start/end, rectangle for a process, diamond for a decision, parallelogram for input/output), connected by arrows showing the flow of control.
• Pseudocode: the formal, syntax-precise language this whole page is written in, close enough to real code that it can be translated directly into any programming language.

Cambridge pseudocode has a fixed, small set of rules. Learn them once here and every worked example on this page will already make sense.

The six basic data types

CHAR values are written in single quotes, STRING values in double quotes, this distinction is easy to lose marks on.

Rules for naming variables

• A variable name must start with a letter.
• It cannot contain spaces, CountryName not Country Name.
• It cannot contain special characters (only letters and digits after the first letter).
• Variable names are case-sensitive: Name and name are two different identifiers, this is a common source of "undeclared variable" style errors in student pseudocode.

Declaring, initialising and assigning

A variable should be declared with its type before use, and a fixed value that never changes is declared as a constant:

CONSTANT MaxAttempts <- 3
DECLARE Name : STRING
DECLARE Age : INTEGER
Name <- "Ali"
Age <- 17

The assignment operator is <-, it means "the value on the right is stored in the variable on the left". It is not the same as the comparison operator =, which is only used inside a condition. Writing IF Flag <- TRUE THEN instead of IF Flag = TRUE THEN is one of the most common syntax slips on Paper 2, see the "spot the error" exercises in section 14.

Operators

Input and output

OUTPUT "Enter a number"
INPUT num
OUTPUT num * 2

OUTPUT displays a value or message, INPUT reads a value from the keyboard into a variable that must already be declared.

Selection is a choice between different paths of execution, based on whether a condition is TRUE or FALSE.

IF, ELSE and nested IF

IF Scores[index] > 100 THEN
    count <- count + 1
    OUTPUT CricketTeams[index]
ENDIF

An IF on its own only runs its block when the condition is TRUE, execution otherwise skips straight past ENDIF. Add an ELSE to give a second path for when the condition is FALSE:

IF count > 0 THEN
    OUTPUT "The number of teams that scored over 100 is ", count
ELSE
    OUTPUT "No team scored over 100"
ENDIF

IF statements can be nested, an IF placed inside the THEN or ELSE branch of another IF, to test a second condition only once the first has already been satisfied. This is exactly how a "running highest and lowest" tracker works:

IF temp > 0 THEN
    IF temp > highest THEN
        highest <- temp
    ENDIF
    IF temp < lowest THEN
        lowest <- temp
    ENDIF
    count <- count + 1
    sum <- sum + temp
ENDIF

Note the outer IF here is a validation guard, a common exam pattern where the outer condition filters out data (only positive, real readings) before any of the inner logic runs at all.

CASE

When one variable is being compared against several possible values, a chain of nested IFs becomes hard to read. A CASE statement expresses this more clearly:

OUTPUT "Enter mark"
INPUT mark
CASE OF mark DIV 10
    9, 8, 7 : OUTPUT "Grade A"
    6       : OUTPUT "Grade B"
    5       : OUTPUT "Grade C"
    4       : OUTPUT "Grade D"
    OTHERWISE : OUTPUT "Grade U"
ENDCASE

Iteration repeats a block of steps. Cambridge pseudocode gives you three loop constructs, and choosing the right one for a given problem is a skill the exam tests directly.

Compound conditions and input validation

A REPEAT UNTIL or WHILE condition is often a compound Boolean expression using AND/OR, most commonly to validate a range of user input. Both loops below do the same job, keep asking until the number is between 1 and 100 inclusive, they simply check the opposite condition at the opposite point in the loop:

REPEAT
    OUTPUT "Enter a number between 1 and 100"
    INPUT num
UNTIL num >= 1 AND num <= 100

OUTPUT "Enter a number between 1 and 100"
INPUT num
WHILE num < 1 OR num > 100
    OUTPUT "Enter a number between 1 and 100"
    INPUT num
ENDWHILE

Notice the condition flips: REPEAT UNTIL exits when the input is valid (num>=1 AND num<=100), WHILE keeps looping while it is invalid (num<1 OR num>100), the two are logical opposites of each other (De Morgan's law). The WHILE version also needs one input statement written before the loop starts, since the condition has to be checked before the first pass has any data to check.

Worked example: sentinel-controlled loop

highest <- -9999
lowest <- 9999
count <- 0
sum <- 0
REPEAT
    OUTPUT "Enter temperature in Celsius"
    INPUT temp
    IF temp > 0 THEN
        IF temp > highest THEN
            highest <- temp
        ENDIF
        IF temp < lowest THEN
            lowest <- temp
        ENDIF
        count <- count + 1
        sum <- sum + temp
    ENDIF
UNTIL temp < 0
OUTPUT "The average temperature is ", sum / count
OUTPUT "The highest temperature is ", highest
OUTPUT "The lowest temperature is ", lowest
OUTPUT "The number of readings taken is ", count

An array is a data structure that stores a fixed number of values of the same data type under one identifier, each accessed by a numeric position.

Terminology

• Index: the position used to access a specific element, StdMarks[7] accesses the element at index 7.
• Lower bound: the smallest valid index (in Cambridge pseudocode, arrays are usually declared starting at index 1).
• Upper bound: the largest valid index.

DECLARE StdMarks : ARRAY[1:50] OF INTEGER

Here the lower bound is 1 and the upper bound is 50, so StdMarks holds exactly 50 integers, accessed as StdMarks[1] through StdMarks[50].

1D arrays: initialise, input, output

DECLARE StdMarks : ARRAY[1:50] OF INTEGER

// Initialise every element to 0
FOR index <- 1 TO 50
    StdMarks[index] <- 0
NEXT index

// Take input from the user and store it in the array
FOR index <- 1 TO 50
    OUTPUT "Enter student mark"
    INPUT StdMarks[index]
NEXT index

// Output the array
FOR index <- 1 TO 50
    OUTPUT StdMarks[index]
NEXT index

Initialising, filling, and reading an array is almost always done with a count-controlled FOR loop, the array's fixed size makes the number of iterations known in advance, exactly the case FOR is built for.

DECLARE StudentNames : ARRAY[1:100] OF STRING

FOR index <- 1 TO 100
    OUTPUT "Enter name of student"
    INPUT StudentNames[index]
NEXT index

FOR index <- 1 TO 100
    OUTPUT StudentNames[index]
NEXT index

2D arrays

A 2D array stores data indexed by two dimensions, typically thought of as rows and columns, useful anywhere data is naturally a grid: a seating plan, a set of test scores across several students and several tests, or a game board.

DECLARE TestScores : ARRAY[1:5, 1:3] OF INTEGER

This declares a grid with 5 rows and 3 columns, 15 elements in total, one INTEGER per student per test. TestScores[2,3] accesses row 2, column 3: student 2's mark on test 3. Filling or reading a 2D array needs nested FOR loops, one for each dimension:

DECLARE TestScores : ARRAY[1:5, 1:3] OF INTEGER
DECLARE student, test, total : INTEGER

// Input: outer loop = student (row), inner loop = test (column)
FOR student <- 1 TO 5
    FOR test <- 1 TO 3
        OUTPUT "Enter mark for student ", student, " test ", test
        INPUT TestScores[student, test]
    NEXT test
NEXT student

// Output each student's total across all three tests
FOR student <- 1 TO 5
    total <- 0
    FOR test <- 1 TO 3
        total <- total + TestScores[student, test]
    NEXT test
    OUTPUT "Student ", student, " total: ", total
NEXT student

The syllabus explicitly requires two array algorithms: searching with a linear search, and sorting with a bubble sort. Both are built here around one running example.

Setting up: parallel arrays

DECLARE Scores : ARRAY[1:12] OF INTEGER
DECLARE CricketTeams : ARRAY[1:12] OF STRING
DECLARE sum, count, index : INTEGER

sum <- 0
count <- 0
FOR index <- 1 TO 12
    OUTPUT "Enter name of team ", index
    INPUT CricketTeams[index]
    OUTPUT "Enter score for ", CricketTeams[index]
    INPUT Scores[index]
    sum <- sum + Scores[index]
    IF Scores[index] > 100 THEN
        count <- count + 1
        OUTPUT CricketTeams[index]
    ENDIF
NEXT index

OUTPUT "Total score: ", sum
OUTPUT "Average score: ", sum / 12

Scores and CricketTeams are parallel arrays, index 5 in one always describes the same team as index 5 in the other. This only works if every operation that moves data in one array (like sorting, below) moves the corresponding element in the other array too.

Linear search

A linear search checks each element in turn, from the first to the last, until it finds a match or runs out of elements. It works on an array in any order, but in the worst case has to check every single element.

OUTPUT "Enter the name of the team to find"
INPUT nameToFind
index <- 1
Found <- FALSE
REPEAT
    IF CricketTeams[index] = nameToFind THEN
        Found <- TRUE
    ELSE
        index <- index + 1
    ENDIF
UNTIL Found = TRUE OR index > 12

IF Found = TRUE THEN
    OUTPUT "Found at position ", index
ELSE
    OUTPUT "Team not found"
ENDIF

Bubble sort

A bubble sort repeatedly steps through the array, comparing each pair of neighbouring elements and swapping them if they are in the wrong order. Each full pass "bubbles" the largest remaining unsorted value up to its correct position, so the algorithm needs at most n-1 passes for n elements. A pass with no swaps means the array is already sorted, so the loop can stop early.

DECLARE pass, temp, temp2 : INTEGER
DECLARE swap : BOOLEAN

pass <- 1
REPEAT
    swap <- FALSE
    FOR index <- 1 TO 12 - pass
        IF Scores[index] > Scores[index + 1] THEN
            swap <- TRUE
            temp <- Scores[index]
            Scores[index] <- Scores[index + 1]
            Scores[index + 1] <- temp

            temp2 <- CricketTeams[index]
            CricketTeams[index] <- CricketTeams[index + 1]
            CricketTeams[index + 1] <- temp2
        ENDIF
    NEXT index
    pass <- pass + 1
UNTIL swap = FALSE OR pass > 12

median <- (Scores[6] + Scores[7]) / 2
OUTPUT "Median score: ", median

The inner FOR only needs to go up to 12 - pass: after each pass, one more element at the end of the array is guaranteed sorted and can be skipped. Swapping Scores[index] and Scores[index+1] is always followed by the matching swap in CricketTeams, this is what keeps the two parallel arrays lined up.

An array is powerful, but it can only hold one data type. Real data rarely looks like that, a single student has a name (STRING), a date of birth (DATE) and a grade average (REAL) all at once. A record solves this: it groups related data of different types together under one identifier, so they can be handled as a single unit.

Defining a record type

In Cambridge pseudocode a record structure is defined once with TYPE ... ENDTYPE, then used as a data type in its own right:

TYPE StudentRecord
    DECLARE StudentID : STRING
    DECLARE Name : STRING
    DECLARE DateOfBirth : DATE
    DECLARE GradeAverage : REAL
ENDTYPE

DECLARE Student1 : StudentRecord

Student1 is now a single variable that internally holds all four fields. An individual field is accessed with a dot: Student1.Name, Student1.GradeAverage.

Reading from and writing to a record

OUTPUT "Enter student ID"
INPUT Student1.StudentID
OUTPUT "Enter student name"
INPUT Student1.Name

Student1.GradeAverage <- 78.5

OUTPUT "Student ", Student1.Name, " has average ", Student1.GradeAverage

Arrays of records

Records and arrays combine constantly: an array where every element is a full record is how you model a whole table of real-world data in pseudocode, one student, one book, one loan per element, each with several fields. This is exactly the structure the library system in section 11 is built on:

TYPE LoanRecord
    DECLARE StudentID : STRING
    DECLARE BookID : STRING
    DECLARE OnLoan : BOOLEAN
ENDTYPE

DECLARE Loan : ARRAY[1:5000] OF LoanRecord

// Access the StudentID field of loan record 12
OUTPUT Loan[12].StudentID

An abstract data type (ADT) is a collection of data together with the set of operations defined on that data, described by its behaviour rather than by how it is actually stored in memory. Stacks, queues and linked lists are the three ADTs named explicitly by the syllabus.

Implementing each one using an array

Every variable and array covered so far only exists while the program is running, once it ends, that data is gone. Files exist to solve exactly that: they let a program save data permanently to storage, and read it back in on a later run.

Opening, reading, writing and closing a text file

Because a text file can hold any number of lines, and a program does not know that number in advance, reading a file almost always uses a WHILE loop controlled by EOF, a pre-condition loop is the right choice here since a completely empty file should read zero lines, not one:

OPENFILE "Data.txt" FOR READ
WHILE EOF("Data.txt") = FALSE
    READFILE "Data.txt", OneLine
    OUTPUT OneLine
ENDWHILE
CLOSEFILE "Data.txt"

FUNCTION DeleteComment(Line : STRING) RETURNS STRING
    DECLARE index, LineLength : INTEGER
    DECLARE ThisChar : CHAR
    DECLARE InComment : BOOLEAN
    DECLARE ReturnString : STRING

    ReturnString <- ""
    InComment <- FALSE
    LineLength <- LENGTH(Line)

    FOR index <- 1 TO LineLength
        ThisChar <- MID(Line, index, 1)
        IF InComment = FALSE THEN
            IF ThisChar = '/' AND MID(Line, index, 2) = "//" THEN
                InComment <- TRUE
            ELSE
                ReturnString <- ReturnString & ThisChar
            ENDIF
        ENDIF
    NEXT index
    RETURN ReturnString
ENDFUNCTION


FUNCTION Stage_1(StdName : STRING) RETURNS INTEGER
    DECLARE StdFileName, OutFileName, OneLine, CleanLine : STRING
    DECLARE LineCount : INTEGER

    StdFileName <- StdName & "_src.txt"
    OutFileName <- StdName & "_S1.txt"
    LineCount <- 0

    OPENFILE StdFileName FOR READ
    OPENFILE OutFileName FOR WRITE

    WHILE EOF(StdFileName) = FALSE
        READFILE StdFileName, OneLine
        CleanLine <- DeleteComment(OneLine)
        IF LENGTH(CleanLine) <> 0 THEN
            WRITEFILE OutFileName, CleanLine
            LineCount <- LineCount + 1
        ENDIF
    ENDWHILE

    CLOSEFILE StdFileName
    CLOSEFILE OutFileName
    RETURN LineCount
ENDFUNCTION

Structured programming means building a solution from named, reusable blocks instead of one long unbroken sequence of statements. Cambridge pseudocode gives you two kinds of block.

Terminology

A procedure or function can be declared with no parameters, one, or several, separated by commas in the header.

BYVAL and BYREF

Each parameter is passed in one of two ways, and the syllabus expects you to know the difference:

• BYVAL (by value): a copy of the argument is passed in. Any change made to the parameter inside the block has no effect on the caller's original variable.
• BYREF (by reference): the parameter becomes a direct link to the caller's original variable. Any change made to the parameter inside the block changes that original variable too.

PROCEDURE Swap(BYREF a : INTEGER, BYREF b : INTEGER)
    DECLARE temp : INTEGER
    temp <- a
    a <- b
    b <- temp
ENDPROCEDURE

x <- 5
y <- 9
CALL Swap(x, y)
OUTPUT x, y   // outputs 9, 5: the caller's variables actually changed

If a and b were declared BYVAL instead, Swap would still run correctly inside itself, but x and y back in the calling code would be completely unaffected, the swap would be thrown away the moment the procedure ended.

Worked example: a pure function

FUNCTION IsRA(x1, y1, x2, y2, x3, y3 : INTEGER) RETURNS BOOLEAN
    DECLARE Side1, Side2, Side3 : INTEGER
    DECLARE RA : BOOLEAN

    Side1 <- (x1 - x2)^2 + (y1 - y2)^2
    Side2 <- (x1 - x3)^2 + (y1 - y3)^2
    Side3 <- (x2 - x3)^2 + (y2 - y3)^2

    RA <- FALSE
    IF (Side1 = Side2 + Side3) OR (Side2 = Side1 + Side3) OR (Side3 = Side1 + Side2) THEN
        RA <- TRUE
    ENDIF
    RETURN RA
ENDFUNCTION

// Called from inside an IF condition, its return value is used directly:
IF IsRA(0, 0, 4, 0, 0, 3) THEN
    OUTPUT "Right-angled"
ENDIF

Paper 2's longest questions rarely test one idea in isolation, they hand you a scenario and expect records, arrays, selection, iteration and functions to all show up in the same answer. These two worked programs are built exactly that way.

Case study: a library loan system

PROCEDURE OKToBorrow(sID : STRING)
    DECLARE index, count : INTEGER
    DECLARE LimitReached : BOOLEAN

    count <- 0
    LimitReached <- FALSE
    FOR index <- 1 TO 5000
        IF (Loan[index].StudentID = sID) AND (Loan[index].OnLoan = TRUE) THEN
            count <- count + 1
        ENDIF
    NEXT index

    IF count >= 5 THEN
        LimitReached <- TRUE
    ENDIF

    IF LimitReached = TRUE THEN
        OUTPUT "Cannot borrow, already 5 books on loan"
    ELSE
        OUTPUT "OK to borrow"
    ENDIF
ENDPROCEDURE


FUNCTION NewLoan(sID : STRING, bID : STRING) RETURNS BOOLEAN
    DECLARE index : INTEGER
    DECLARE Found : BOOLEAN

    index <- 1
    Found <- FALSE
    WHILE index <= 5000 AND Found = FALSE
        IF Loan[index].StudentID = "" THEN
            Loan[index].StudentID <- sID
            Loan[index].BookID <- bID
            Loan[index].OnLoan <- TRUE
            Found <- TRUE
        ELSE
            index <- index + 1
        ENDIF
    ENDWHILE
    RETURN Found
ENDFUNCTION


FUNCTION ReturnBook(sID : STRING, bID : STRING) RETURNS BOOLEAN
    DECLARE index : INTEGER
    DECLARE Found, AlreadyReturned : BOOLEAN

    index <- 1
    Found <- FALSE
    AlreadyReturned <- FALSE
    WHILE index <= 5000 AND Found = FALSE
        IF (Loan[index].StudentID = sID) AND (Loan[index].BookID = bID) THEN
            Found <- TRUE
            IF Loan[index].OnLoan = TRUE THEN
                Loan[index].OnLoan <- FALSE
            ELSE
                AlreadyReturned <- TRUE
            ENDIF
        ENDIF
        index <- index + 1
    ENDWHILE

    IF Found = TRUE AND AlreadyReturned = FALSE THEN
        RETURN TRUE
    ELSE
        RETURN FALSE
    ENDIF
ENDFUNCTION


PROCEDURE CountLoans(sID : STRING)
    DECLARE index, Borrowed, Returned : INTEGER

    Borrowed <- 0
    Returned <- 0
    FOR index <- 1 TO 5000
        IF Loan[index].StudentID = sID THEN
            IF Loan[index].OnLoan = TRUE THEN
                Borrowed <- Borrowed + 1
            ELSE
                Returned <- Returned + 1
            ENDIF
        ENDIF
    NEXT index

    OUTPUT "Currently on loan: ", Borrowed
    OUTPUT "Returned: ", Returned
ENDPROCEDURE

Every routine here scans the same Loan array, but reaches for a different loop: OKToBorrow and CountLoans always check all 5000 slots, so a count-controlled FOR fits; NewLoan and ReturnBook can stop the moment they find what they are looking for, so a condition-controlled WHILE with a Found flag is both correct and more efficient.

Case study: pattern printing

PROCEDURE Square(SquareLength : INTEGER)
    DECLARE SquareVal, TempStr : STRING
    DECLARE row, col : INTEGER

    SquareVal <- NUM_TO_STR(SquareLength)

    IF SquareLength = 1 THEN
        OUTPUT SquareVal
    ELSE
        IF SquareLength = 2 THEN
            OUTPUT SquareVal & SquareVal
            OUTPUT SquareVal & SquareVal
        ELSE
            // top border row
            TempStr <- ""
            FOR col <- 1 TO SquareLength
                TempStr <- TempStr & SquareVal
            NEXT col
            OUTPUT TempStr

            // middle rows: border character, then stars, then border character
            FOR row <- 1 TO SquareLength - 2
                TempStr <- ""
                FOR col <- 1 TO SquareLength - 2
                    TempStr <- TempStr & "*"
                NEXT col
                TempStr <- SquareVal & TempStr & SquareVal
                OUTPUT TempStr
            NEXT row

            // bottom border row
            TempStr <- ""
            FOR col <- 1 TO SquareLength
                TempStr <- TempStr & SquareVal
            NEXT col
            OUTPUT TempStr
        ENDIF
    ENDIF
ENDPROCEDURE

This needs three separate cases (1, 2, and everything else) because a square smaller than 3 characters wide has no room for a distinct border and interior, always check your loop bounds against the smallest possible input, not just a "typical" one, this is exactly the instinct section 14's test data section trains.

A development life cycle is a structured set of stages a team follows to turn a problem into a working, maintained piece of software. Its purpose is to make development predictable and manageable, without one, larger projects tend to drift, miss requirements, or ship with untested assumptions. Every life cycle model is built from the same five underlying stages:

5. Maintenance: keep the finished, deployed program working and up to date over time, also covered in section 14.

Different projects need different life cycles, different ways of arranging and repeating those five stages, depending on how well understood the requirements are, how large the system is, and how much risk the team can tolerate.

Both of these are design tools used before coding starts, to plan a program's shape on paper first.

Structure charts

A structure chart shows how a problem has been decomposed into modules (procedures and functions), arranged as a hierarchy, and exactly what data passes between them. Each box is a module, each line connecting two boxes represents a call from the box above to the box below, and each line is labelled with a data couple, an arrow alongside it showing what data flows and in which direction: pointing down into the module for a parameter, pointing up out of it for a returned value.

State-transition diagrams

A state-transition diagram documents a system that moves between a fixed set of distinct states, based on events. Each state is drawn as a circle (or rounded box), and each possible move between two states is a labelled arrow showing the event that triggers it, and any action taken.

A program is not finished when it compiles or runs without crashing, it is finished when it has been shown to do the right thing, including on the inputs nobody expected. This section is where "add extra content on test data types" lives, and it is genuinely one of the highest-yield topics on Paper 2.

Types of error

Testing methods

Test strategy and test plan

A test strategy is the overall approach: which of the methods above will be used, in what order, and why. A test plan turns that strategy into a concrete, executable checklist, so testing is systematic rather than ad hoc. A test plan typically records, for every test: a test number, what it is checking, the exact test data used, the type of that data (see below), the expected outcome, the actual outcome once run, and a pass/fail result.

Choosing test data: normal, boundary, abnormal

Good test data is chosen deliberately to expose faults, not just to confirm the program works when everything goes right. Three categories are expected by name:

Maintenance

Maintenance is everything that happens to a program after it is deployed and in use. The syllabus names three types:

Spot the error