OCR A Level Computer Science Paper 2 — Last-Minute Revision Guide (H446/02)

OCR A Level Computer Science Component 2 (H446/02) — Algorithms and Programming — is worth 140 marks over 2.5 hours (40% of the A Level), and no calculators are allowed. Expect definitions, tracing, algorithm writing, dry runs, Big-O comparisons, OOP and extended evaluation.

Examiners consistently say the same thing: fluent pseudocode, careful tracing, and detailed standard algorithm knowledge are what separate the top bands. This guide compresses the whole paper for your last 48 hours.

Whole-paper strategy

Question type	What gets the marks
Define / describe	Correct technical term + one consequence or example
Trace an algorithm	A proper trace table — variables, loop counters, output. Don’t do it in your head
Write an algorithm	Clear variable names, initialise values, indent, close every loop/selection
Compare methods	Time, memory, implementation complexity, suitability for the given data
Evaluate / discuss	Balanced points, applied to the scenario, justified judgement at the end

Last 48 hours priorities:

Write linear search, binary search, bubble sort, insertion sort, merge sort, stack, queue, linked list, tree traversal, graph traversal and Dijkstra from memory
Do at least three trace questions: one recursive, one nested loop, one array/list manipulation
Memorise Big-O for the standard algorithms — and why, not just the label

OCR Reference Language crash sheet

Construct	OCR-style form
Assignment	`score = score + 1`
Input/output	`name = INPUT("Enter name")` / `OUTPUT name`
Selection	`IF condition THEN ... ELSE ... ENDIF`
Count-controlled loop	`FOR i = 0 TO 9 ... NEXT i`
Condition-controlled loop	`WHILE condition ... ENDWHILE` / `REPEAT ... UNTIL condition`
Arrays	`numbers[0] = 23`, `LEN(numbers)`
Subroutines	`PROCEDURE Name(params) ... ENDPROCEDURE` / `FUNCTION Name(params) RETURNS type`
Classes	`CLASS Student ... PRIVATE name ... PUBLIC PROCEDURE New(...) ... ENDCLASS`

Habits that gain marks:

Initialise variables before use
Use LEN(array) instead of magic numbers
Show array indexes clearly — state if you’re using 0-based indexing
Use RETURN only in functions, OUTPUT only when something must be displayed
For OOP answers, show attributes, methods, access modifiers and constructor logic

2.1 Computational thinking

Skill	What to remember
Abstraction	Remove unnecessary detail, keep what’s needed — e.g. model a map as a weighted graph (nodes = locations, edges = roads, weights = distance/time)
Thinking ahead	Identify inputs, outputs, validation, edge cases (empty lists, duplicates, full queues) before coding; use caching/memoisation/indexing for repeated lookups
Procedural thinking	Break into ordered steps and subroutines using sequence, selection, iteration
Logical thinking	Boolean expressions, truth tables, check every IF branch is reachable and loops terminate; dry-run normal, boundary and erroneous data
Concurrent thinking	Identify tasks that could run simultaneously; know race conditions, deadlock, starvation, synchronisation

Common exam distinction: decomposition breaks the problem down → abstraction removes unnecessary detail → algorithmic thinking creates the ordered steps → evaluation judges suitability, efficiency and correctness.

2.2 Programming constructs

Construct	Purpose	Exam trap
Sequence	Instructions run in order	Don’t reorder input/processing/output without reason
Selection	IF/CASE chooses a path	Use ELSE for default cases
Iteration	FOR / WHILE / REPEAT	FOR = known repeats; WHILE/REPEAT = condition-based
Subroutine	Reusable named block	Functions return a value; procedures perform actions
Recursion	Subroutine calls itself	Must have a base case that it moves towards

Scope, lifetime and parameters:

Local scope = available only inside its block; global = available everywhere (harder to debug)
Pass by value copies data; pass by reference (BYREF) lets the subroutine change the original

PROCEDURE AddOneByValue(n)
    n = n + 1          // original variable outside is unchanged
ENDPROCEDURE

PROCEDURE AddOneByReference(BYREF n)
    n = n + 1          // original variable outside IS changed
ENDPROCEDURE

Validation vs verification: validation checks data is reasonable (presence, type, range, length, format, lookup, check digit); verification checks data has been copied/transmitted correctly. Good test plans use normal, boundary, invalid data and record input/expected/actual/pass-fail.

Recursion

FUNCTION Factorial(n) RETURNS INTEGER
    IF n = 0 THEN
        RETURN 1
    ELSE
        RETURN n * Factorial(n - 1)
    ENDIF
ENDFUNCTION

Recursion — advantage	Recursion — disadvantage
Elegant for divide-and-conquer, trees, graphs, mathematical definitions	More memory due to stack frames; risk of stack overflow
Often shorter, closer to the problem definition	Harder to trace and debug

Object-oriented programming

Term	Meaning
Class	Template/blueprint defining attributes and methods
Object	Instance of a class with its own attribute values
Constructor	Special method that initialises a new object
Encapsulation	Bundling data + methods, protecting data with private access
Inheritance	A subclass reuses/extends a superclass
Polymorphism	Same method call behaves differently depending on object type
Aggregation/composition	Whole-part relationships; composition implies stronger ownership

CLASS BankAccount
    PRIVATE accountNumber
    PRIVATE balance
    PUBLIC PROCEDURE New(newNumber, openingBalance)
        accountNumber = newNumber
        balance = openingBalance
    ENDPROCEDURE
    PUBLIC FUNCTION GetBalance() RETURNS REAL
        RETURN balance
    ENDFUNCTION
    PUBLIC PROCEDURE Deposit(amount)
        IF amount > 0 THEN
            balance = balance + amount
        ENDIF
    ENDPROCEDURE
ENDCLASS

CLASS SavingsAccount INHERITS BankAccount
    PRIVATE interestRate
    PUBLIC PROCEDURE AddInterest()
        Deposit(GetBalance() * interestRate)
    ENDPROCEDURE
ENDCLASS

OOP exam traps: encapsulation is bundling data with methods and controlling access, not just “hiding data”. Inheritance must model an “is-a” relationship (a Dog IS an Animal). Polymorphism needs an overridden/common method called on different object types.

Data structures

Structure	Best for	Limitation
1D array	Indexed list of same-type values	Fixed size; insert/delete may need shifting
2D array	Tables, grids, matrices	Nested loops, easy to mix up indexes
Record	Grouping fields of one entity	—
Stack (LIFO)	Undo, browser history, expression evaluation, DFS	—
Queue (FIFO)	Print queues, scheduling, buffers, BFS	—
Linked list	Efficient insert/delete at known position	Sequential access only — O(n) search
Hash table	Near O(1) average search/insert/delete	Collisions need handling (probing/chaining); worst case O(n)
Tree (BST)	Ordered hierarchical data	Must stay balanced for efficient search
Graph	Networks, maps, relationships	Adjacency matrix = O(V²) memory; adjacency list = efficient for sparse graphs

Stack push/pop

PROCEDURE Push(BYREF stack, BYREF top, item, maxSize)
    IF top = maxSize - 1 THEN
        OUTPUT "Stack overflow"
    ELSE
        top = top + 1
        stack[top] = item
    ENDIF
ENDPROCEDURE

FUNCTION Pop(BYREF stack, BYREF top) RETURNS STRING
    IF top = -1 THEN
        OUTPUT "Stack underflow"
        RETURN ""
    ELSE
        item = stack[top]
        top = top - 1
        RETURN item
    ENDIF
ENDFUNCTION

Binary tree traversals

Traversal	Order	Use
In-order	Left, root, right	Outputs a BST in sorted order
Pre-order	Root, left, right	Copying/serialising a tree
Post-order	Left, right, root	Deleting a tree; evaluating expression trees

2.3 Algorithms & Big-O

Complexity	Meaning	Example
O(1)	Constant	Array index access
O(log n)	Halves each time	Binary search
O(n)	Linear	Linear search
O(n log n)	Efficient divide-and-conquer	Merge sort, quicksort average
O(n²)	Nested loops	Bubble sort, insertion sort (worst)
O(2ⁿ)	Doubles per item	Brute-force combinational problems
O(n!)	All permutations	Brute-force travelling salesman

No calculator? No problem. For growth-rate questions, just compare the broad shape: log n < n < n log n < n² < 2ⁿ < n!

P / NP / heuristics: tractable = solvable in reasonable polynomial time (O(n), O(n log n), O(n²)); intractable = exact solution impractical for large inputs; heuristic = practical approximation when exact algorithms are too slow.

Standard algorithm comparison

Algorithm	Precondition	Best	Average/Worst
Linear search	None	O(1)	O(n)
Binary search	Sorted data	O(1)	O(log n)
Bubble sort	None	O(n) optimised	O(n²)
Insertion sort	None	O(n)	O(n²)
Merge sort	None	O(n log n)	O(n log n)
Quicksort	None	O(n log n)	O(n²) worst (poor pivot)

The standard algorithm bank

Binary search

FUNCTION BinarySearch(values, target) RETURNS INTEGER
    low = 0
    high = LEN(values) - 1
    WHILE low <= high
        mid = (low + high) DIV 2
        IF values[mid] = target THEN
            RETURN mid
        ELSEIF target < values[mid] THEN
            high = mid - 1
        ELSE
            low = mid + 1
        ENDIF
    ENDWHILE
    RETURN -1
ENDFUNCTION

Bubble sort

PROCEDURE BubbleSort(BYREF values)
    FOR pass = 0 TO LEN(values) - 2
        FOR i = 0 TO LEN(values) - 2 - pass
            IF values[i] > values[i + 1] THEN
                Swap(values, i, i + 1)
            ENDIF
        NEXT i
    NEXT pass
ENDPROCEDURE

Merge sort

FUNCTION MergeSort(values) RETURNS ARRAY
    IF LEN(values) <= 1 THEN
        RETURN values
    ENDIF
    mid = LEN(values) DIV 2
    left = MergeSort(SUBARRAY(values, 0, mid - 1))
    right = MergeSort(SUBARRAY(values, mid, LEN(values) - 1))
    RETURN Merge(left, right)
ENDFUNCTION

BFS and DFS

PROCEDURE BFS(graph, start)
    visited.ADD(start)
    Enqueue(q, start)
    WHILE q is not empty
        node = Dequeue(q)
        OUTPUT node
        FOR EACH neighbour IN graph[node]
            IF neighbour NOT IN visited THEN
                visited.ADD(neighbour)
                Enqueue(q, neighbour)
            ENDIF
        NEXT neighbour
    ENDWHILE
ENDPROCEDURE

PROCEDURE DFS(graph, node, BYREF visited)
    visited.ADD(node)
    OUTPUT node
    FOR EACH neighbour IN graph[node]
        IF neighbour NOT IN visited THEN
            DFS(graph, neighbour, visited)
        ENDIF
    NEXT neighbour
ENDPROCEDURE

BFS uses a queue, visits level by level, finds shortest path in an unweighted graph
DFS uses a stack (or recursion), goes as deep as possible before backtracking — used for path finding and connected components

Dijkstra’s algorithm

PROCEDURE Dijkstra(graph, start)
    FOR EACH node IN graph
        distance[node] = INFINITY
        previous[node] = NULL
        unvisited.ADD(node)
    NEXT node
    distance[start] = 0
    WHILE unvisited is not empty
        current = node in unvisited with smallest distance
        unvisited.REMOVE(current)
        FOR EACH neighbour IN graph[current]
            alt = distance[current] + weight(current, neighbour)
            IF neighbour IN unvisited AND alt < distance[neighbour] THEN
                distance[neighbour] = alt
                previous[neighbour] = current
            ENDIF
        NEXT neighbour
    ENDWHILE
ENDPROCEDURE

Exam table method: start node = 0, all others = infinity. Each step, pick the unvisited node with the smallest tentative distance and make it permanent. Update each unvisited neighbour if the route through the current node is shorter. Use the previous-node column to reconstruct the route backwards.

A* search

f(n) = g(n) + h(n) — g = known cost so far, h = heuristic estimate to the goal
With an admissible heuristic (never overestimates), A* finds an optimal path — and is often faster than Dijkstra because the heuristic guides it towards the target

Backtracking

FUNCTION SolveMaze(position) RETURNS BOOLEAN
    IF position is goal THEN
        RETURN TRUE
    ENDIF
    Mark position as visited
    FOR EACH nextPosition from position
        IF nextPosition is valid AND nextPosition is not visited THEN
            IF SolveMaze(nextPosition) = TRUE THEN
                RETURN TRUE
            ENDIF
        ENDIF
    NEXT nextPosition
    Unmark position if path needs to be reused
    RETURN FALSE
ENDFUNCTION

Try a choice → recurse → undo if it fails. Used for mazes, Sudoku, N-Queens, constraint satisfaction.

Trace tables — don’t skip this

A trace table records every variable each time it changes, including loop counters and Boolean flags. Record output separately. For arrays, write the whole array after each pass that mutates it. For recursion, list each call on its own line with parameters and return value — and always check the final condition that ends the loop, since extra/missing iterations lose marks constantly.

Extended response mini-templates

Compare two algorithms:

State the main difference in method
State the time complexity of each
State any preconditions (e.g. sorted data for binary search)
Apply to the scenario — data size, frequency of searches, memory limits, how often data changes
Make a justified recommendation

Discuss using OOP: classes model real-world entities clearly; encapsulation protects data; inheritance/polymorphism reduce duplication — but OOP can be unnecessary complexity for small procedural problems, and poor class design causes tight coupling.

Recursive vs iterative: recursion is clearer for trees/graphs/divide-and-conquer; iteration is more memory-efficient (no call stack frames); recursion risks stack overflow if depth is large or the base case is wrong. Always link your answer back to the problem context.

The night before

Don’t try to relearn everything from scratch — reproduce the standard algorithm bank above, then check and correct it
Sleep is more valuable than one more late-night past paper
Take a ruler and pencil for traces/tables — write variables clearly and leave space for array states

Good luck for Wednesday! For more topic-by-topic notes and practice, visit the OCR A Level Computer Science revision hub or browse the full A Level revision notes on CompSci Tutoring.