Notes · Computer ScienceUK · A-Levels

Fundamentals of programming

Every program is built from a small set of ideas: values of a given data type held in variables, combined by the three structured constructs of sequence, selection and iteration, and packaged into reusable subroutines. This chapter develops those foundations rigorously, adds the call stack and recursion, and then raises the level of abstraction to the object-oriented paradigm of classes, inheritance and polymorphism. These skills are exercised directly in the on-screen Paper 1 and in the practical project.

5 sections~18 min reading time3 competenciesLevel Foundation 2 · Standard 2 · Advanced 1

T·0111 / 14

Exam profile

AO1 · Know the built-in and structured data types, the three programming constructs, subroutines, scope, recursion and the object-oriented concepts of class, inheritance and polymorphismAO2 · Trace and reason about given code, including nested selection, iteration, parameter passing and recursive callsAO3 · Design and write structured, object-oriented programs and evaluate them (assessed on-screen in Paper 1 and in the NEA)

Operators:defineexplainwrite an algorithmtracedescribecomparedesign

basic level

AS-Level expects confident use of data types, the three constructs, subroutines with parameters, and simple string handling and exception handling.

higher level

The full A-Level adds recursion and the call stack, and the whole object-oriented paradigm - classes, encapsulation, inheritance, polymorphism and composition - which are examined in Paper 1 and demanded by the NEA.

Depth

Text

Contents · 5 sections

Fundamentals of programming

Data types and program structure#

FoundationAQA 7517 4.1.1AQA 7517 4.1.2DfE GCE Computer Science - programming

A data type tells the computer both how to store a value in memory and which operations are legal on it, and choosing the right type is the first design decision in any program. The built-in primitive types are the integer (a whole number), the real or float (a number with a fractional part, stored in floating point), the Boolean (one of the two values true or false), the character (a single symbol such as `A` or `?`), and the string (an ordered sequence of characters). The type fixes the operations: you may take the remainder of two integers but not of two Booleans, and adding the strings "12" and "3" concatenates them to "123" rather than giving 15. Getting the type wrong - for example storing a house number as an integer when it might be "221B" - is a design fault, not a coding slip.

Beyond the primitives, most languages let a programmer build structured and user-defined types. A record groups a fixed set of named fields, each with its own type, into one value - a

\texttt{Student}

record might hold an integer id, a string name and a real mark. An enumerated type lists the permitted values of a small set (the days of the week); a set holds an unordered collection of distinct values. Records are the ancestor of the object: they bundle related data so it can be passed around as a unit, which is exactly what a class will later do while also bundling the operations.

A variable is a named location in memory whose contents may change during execution; a constant is a named value fixed at design time (such as

\texttt{VAT} = 0.20

). Using a named constant rather than a bare literal makes a program readable and safe to change: if the rate changes you edit one line, and the name documents intent. Assignment copies a value into a variable - the statement

\texttt{total} \leftarrow \texttt{total} + \texttt{item}

evaluates the right-hand side first and then stores the result, which is why a variable can sensibly appear on both sides.

The operators divide into three families. Arithmetic operators combine numbers: as well as

+

-

\times

and

/

, A-Level requires integer division (the whole-number quotient, e.g.

17\ \text{DIV}\ 5 = 3

) and modulo (the remainder,

17\ \text{MOD}\ 5 = 2

), which together are indispensable for digit extraction, hashing and wrap-around. Relational operators (

=

\neq

<

\leq

>

\geq

) compare two values and yield a Boolean. Boolean operators (AND, OR, NOT) combine Boolean values and drive every decision the program makes. Knowing the exact result of integer division and modulo is tested routinely, so recompute them rather than guessing.

a = (a\ \text{DIV}\ b)\times b + (a\ \text{MOD}\ b)

Division identity

For integers with $b>0$ , the quotient and remainder always reconstruct the original: e.g. $23 = 5\times4 + 3$ .

Worked example

Extracting the digits of a number

Using only integer division and modulo, describe how to obtain the units, tens and hundreds digits of the integer 472, and give each value.

Units digit
The units digit is the remainder on division by 10: $472\ \text{MOD}\ 10 = 2$ .
Tens digit
Remove the units digit with $472\ \text{DIV}\ 10 = 47$ , then take that modulo 10: $47\ \text{MOD}\ 10 = 7$ .
Hundreds digit
Divide twice by 10: $472\ \text{DIV}\ 100 = 4$ , and $4\ \text{MOD}\ 10 = 4$ .

Result: Units 2, tens 7, hundreds 4. Repeated MOD 10 and DIV 10 peel digits off the right - the same idea underlies converting a number to any base.

Typical mistakes

Storing identifiers such as phone numbers, postcodes or serial numbers as integers - leading zeros are lost and no arithmetic is ever needed, so a string is correct.
Confusing $/$ (real division) with DIV (integer division): $7/2 = 3.5$ but $7\ \text{DIV}\ 2 = 3$ , and the remainder $7\ \text{MOD}\ 2 = 1$ .

Active revision

For each of these values give the most appropriate data type and one reason: a person's age, whether a light is on, a product price, a UK postcode. Then evaluate $23\ \text{DIV}\ 4$ , $23\ \text{MOD}\ 4$ and $-1$ interpreted as a Boolean condition.

Active recall

Recall the key points — then reveal.

Sources: GCE AS and A level subject content for computer science (Department for Education) · AQA A-level Computer Science 7517 specification (AQA)

Sequence, selection and iteration#

FoundationAQA 7517 4.1.3DfE GCE Computer Science - programming constructs

The control flow of a condition-controlled (WHILE) loop

Fig. 1The condition is tested before the body. While it is true the body runs and control loops back to re-test; when it becomes false control leaves the loop. Because the test comes first, the body can run zero times.

Structured programming rests on a remarkable result: any computable algorithm can be expressed using just three control constructs - sequence, selection and iteration - with no need for arbitrary jumps. Sequence is simply executing statements one after another in order; because assignment has side effects, the order matters, and swapping two statements can change the outcome. This is the default flow and needs no keyword.

Selection chooses between alternative paths on a Boolean condition. The two-way form is

\texttt{IF}

condition

\texttt{THEN}

...

\texttt{ELSE}

...

\texttt{ENDIF}

; nesting selections or chaining them with

\texttt{ELSE IF}

handles several mutually exclusive cases, and a

\texttt{CASE}

\texttt{SWITCH}

statement expresses a clean multi-way choice on the value of one variable. A condition may combine relational and Boolean operators, so care with operator precedence and with the boundaries (

<

versus

\leq

) is essential - most selection bugs live exactly at the boundary.

Iteration repeats a block. A count-controlled loop (

\texttt{FOR}\ i \leftarrow 1\ \texttt{TO}\ n

) runs a known number of times and is used when the number of repetitions is fixed in advance. A condition-controlled loop repeats while (or until) a condition holds:

\texttt{WHILE}

tests before the body, so the body may run zero times, whereas

\texttt{REPEAT ... UNTIL}

tests after the body, so it always runs at least once. Choosing the wrong kind - a WHILE where a REPEAT is needed, or vice versa - is a classic off-by-one or empty-input fault. The control flow of a WHILE loop is shown opposite: the condition is the hinge, and the back-edge from the body is what makes it a loop.

Loops are the natural partner of arrays and strings: a count-controlled loop over the indices

0

n-1

visits every element exactly once. The single most common iteration error is the off-by-one: looping to

n

instead of

n-1

over a zero-indexed array reads past the end, and starting a running total at the wrong value corrupts every result. Always check a loop on the smallest cases - an empty collection and a single element - because that is where boundary faults surface.

Worked example

Tracing a nested loop

Trace the value printed by: total = 0; FOR i = 1 TO 3; FOR j = 1 TO 2; total = total + i*j; NEXT j; NEXT i; PRINT total.

i = 1
j = 1 adds $1\times1 = 1$ (total 1); j = 2 adds $1\times2 = 2$ (total 3).
i = 2
j = 1 adds $2\times1 = 2$ (total 5); j = 2 adds $2\times2 = 4$ (total 9).
i = 3
j = 1 adds $3\times1 = 3$ (total 12); j = 2 adds $3\times2 = 6$ (total 18).

Result: The inner loop runs $3\times2 = 6$ times in total and the program prints 18.

Typical mistakes

Using a WHILE loop for input that must be read at least once (where REPEAT ... UNTIL is correct), or vice versa - the pre-test vs post-test distinction is examined.
Off-by-one boundary errors: iterating from 1 to $n$ over a zero-indexed array of length $n$ reads one element beyond the end.

Active revision

Write pseudocode using a WHILE loop that reads numbers until the user enters 0 and prints their total, then state exactly how it behaves if the very first number entered is 0.

Active recall

Recall the key points — then reveal.

Sources: AQA A-level Computer Science 7517 specification (AQA)

Subroutines, parameters, scope and the stack#

StandardAQA 7517 4.1.4AQA 7517 4.1.5DfE GCE Computer Science - subroutines

The call stack during nested subroutine calls

Fig. 2main calls calculate, which calls square. Each call pushes a frame; square finishes first and is popped first (last in, first out), returning control up the chain. Each frame holds that call's locals and its return address.

A subroutine is a named, self-contained block of code that performs one task and can be called from many places. A procedure carries out an action; a function computes and returns a value and can be used inside an expression. Subroutines are the tool of decomposition: they let a large problem be split into small, individually testable pieces, remove duplication, and hide the details of how a task is done behind a meaningful name - the beginnings of abstraction. A program made of well-named subroutines reads like a description of the solution.

A subroutine communicates through parameters. In pass by value a copy of the argument is given to the subroutine, so changes inside it do not affect the caller's variable; in pass by reference the subroutine receives the address of the caller's variable and can therefore change it. The distinction is examined and is a frequent source of bugs: expecting a by-value parameter to update the caller (it will not) or accidentally mutating a shared structure through a reference. Functions ideally take their inputs by value and return a result, leaving the caller's data untouched - a small step towards the purity you will meet in functional programming.

Scope governs where a name is visible. A local variable is declared inside a subroutine and exists only while that subroutine runs; it cannot be seen from outside and is destroyed on return. A global variable is visible everywhere. Locals are strongly preferred: they prevent one subroutine accidentally corrupting another's data, make subroutines reusable, and keep the program's state easy to reason about. Overusing globals couples everything together and is a classic cause of subtle, hard-to-find faults.

Calls are managed by the call stack, a last-in-first-out structure. Each call pushes a stack frame holding the subroutine's parameters, local variables and the return address; when the subroutine finishes, its frame is popped and control resumes at the return address. This is exactly why locals vanish on return and why the most recently called subroutine is the first to finish. The stack also explains stack overflow: unbounded recursion pushes frames faster than they are popped until the stack space is exhausted.

Worked example

By value versus by reference

A procedure increment(x) sets x = x + 1. A caller sets n = 5 and calls increment(n). State the value of n after the call when x is passed (a) by value and (b) by reference.

By value
increment receives a copy of 5 in its own local x. It sets that copy to 6, then its frame is popped. The caller's n is untouched.
By reference
increment receives the address of n, so x and n are the same location. Setting x = x + 1 writes 6 into n itself.

Result: (a) n is still 5; (b) n is 6. The only difference is whether the parameter is a copy or an alias of the caller's variable.

Typical mistakes

Assuming a by-value parameter change is seen by the caller - it is not; only a by-reference parameter (or a returned value that is reassigned) affects the caller.
Relying on global variables for data that should be a parameter or local, which couples subroutines together and breaks reuse.

Active revision

A function swap(a, b) exchanges its two parameters. Explain why, if a and b are passed by value, the caller's variables are unchanged after the call, and what must change for the swap to work.

Active recall

Recall the key points — then reveal.

Sources: AQA A-level Computer Science 7517 specification (AQA)

Recursion, string handling and exception handling#

StandardAQA 7517 4.1.6AQA 7517 4.1.7DfE GCE Computer Science - recursion and exceptions

Recursion is a subroutine that calls itself on a smaller version of the same problem. Every correct recursive definition has two ingredients: one or more base cases that stop the recursion, and a recursive case that moves towards a base case. The factorial is the standard example:

n! = n \times (n-1)!

with base case

0! = 1

. Recursion is powerful when a problem is naturally self-similar - traversing trees, the merge sort, and the Tower of Hanoi are far clearer recursively than iteratively - but it is not free: each call uses a stack frame, so deep or missing-base-case recursion causes a stack overflow. Any recursive routine can in principle be rewritten with an explicit stack and a loop.

String handling operations are examined and used constantly. Typical operations are finding the length, extracting a substring by position, locating a character or substring, concatenating strings, and converting between cases and between strings and numbers. Two conversions matter especially: string-to-integer/real for turning validated input into a number, and integer/real-to-string for building output. Remember that a character has an underlying numeric code (its ASCII/Unicode value), so characters can be compared and shifted arithmetically - the basis of the Caesar cipher.

Exception handling separates the normal flow of a program from its response to run-time errors. A block that might fail is placed in a

\texttt{TRY}

; if an exception is raised (thrown) - a division by zero, a failed type conversion, a missing file - control jumps to a matching

\texttt{CATCH}

\texttt{EXCEPT}

handler rather than crashing, and an optional

\texttt{FINALLY}

block runs either way to release resources. This lets a program fail gracefully: catch the bad input, tell the user, and carry on.

Exception handling is not a substitute for validation. Where an error is predictable - a number outside a range, a wrongly formatted date - it is better and clearer to check for it explicitly and re-prompt; exceptions are for the genuinely exceptional and for errors that cannot be tested for in advance. Overusing exceptions to steer ordinary control flow makes a program slow and hard to follow, and swallowing an exception silently hides faults that should be reported.

n! = \begin{cases} 1 & \text{if } n = 0 \\ n \times (n-1)! & \text{if } n > 0 \end{cases}

Recursive factorial

The base case $0! = 1$ stops the recursion; the recursive case reduces $n$ towards 0.

Worked example

Tracing a recursive factorial

Trace factorial(4), where factorial(n) returns 1 if n = 0 else n * factorial(n-1). Show the descent to the base case and the returns unwinding.

Descend (push frames)
factorial(4) needs 4factorial(3); factorial(3) needs 3factorial(2); factorial(2) needs 2factorial(1); factorial(1) needs 1factorial(0).
Base case
factorial(0) returns 1 - the recursion stops here and the frames now unwind.
Unwind (pop frames)
factorial(1) = $1\times1 = 1$ ; factorial(2) = $2\times1 = 2$ ; factorial(3) = $3\times2 = 6$ ; factorial(4) = $4\times6 = 24$ .

Result: factorial(4) = 24. Five frames were pushed (n = 4 down to 0) and popped in reverse - the call stack in action.

Typical mistakes

Writing recursion with no base case, or a recursive case that does not move towards it, so the recursion never terminates and the stack overflows.
Treating exception handling as ordinary control flow, or catching an exception and doing nothing, which hides the underlying fault.

Active revision

Write a recursive function factorial(n), state its base case, and trace factorial(4) call by call, showing the returns unwinding back up the stack.

Active recall

Recall the key points — then reveal.

Sources: GCE AS and A level subject content for computer science (Department for Education)

Object-oriented programming#

AdvancedAQA 7517 4.1.8DfE GCE Computer Science - object-oriented programming

A class inheritance hierarchy

Fig. 3Animal is the superclass; Mammal and Bird inherit from it, and Dog and Cat inherit from Mammal. Each subclass acquires all attributes and methods of every class above it and may add or override its own - a Dog is-a Mammal is-an Animal.

Object-oriented programming (OOP) raises the level of abstraction from data-plus-subroutines to objects that bundle data and the operations on it together. A class is a blueprint that defines attributes (the data each object holds) and methods (the operations each object can perform); an object is a particular instance of a class, created by instantiation, with its own values for the attributes. A

\texttt{BankAccount}

class might define the attributes balance and owner and the methods deposit and withdraw; each real account is an object of that class.

Encapsulation is the principle that an object's internal data is private and reachable only through its own methods. Attributes are marked private and exposed, where necessary, through public getter and setter methods that can enforce rules - a setter for balance can refuse a negative value. Encapsulation protects an object's invariants, lets the internal representation change without breaking users of the class, and is a concrete realisation of information hiding: the outside world depends on what an object does, not how.

Inheritance lets a subclass be defined as a specialisation of a superclass, automatically acquiring its attributes and methods and adding or overriding its own. It expresses an is-a relationship - a

\texttt{SavingsAccount}

is a

\texttt{BankAccount}

- and removes duplication by placing shared behaviour once in the superclass. The class hierarchy opposite shows a chain of inheritance: a Dog is a Mammal, which is an Animal, so a Dog has every attribute and method defined anywhere up that chain. (Relationships that are has-a rather than is-a - a Car has an Engine - are modelled by composition/aggregation, an object holding a reference to another, not by inheritance.)

Polymorphism means that the same method call can behave differently depending on the object's actual class. If Animal defines a method

\texttt{makeSound}

and both Dog and Cat override it, then calling

\texttt{makeSound}

on a collection of Animals produces a bark or a miaow as appropriate, chosen at run time. Polymorphism, together with inheritance and encapsulation, lets a program be written against general types and extended with new subclasses without changing existing code - the payoff that makes OOP the dominant paradigm for large systems and the natural approach for a substantial NEA project.

Worked example

Overriding a method for polymorphism

Animal defines describe() returning "An animal". Dog inherits from Animal and overrides describe() to return "A dog that barks". If a variable of type Animal actually references a Dog object and describe() is called, what is returned, and what is this called?

Static type vs actual object
The variable's declared type is Animal, but at run time it references a Dog object. Method calls resolve on the actual object's class, not the declared type.
Resolve the call
Because Dog overrides describe(), the Dog version is chosen. If Dog had not overridden it, the inherited Animal version would run instead.

Result: It returns "A dog that barks". Selecting the overriding method at run time from the object's real class is polymorphism (dynamic dispatch).

Typical mistakes

Confusing a class (the blueprint) with an object (an instance of it), or using inheritance for a has-a relationship that should be composition.
Believing inherited private attributes can be accessed directly from a subclass - encapsulation still requires going through inherited public/protected methods.

Active revision

Design a class hierarchy for a library with a base class Item and subclasses Book and DVD. State one attribute and one method for Item that all items share, and one attribute unique to each subclass, and explain where polymorphism would be useful.

Active recall

Recall the key points — then reveal.

Sources: AQA A-level Computer Science 7517 specification (AQA)

References & sources

Sources

Department for Education

GCE AS and A level subject content for computer science

AQA

AQA A-level Computer Science 7517 specification

Fundamentals of programming

5 sections~18 min reading time3 competenciesLevel Foundation 2 · Standard 2 · Advanced 1

Fundamentals of programming

Key points

Extracting the digits of a number

Key points

Tracing a nested loop

Key points

By value versus by reference

Key points

Tracing a recursive factorial

Key points

Overriding a method for polymorphism

Sources

Fundamentals of programming

Key points

Extracting the digits of a number

Key points

Tracing a nested loop

Key points

By value versus by reference

Key points

Tracing a recursive factorial

Key points

Overriding a method for polymorphism

Sources