Topics

How to revise with these notes

• Read, then close the page. After each section, try to explain it out loud or write the key terms from memory.
• Answer before you look. Each question shows its marks. One mark usually means one distinct point, so a 4-mark question needs four separate ideas.
• Use the command word. State wants a short fact. Describe wants what happens. Explain wants why or how. Compare wants both sides of each point.
• Mark your progress. Use the button at the end of each topic. Your progress is saved in this browser only.

Everything inside a computer, from numbers and text to photos and music, is stored as patterns of bits. This topic is about how those patterns are chosen, how big the files get, and how compression makes them smaller.

Number bases

A bit is a single binary digit (0 or 1). Eight bits make a byte, and four bits make a nibble. You need to convert fluently between three bases.

• Denary (base 10): the numbers people use every day.
• Binary (base 2): how the computer actually stores values.
• Hexadecimal (base 16): digits 0 to 9 then A to F (A = 10 … F = 15). One hex digit represents exactly one nibble.

To convert 181 to hex, split the binary into nibbles: 1011 = 11 = B and 0101 = 5, so 181 = B5.

Why programmers use hex: it is shorter than binary, easier to read and copy, and less error-prone, yet it converts directly to binary. You see it in MAC addresses, HTML colour codes such as #FF8800, memory dumps and error codes.

Binary prefixes

Storage is measured in powers of 2, but the familiar prefixes (kilo, mega …) are powers of 10. The IEC binary prefixes remove the confusion.

Negative numbers: one's and two's complement

In two's complement the most significant bit (MSB) has a negative place value. In 8 bits the column values are −128, 64, 32, 16, 8, 4, 2, 1, so the range is −128 to +127.

To write a negative number: write the positive version in binary, flip every bit (that gives the one's complement), then add 1.

Binary arithmetic and overflow

Binary addition follows four rules: 0+0 = 0, 0+1 = 1, 1+1 = 0 carry 1, and 1+1+1 = 1 carry 1. To subtract, add the two's complement of the second number and ignore any carry out of the MSB.

  45 − 20  =  45 + (−20)
    0010 1101      (+45)
  + 1110 1100      (−20)
  -----------
  1 0001 1001      discard the carry out  →  0001 1001 = 25 ✓

Overflow happens when a result is too large for the number of bits available. In two's complement you can spot it when two positives give a negative result, or two negatives give a positive one.

    0101 1010      (+90)
  + 0011 1100      (+60)
  -----------
    1001 0110      the MSB is 1, so this reads as −106, not +150. Overflow.

Binary-coded decimal (BCD)

In BCD each denary digit is stored as its own 4-bit nibble. For example, 59 is 0101 1001, not the pure binary 0011 1011. Nibbles 1010 to 1111 are never used.

• Uses: digital clocks, calculators and electronic displays, where each digit is shown separately; and financial values, where BCD avoids the rounding errors of binary fractions.
• Drawback: it wastes space compared with pure binary, and arithmetic is more complex.

Character sets

Character set

The full list of characters a computer recognises, each with a unique binary code.

ASCII

Uses 7 bits, so 128 characters: English letters, digits, punctuation and control codes. Extended ASCII uses 8 bits for 256 characters.

Unicode

Uses up to 4 bytes per character, so it can represent every writing system (Urdu, Arabic, Chinese …) plus symbols and emoji. Its first 128 codes match ASCII.

Codes run in order: 'A' = 65, 'B' = 66 …; 'a' = 97; '0' = 48. This is why programs can sort text and convert case with arithmetic, for example CHR(ASC('a') − 32) gives 'A'. Unicode's drawback is that each character can take more storage than in ASCII.

Bitmap images

Pixel

The smallest addressable element (picture element) of an image.

Colour depth

The number of bits used to store the colour of one pixel. n bits give 2ⁿ possible colours.

Image resolution

The number of pixels in the image, written as width × height.

Screen resolution

The number of pixels the screen can display, width × height.

File header

Data at the start of the file describing the image: file type, width, height, colour depth, compression used.

File size (bits) = width × height × colour depth

Increasing the resolution or colour depth improves quality but increases the file size.

Vector graphics

A vector graphic stores a drawing list: a set of drawing objects (lines, circles, rectangles, curves) and the properties of each one, such as its coordinates, radius, line colour, line thickness and fill colour. The image is redrawn from these instructions whenever it is displayed.

Sound

Sound is an analogue wave. To store it digitally the amplitude is measured (sampled) at regular intervals by an analogue-to-digital converter.

Sampling rate

The number of samples taken per second, measured in hertz (Hz).

Sampling resolution

The number of bits used to store each sample (also called bit depth).

File size (bits) = sampling rate × sampling resolution × length in seconds (× number of channels)

A higher sampling rate or resolution gives a closer match to the original sound, but a larger file.

Compression

Compression reduces file size so files take less storage, transfer faster and use less bandwidth.

Run-length encoding (RLE)

RLE replaces a run of identical values with one copy of the value and a count. A row of pixels W W W W B B W W W becomes 4W 2B 3W; the text AAAAABBBCCCCCCCC becomes 5A 3B 8C. RLE works well on images with large blocks of colour but can make files bigger when there are few repeats, such as in photographs.

How lossy methods save space

• Images: reduce the resolution or colour depth, or (as JPEG does) remove fine detail and colour differences the human eye barely notices.
• Sound: perceptual coding removes frequencies outside human hearing and quiet sounds masked by louder ones. Lowering the sampling rate or resolution also helps.

Exam-style questions

Written in the style of Paper 1. Answer without a calculator, as in the exam.

A network is two or more devices connected so they can share data and resources. This topic covers how networks are organised, the hardware that connects them, how the internet finds a device, and how media is streamed.

LANs and WANs

Reasons for networking: share files, printers and an internet connection; central backups; communication such as email; software can be installed and updated centrally.

Client-server and peer-to-peer

Thin and thick clients

A thin client depends heavily on the server: it needs a constant connection and does little processing itself, so it is cheap and easy to manage. A thick (fat) client can process and store data locally and still work when the connection drops, but costs more and is harder to keep updated and secure.

Network topologies

Cloud computing

Cloud computing means using storage, software or processing power provided over the internet by remote servers. A public cloud is shared infrastructure run by a provider and sold to anyone. A private cloud is dedicated to one organisation, either on its own servers or hosted for it.

• Benefits: access from anywhere on any device; no need to buy and maintain your own hardware; storage scales up or down as needed; the provider handles backups and security patches.
• Drawbacks: needs a reliable internet connection; data security and privacy depend on the provider; ongoing subscription costs; the provider could go out of business or suffer an outage.

Wired and wireless transmission

Network hardware

Network Interface Card (NIC)

Connects a device to a wired network. It has a unique MAC address.

Wireless NIC (WNIC)

Lets a device connect to a wireless network.

Wireless Access Point (WAP)

Lets wireless devices join a wired network.

Switch

Connects devices in a LAN. It reads the destination MAC address and sends each frame only to the device it is for.

Router

Connects different networks (for example a LAN to the internet) and forwards packets towards their destination using IP addresses.

Bridge

Joins two LAN segments that use the same protocol so they act as one network.

Repeater

Regenerates (boosts) a signal so it can travel further along a cable.

Server

A computer that provides a service to clients, such as a file, web, print or mail server.

Modem

Converts digital signals to analogue for transmission over telephone lines, and back again.

The internet is carried over a mix of infrastructure: the public switched telephone network (PSTN), dedicated (leased) lines, and the cell phone network.

Ethernet and CSMA/CD

Ethernet is the most common protocol for wired LANs. Data is sent in frames containing the source and destination MAC addresses. On a shared medium, two devices may transmit at once and cause a collision. CSMA/CD (Carrier Sense Multiple Access with Collision Detection) deals with this:

1. A device that wants to send listens to check whether the channel is idle (carrier sense).
2. If it is idle, the device starts transmitting; otherwise it waits.
3. While transmitting, the device keeps listening for a collision.
4. If it detects a collision, it stops and sends a jam signal so every device knows.
5. Each device waits a random time (back-off) before trying again, so they are unlikely to collide again.

The internet and the World Wide Web

The internet is the global network of interconnected networks: the hardware and infrastructure. The World Wide Web is a collection of linked web pages and resources that are accessed using the internet, through a browser and HTTP(S). Email and online gaming also use the internet but are not part of the web.

IP addressing

Why IPv6: IPv4 allows only about 4.3 billion addresses, which have run out as more devices connect. IPv6 gives 2¹²⁸ addresses, and it removes the need for workarounds such as address translation.

Public IP address

Unique across the whole internet, assigned by an ISP. It can be reached from the internet.

Private IP address

Used only inside a LAN (for example ranges starting 192.168. or 10.). It can be reused on other LANs and cannot be reached directly from the internet; the router translates it.

Static IP address

Stays the same every time the device connects. Used for servers that must always be found at the same address.

Dynamic IP address

Allocated each time the device connects (by DHCP) and may change. It makes efficient use of a limited pool of addresses.

Subnetting

Dividing a network into smaller sub-networks. The IP address is split into a network ID and a host ID. Subnetting improves security and management and reduces traffic, because data stays inside its subnet.

URLs and the Domain Name Service

A URL (Uniform Resource Locator) is the text address of a resource, for example https://www.example.com/notes/page1.html: protocol, domain name, then path. People remember names; computers need IP addresses. The DNS converts one to the other:

1. The user types a URL into the browser.
2. The browser sends the domain name to a DNS server (the browser and operating system check their own caches first).
3. The DNS server looks up the domain name in its database. If it doesn't have the entry, it passes the request to another DNS server higher in the hierarchy.
4. The IP address is returned to the browser, which may cache it.
5. The browser sends its request to the web server at that IP address.

Streaming

Bit streaming sends media as a continuous stream of bits, so playback begins before the whole file has downloaded. Real-time streaming sends a live event as it happens; on-demand streaming sends stored media whenever a user chooses to watch.

The receiver stores incoming data in a buffer. The media player reads from the buffer at a steady rate while new data keeps arriving, so short drops in network speed don't interrupt playback. The higher the bit rate (bits per second) needed, the faster the connection must be: higher-quality video needs more bandwidth.

Exam-style questions

A computer needs devices to take data in, put results out, and store things for the short and long term. The second half of this topic goes down to the logic gates every processor is built from.

Why a computer needs each type of hardware

Input devices

Let data and instructions enter the computer (keyboard, microphone, touchscreen, sensors).

Output devices

Present results to the user or another system (screen, printer, speakers, actuators).

Primary memory

RAM and ROM, directly accessible by the CPU. RAM holds the programs and data currently in use.

Secondary storage

Non-volatile storage that keeps programs and files when the power is off (hard disk, SSD, optical disc). Removable storage such as USB flash drives lets data be moved between computers or kept as a backup.

Embedded systems

An embedded system is a small computer built into a larger device to carry out one dedicated function, such as the controller in a washing machine, microwave, car engine management unit or smart thermostat. It usually has a microcontroller with its program stored in ROM or flash memory.

• Benefits: small, cheap to mass-produce, low power, reliable, and starts instantly.
• Drawbacks: hard or impossible to upgrade, and difficult to repair. If connected to the internet, it can be a security risk.

How the main devices work

Laser printer

1. The printing drum is given an electrostatic charge.
2. A laser beam scans across the rotating drum, removing the charge where the image should not be, so a charged pattern of the page is left.
3. Charged toner is attracted to the charged areas of the drum.
4. The paper is given a charge and passes over the drum, so the toner transfers onto the paper.
5. A fuser (heated rollers) melts the toner so it is fixed permanently to the paper.
6. A discharge lamp removes the remaining charge from the drum ready for the next page.

3D printer

A 3D design (from CAD software) is sliced into thin horizontal layers. The printer builds the object one layer at a time, usually by extruding melted plastic through a heated nozzle that moves in the x and y directions, while the platform moves down. Other types use resin cured by a UV laser, or powder fused by a laser.

Microphone and speaker

In a microphone, sound waves make a diaphragm vibrate. The vibration moves a coil in a magnetic field (or changes capacitance), producing a varying electrical signal. This analogue signal is converted to digital by an ADC.

In a speaker, a DAC converts digital data to an analogue electrical signal. The current flows through a coil attached to a cone; the changing current makes the coil move in and out within a permanent magnet's field, so the cone vibrates and creates sound waves.

Magnetic hard disk

Data is stored on spinning platters coated with magnetic material. Each surface is divided into concentric tracks, which are split into sectors. A read/write head on an actuator arm moves across the platter. To write, the head magnetises tiny areas in one of two directions to represent 1 or 0; to read, it detects the direction of magnetisation.

Solid-state (flash) memory

An SSD stores data in NAND flash memory made of transistors arranged in a grid. Each cell traps electrons in a floating gate (insulated by an oxide layer) to represent a bit, so the data stays when power is removed. There are no moving parts, which makes SSDs faster, quieter, more robust and lower power than hard disks, though cells can wear out after many writes.

Optical disc reader and writer

A laser shines onto the surface of a spinning disc, following a single spiral track. The surface has pits and lands that reflect light differently; a sensor detects the reflected light and the changes are read as binary. To write, a higher-power laser burns marks into a dye layer. Blu-ray uses a shorter-wavelength (blue) laser, so data can be packed more densely than on CD or DVD.

Touchscreen

A capacitive screen has a conductive layer carrying an electrostatic field. A finger (which conducts) changes the capacitance at the point touched, and the controller calculates its position from sensors at the corners. It supports multi-touch but doesn't work with ordinary gloves. A resistive screen has two flexible conductive layers separated by a gap; pressing joins them at that point and completes a circuit. It works with any stylus but is less clear and less responsive.

Virtual reality headset

The headset has two small screens (one per eye) showing slightly different images, so the user sees in stereoscopic 3D. Lenses focus the image. Sensors such as gyroscopes and accelerometers track head movement, and the image is updated to match so the user feels inside the scene. Headphones give spatial sound, and some headsets track eye movement too.

Buffers

A buffer is a temporary area of memory that holds data being transferred between two devices or processes that work at different speeds. For example, a printer buffer receives a whole document quickly from the CPU, so the CPU can carry on with other tasks while the slower printer prints from the buffer. Video streaming uses a buffer in the same way.

RAM and ROM

SRAM and DRAM

Types of ROM

PROM

Programmable ROM: blank when made, can be programmed once by the user (fuses are burnt) and then can't be changed.

EPROM

Erasable PROM: can be erased by exposing the chip to ultraviolet light through a window, then reprogrammed. The chip must be removed to be erased, and the whole chip is erased at once.

EEPROM

Electrically Erasable PROM: can be erased and rewritten electrically while still in the device, byte by byte. Flash memory is a type of EEPROM. Used for firmware that may need updating.

Monitoring and control systems

A monitoring system uses sensors to read the environment and alerts or records, but doesn't change anything (for example a hospital heart monitor or pollution monitor). A control system also uses actuators (motors, valves, heaters, pumps) to change the environment.

Most control systems use feedback: the output affects the next input. For example, a greenhouse:

1. A temperature sensor sends a reading, converted to digital by an ADC.
2. The microprocessor compares the reading with the stored target value.
3. If it is too cold, a signal is sent (through a DAC if needed) to an actuator to turn on the heater; if too hot, to open a window.
4. The process repeats continuously, so the new temperature is read and the system keeps adjusting.

Logic gates

A logic gate takes one or more binary inputs and produces one binary output. Learn the symbol and truth table for each of these six.

Logic circuits and expressions

Gates join to make circuits. You must be able to move between four forms: a problem statement, a logic expression, a circuit diagram and a truth table. Here is the circuit for X = (A AND B) OR (NOT C):

Exam-style questions

The CPU fetches instructions from memory, decodes them and executes them, billions of times a second. You need to know the parts involved, the registers that hold values along the way, and how to read and trace simple assembly language.

The Von Neumann model

Almost all general-purpose computers follow the Von Neumann architecture. Its key idea is the stored program concept: program instructions and data are both stored in the same main memory, and instructions are fetched and executed one at a time, in sequence.

Registers

A register is a very fast storage location inside the CPU. General-purpose registers hold any data the program is working with; special-purpose registers each have one job.

Other components

Arithmetic Logic Unit

Carries out arithmetic (add, subtract) and logic operations (AND, OR, comparisons, shifts).

Control Unit

Decodes instructions and sends control signals to coordinate every other part of the CPU and the movement of data.

System clock

Produces timing signals at a fixed rate so that all components work in step.

Immediate Access Store

Main memory (RAM) that the CPU can access directly, holding the program and data in use.

Buses

What affects CPU performance

• Clock speed: more cycles per second means more instructions executed per second (but more heat).
• Number of cores: each core can process instructions independently, so several tasks run at the same time. The software must be able to split its work for this to help.
• Bus width: a wider data bus moves more bits per transfer; a wider address bus can address more memory.
• Cache memory: fast memory close to the CPU holding frequently used instructions and data, so the CPU waits less for slower RAM. More cache means more hits.

Ports

USB

Universal Serial Bus. Connects many kinds of peripherals; devices are detected automatically and the right driver is loaded; supplies power; data travels serially.

HDMI

High Definition Multimedia Interface. Sends high-definition digital video and audio together to monitors and TVs; supports encryption to protect content.

VGA

Video Graphics Array. An older port that sends analogue video only, with no audio, so quality is lower at high resolutions.

The fetch-execute cycle

Register Transfer Notation (RTN) shows data moving between registers. Square brackets mean "the contents of", so [PC] is the value in the PC.

Interrupts

An interrupt is a signal to the processor that something needs attention. It can come from hardware (a key press, a printer out of paper), software (division by zero, a program requesting a service) or a timer.

1. At the end of each fetch-execute cycle, the processor checks for an interrupt.
2. If there is one with a higher priority than the current task, the contents of the registers (including the PC) are saved on a stack.
3. The address of the correct Interrupt Service Routine (ISR) is loaded into the PC, and the ISR runs.
4. When the ISR finishes, the saved register values are restored and the original task continues where it left off.

Assembly language

Machine code is binary instructions the processor runs directly. Assembly language replaces each binary opcode with a mnemonic such as LDD or ADD, so there is usually one assembly instruction per machine code instruction. An assembler translates it.

The two-pass assembler

• Pass 1: reads the program line by line, removes comments, and builds a symbol table containing every label (symbolic address) and the address it stands for. Labels used before they are defined (forward references) are added and resolved later in the pass.
• Pass 2: uses the symbol table to replace each label with its address, converts each opcode mnemonic to its binary opcode, and produces the object (machine) code.

Addressing modes

Immediate

The operand is the value to use. LDM #25 loads 25.

Direct

The operand is the address of the value. LDD 150 loads whatever is stored at address 150.

Indirect

The operand is an address that holds another address; the value is at that second address. LDI 150.

Indexed

The address used is the operand plus the contents of the IX. LDX 150 with IX = 3 loads from address 153.

Relative

The address is given as an offset from the current instruction's address, so code still works if it is moved in memory.

The instruction set used in 9618 papers

In operands, # means a denary value, B a binary value and & a hexadecimal value, such as #12, #B00001100, #&0C.

Worked example: tracing a program

This program adds up the whole numbers from the value at address 301 down to 1. Address 301 starts at 3.

100  LDM #0
101  STO 300
102  LDD 301
103  CMP #0
104  JPE 112
105  LDD 300
106  ADD 301
107  STO 300
108  LDD 301
109  DEC ACC
110  STO 301
111  JMP 102
112  LDD 300
113  END

Each loop adds the counter (301) to the total (300), then decreases the counter. When the counter reaches 0, the comparison at 103 is true and the program jumps to 112. The total ends as 3 + 2 + 1 = 6.

Bit manipulation

Shifts

Logical shift

Bits move left or right; the bit shifted out is lost and a 0 enters at the other end. A left shift of 1 multiplies an unsigned number by 2; a right shift divides by 2 (if no 1s are lost).

Arithmetic shift

Like a logical shift, but the sign bit is preserved, so it works correctly on two's complement numbers. On a right shift, the sign bit is copied into the space.

Cyclic shift

The bit shifted out of one end goes back in at the other end, so no bits are lost (also called a rotate).

Masks

A mask is a bit pattern used with a logic operation to work on particular bits. This is how a control program checks or changes individual flags, for example one bit per sensor in a status byte.

Exam-style questions

System software runs the computer itself rather than doing a job for the user. The operating system manages the hardware and other programs; utilities keep the system healthy; translators turn source code into something the processor can run.

Why a computer needs an operating system

Without an OS, every application would have to control the hardware directly. The OS provides a user interface, hides the complexity of the hardware, and manages resources so several programs can run safely at once.

Utility software

Disk formatter

Prepares a disk for first use by dividing it into tracks and sectors and setting up a file system. It deletes existing data and can check for bad sectors.

Virus checker

Scans files and memory for viruses by comparing them with a database of known virus signatures, and by watching for suspicious behaviour (heuristics). Infected files are quarantined or deleted. It must be updated regularly.

Defragmentation software

Over time, files are split into fragments scattered across a hard disk. The defragmenter moves the fragments so each file is stored in contiguous sectors and free space is grouped together. The read/write head moves less, so files load faster. (Not needed on SSDs.)

Disk contents analysis and repair

Checks the disk for errors and bad sectors, marks them so they won't be used, and recovers data where possible. It also shows how the space is being used.

File compression

Reduces the size of files so they use less storage and are faster to send.

Back-up software

Makes copies of files on a schedule, often only those that changed since the last backup (incremental), so data can be restored if lost.

Program libraries

A program library is a collection of pre-written, pre-tested, ready-compiled routines (such as maths or graphics functions) that programmers can use in their own programs.

• Benefits: saves development time; the code has already been tested, so it is more reliable; specialist routines can be used without the programmer having the expertise to write them.

Dynamic Link Libraries (DLLs)

A DLL file is linked to a program only when the program runs, rather than copied into the executable at compile time.

• Benefits: executables are smaller; one copy in memory can be shared by several programs at once, saving RAM; the DLL can be updated without recompiling every program that uses it.
• Drawbacks: if the DLL is missing, renamed or corrupted, the program won't run; an updated DLL may be incompatible with programs written for the old version; the program depends on something outside the programmer's control.

Language translators

Programs written in assembly or a high-level language must be translated into machine code. There are three kinds of translator.

Assembler

Translates assembly language into machine code, usually one machine instruction per assembly instruction.

Compiler

Translates the whole high-level program into an executable machine code file before it runs.

Interpreter

Translates and executes the program one statement at a time, without producing a separate executable file.

Partly compiled, partly interpreted: Java source code is compiled into bytecode, an intermediate form. The Java Virtual Machine then interprets (or just-in-time compiles) the bytecode on each computer. This makes the same compiled program portable to any platform with a JVM. Python works similarly.

Integrated Development Environments

An IDE is a single program that provides the tools needed to write, test and debug code.

Exam-style questions

Three different ideas are easy to mix up in an exam: keeping data safe from loss and attack (security), controlling who may see personal data (privacy), and making sure data is accurate (integrity).

Security, privacy and integrity

Data security

Protecting data against loss, damage or unauthorised access, for example with backups, passwords and firewalls.

Data privacy

Keeping personal data from being seen or used by people who don't have the right to. Data protection laws require organisations to collect only necessary data, keep it accurate and secure, and use it only for the stated purpose.

Data integrity

Making sure data is accurate, complete and consistent: correct when entered and unchanged when stored or transmitted.

Data must be kept secure because it may be confidential (medical records, bank details), valuable to the organisation, or needed by law. Losing it can cause financial loss, legal action and damage to reputation.

Threats

Virus

Malicious code that attaches itself to a program or file and replicates when the host runs. It can delete or corrupt data, or make the computer unusable.

Worm

A standalone program that replicates itself across a network without needing a host file or user action, often using up bandwidth and resources.

Spyware

Secretly monitors the user, for example by recording keystrokes (a key logger), and sends the information to a third party, who may use it to steal passwords or bank details.

Hacking

Gaining unauthorised access to a computer system, possibly to steal, change or delete data.

Phishing

An email or message that appears to come from a trusted source and tries to trick the user into revealing personal data, often by following a link to a fake website.

Pharming

Malicious code installed on a computer or DNS server redirects the user from a genuine website to a fake one, even when the correct URL is typed.

Security measures

• User accounts and access rights: each user logs in with their own account and can only read, write or delete the data their role allows.
• Passwords: should be strong (long, mixed characters), changed regularly and never shared. Systems can lock an account after several failed attempts.
• Authentication: proving who a user is, using passwords, biometrics (fingerprint, face, iris), two-factor authentication or digital signatures.
• Firewall: hardware or software that monitors traffic between a network and the internet, and blocks traffic that doesn't meet a set of rules, such as from unauthorised IP addresses or ports.
• Anti-virus and anti-spyware software: detect and remove malware; scan files in real time.
• Encryption: scrambles data with a key so that, if it is intercepted or stolen, it cannot be understood without the key. It does not stop the data being intercepted.
• Backup: copies of data stored separately (ideally off-site or in the cloud) so lost or corrupted data can be restored. Disk mirroring writes data to two disks at once.

Validation

Validation is an automatic check by the computer that data entered is reasonable and meets set rules. It can't check that data is actually correct: a valid date of birth could still be the wrong one.

Check digit example (modulo 11)

For the code 3572, multiply each digit by a weight (5, 4, 3, 2) and add: 15 + 20 + 21 + 4 = 60. Find the remainder after dividing by 11: 60 MOD 11 = 5. The check digit is 11 − 5 = 6, so the full code is 35726. When the code is entered, the computer recalculates the check digit and compares. This catches most single-digit errors and transposed digits.

Verification

Verification checks that data has been copied accurately from one place to another: when typed in, or when transferred.

During data entry

• Visual check: the user reads the data on screen and compares it with the original document.
• Double entry: the data is entered twice (often by different people, or a password typed twice) and the computer compares the two entries.

During data transfer

• Parity check: the sender and receiver agree on even or odd parity. A parity bit is set so that each byte has an even (or odd) number of 1s. The receiver counts the 1s in each byte; if the parity is wrong, an error has occurred. A single parity bit cannot detect an even number of bit errors in the same byte, and cannot show which bit is wrong.
• Parity block (parity byte): data is sent in a block of bytes, each with a parity bit, plus a final parity byte that holds a parity bit for each column. If one bit is wrong, the faulty row and column cross at that bit, so it can be located and corrected.
• Checksum: the sender calculates a value from the block of data using an agreed algorithm and sends it with the block. The receiver recalculates the checksum and compares; if they differ, the data is requested again.

Worked example: parity block with even parity

The first bit of each byte is the parity bit. One bit was changed in transmission.

Byte 3 has an odd number of 1s and column 6 has an odd number of 1s. They cross at byte 3, bit 6, so that bit is flipped back from 1 to 0. The corrected byte is 0111 0001.

Exam-style questions

Computer professionals make decisions that affect clients, users and the public. This topic covers the codes of conduct they follow, who owns software and creative work, the licences that control how software can be used, and the effects of artificial intelligence.

Ethics and professional codes

Ethics are the moral principles that guide behaviour. Professional bodies publish codes of conduct so that members know what is expected of them, the public can trust them, and there is a standard against which bad practice can be judged.

The ACM/IEEE Software Engineering Code of Ethics

It sets out eight principles. Software engineers should act:

The BCS (the British Computer Society) code of conduct covers similar ground under four headings: the public interest, professional competence and integrity, duty to the relevant authority, and duty to the profession.

Copyright and ownership

Copyright gives the creator of an original work (program code, music, text, images) legal ownership of it. Copyright law makes it illegal to copy, modify, distribute or sell the work without the owner's permission.

• Why it is needed: creators invest time and money and need to be rewarded; it encourages innovation; it stops others profiting from work they didn't do.
• How software is protected: licence agreements, product keys or activation codes, online authentication, digital watermarks, and distributing only compiled code.
• Plagiarism: presenting someone else's work as your own, which is unethical even when it isn't illegal.

Software licences

Artificial intelligence and its impact

Artificial intelligence (AI) is the ability of a computer system to perform tasks that normally need human intelligence, such as recognising speech and images, making decisions, and learning from data.

Exam-style questions

A relational database stores data in linked tables so each fact is recorded once. You need the vocabulary, the skill of normalising a design to third normal form, and enough SQL to create tables and query them.

Why not just use files?

In a file-based system, each department or program keeps its own data files. This causes:

• Data redundancy: the same data is stored in several files, which wastes storage.
• Data inconsistency: when data changes in one file but not another, the copies disagree.
• Data dependence: programs are tied to the structure of their files, so changing a file's structure means changing every program that uses it.
• Poor security and sharing: it is hard to control who sees what, and hard to combine data from different files.

A relational database solves these by storing each item of data once, in linked tables, managed by a DBMS.

Relational database terms

Entity

Anything about which data is stored, such as a student or a book.

Table (relation)

A set of data about one type of entity, arranged in rows and columns.

Record (tuple)

One row of a table: the data about one instance of the entity.

Field (attribute)

One column of a table: one item of data about each entity.

Primary key

A field (or combination of fields) that uniquely identifies each record.

Candidate key

Any field or combination that could be chosen as the primary key.

Secondary key

A candidate key not chosen as the primary key, or a field indexed to allow fast searching.

Composite key

A primary key made of two or more fields.

Foreign key

A field in one table that is the primary key of another table, used to link the two.

Referential integrity

Every foreign key value must match an existing primary key value in the linked table. You can't add a loan for a member who doesn't exist, or delete a member who still has loans.

Indexing

A separate structure that stores key values and the location of each record, so records can be found quickly without reading the whole table.

Relationships and E-R diagrams

Relationships can be one-to-one (1:1), one-to-many (1:M) or many-to-many (M:M). A many-to-many relationship can't be built directly; it is resolved with a link table, which turns it into two one-to-many relationships.

Normalisation

Normalisation is the process of organising data into tables to remove redundancy and the problems it causes when inserting, updating or deleting data.

First normal form (1NF)

No repeating groups of attributes; every field holds a single (atomic) value; there is a primary key.

Second normal form (2NF)

In 1NF, and no partial dependencies: every non-key field depends on the whole primary key, not just part of a composite key. (A table with a single-field key that is in 1NF is automatically in 2NF.)

Third normal form (3NF)

In 2NF, and no non-key (transitive) dependencies: no non-key field depends on another non-key field.

Worked example

An unnormalised table records orders. One order can contain many products, so the product fields repeat:

ORDER(OrderNo, OrderDate, CustomerID, CustomerName, {ProductID, Description, UnitPrice, Quantity})

To 1NF: remove the repeating group so each row holds one product of one order. The primary key becomes the composite key OrderNo + ProductID.

ORDER(OrderNo, ProductID, OrderDate, CustomerID, CustomerName, Description, UnitPrice, Quantity)

To 2NF: look for fields that depend on only part of the key. OrderDate, CustomerID and CustomerName depend only on OrderNo. Description and UnitPrice depend only on ProductID. Only Quantity needs both.

ORDER(OrderNo, OrderDate, CustomerID, CustomerName)
PRODUCT(ProductID, Description, UnitPrice)
ORDER_LINE(OrderNo, ProductID, Quantity)

To 3NF: CustomerName depends on CustomerID, which is not the key of ORDER. Move it to its own table.

CUSTOMER(CustomerID, CustomerName)
ORDER(OrderNo, OrderDate, CustomerID*)
PRODUCT(ProductID, Description, UnitPrice)
ORDER_LINE(OrderNo*, ProductID*, Quantity)

Underlined fields are primary keys; * marks a foreign key.

Database Management Systems

A DBMS is software that controls access to the database and addresses the problems of file-based systems.

Data dictionary

Stores the metadata: the name of every table and field, data types, field sizes, validation rules, primary and foreign keys, relationships and access rights.

Data modelling

Tools for designing and analysing the structure of the data, such as E-R diagrams.

Logical schema

The overall design of the database, showing the tables, fields and relationships, independent of how the data is stored physically.

Data integrity

Enforces validation rules and referential integrity; manages concurrent access so two users don't overwrite each other's changes (record locking).

Data security

Usernames and passwords, access rights for different users, automatic backups, encryption, and audit trails.

Developer interface

Lets developers create and manipulate the database without writing everything in SQL, for example tools to build tables, forms and reports.

Query processor

Takes a query written in SQL (or built in a query-by-example interface), checks it, optimises it, and runs it on the database.

SQL: defining the database (DDL)

Data Definition Language creates and changes the structure of a database. Data types in the syllabus: CHARACTER, VARCHAR(n), BOOLEAN, INTEGER, REAL, DATE, TIME.

CREATE DATABASE Library;

CREATE TABLE MEMBER (
    MemberID   CHARACTER(5),
    FirstName  VARCHAR(30),
    LastName   VARCHAR(30),
    DateJoined DATE,
    PRIMARY KEY (MemberID)
);

CREATE TABLE LOAN (
    LoanID    INTEGER,
    MemberID  CHARACTER(5),
    BookID    CHARACTER(6),
    LoanDate  DATE,
    Returned  BOOLEAN,
    PRIMARY KEY (LoanID),
    FOREIGN KEY (MemberID) REFERENCES MEMBER(MemberID)
);

ALTER TABLE MEMBER ADD Email VARCHAR(60);
ALTER TABLE LOAN ADD FOREIGN KEY (BookID) REFERENCES BOOK(BookID);

SQL: querying and changing data (DML)

Data Manipulation Language adds, changes, deletes and retrieves the data.

-- Titles and prices of science books, cheapest first
SELECT Title, Price
FROM BOOK
WHERE Genre = 'Science' AND Price < 20
ORDER BY Price ASC;

-- How many books in each genre
SELECT Genre, COUNT(BookID)
FROM BOOK
GROUP BY Genre;

-- Total value and average price of all books
SELECT SUM(Price), AVG(Price) FROM BOOK;

-- Names of members with a book not yet returned, with the book title
SELECT MEMBER.FirstName, MEMBER.LastName, BOOK.Title
FROM MEMBER
INNER JOIN LOAN ON MEMBER.MemberID = LOAN.MemberID
INNER JOIN BOOK ON LOAN.BookID = BOOK.BookID
WHERE LOAN.Returned = FALSE;

INSERT INTO MEMBER (MemberID, FirstName, LastName, DateJoined)
VALUES ('M0042', 'Sara', 'Khan', '2026-09-01');

UPDATE BOOK SET Price = 12.50 WHERE BookID = 'B00123';

DELETE FROM LOAN WHERE Returned = TRUE;

Exam-style questions

CREATE TABLE BOOK (
    BookID  CHARACTER(6),
    Title   VARCHAR(50),
    Author  VARCHAR(40),
    Genre   VARCHAR(20),
    Price   REAL,
    PRIMARY KEY (BookID)
);

SELECT Title, Author
FROM BOOK
WHERE Author = 'R Ahmed'
ORDER BY Title;

SELECT MemberID, COUNT(LoanID)
FROM LOAN
GROUP BY MemberID;

Before writing code you need a clear plan. This topic covers the thinking skills used to break a problem down, and the three ways of writing an algorithm that Paper 2 expects: structured English, flowcharts and pseudocode.

Computational thinking

Abstraction

Removing unnecessary detail and keeping only what is essential to solve the problem. A metro map is an abstraction: it shows stations and connections but not exact distances or streets.

Decomposition

Breaking a complex problem into smaller sub-problems that are easier to understand and solve. Each sub-problem can become a module (procedure or function).

Benefits of abstraction: it reduces complexity, so the solution is quicker to design and program; the program is smaller and needs less memory; and the design focuses on what the user actually needs. Benefits of decomposition: modules can be written by different people at the same time, tested separately, and reused in other programs.

What an algorithm is

An algorithm is a solution to a problem expressed as a sequence of clearly defined steps. Every algorithm is built from three basic constructs: sequence (steps in order), selection (choosing a path with IF or CASE) and iteration (repeating with a loop).

Identifier tables

Before writing pseudocode, list every variable you'll need. Exam questions often ask you to complete one.

One algorithm, three ways

Problem: input 10 integers and output the largest.

Structured English

A restricted form of English using short, numbered statements and command words.

1. INPUT the first number and store it as the largest so far
2. REPEAT 9 times
     INPUT a number
     IF the number is greater than the largest so far
        THEN store it as the largest so far
3. OUTPUT the largest

Flowchart

Pseudocode

DECLARE Num, Max, Count : INTEGER
INPUT Num
Max ← Num
FOR Count ← 2 TO 10
    INPUT Num
    IF Num > Max THEN
        Max ← Num
    ENDIF
NEXT Count
OUTPUT "The largest number is ", Max

Stepwise refinement

Stepwise refinement means taking each step of an outline algorithm and breaking it into more detailed steps, repeatedly, until each step can be written directly as a line of code. It is decomposition applied to the algorithm itself.

1. Get valid marks for 30 students
   1.1 FOR each of 30 students
       1.1.1 INPUT a mark
       1.1.2 WHILE the mark is not between 0 and 100
             OUTPUT an error message and INPUT the mark again
       1.1.3 Add the mark to the total
2. Calculate the average
   2.1 Average = total / 30
3. Output the average, rounded to 1 decimal place

Exam-style questions

DECLARE Temp, Highest, Lowest, Total : REAL
DECLARE Day : INTEGER
INPUT Temp
Highest ← Temp
Lowest ← Temp
Total ← Temp
FOR Day ← 2 TO 30
    INPUT Temp
    IF Temp > Highest THEN
        Highest ← Temp
    ENDIF
    IF Temp < Lowest THEN
        Lowest ← Temp
    ENDIF
    Total ← Total + Temp
NEXT Day
OUTPUT "Highest: ", Highest
OUTPUT "Lowest: ", Lowest
OUTPUT "Average: ", Total / 30

1. Set the count of passes to zero
2. Repeat for each of 25 students:
     input the student's mark
     if the mark is 40 or more, add 1 to the count of passes
3. Output the count of passes and the percentage of students who passed

DECLARE Passes, Student, Mark : INTEGER
Passes ← 0
FOR Student ← 1 TO 25
    INPUT Mark
    IF Mark >= 40 THEN
        Passes ← Passes + 1
    ENDIF
NEXT Student
OUTPUT "Passes: ", Passes
OUTPUT "Percentage passed: ", Passes / 25 * 100

Choosing the right way to store data makes an algorithm simpler. This topic covers the basic data types, records, arrays, text files and three abstract data types: the stack, the queue and the linked list.

Data types

Records

A record is a composite, user-defined data type that groups related items of data, possibly of different types, under one identifier. Each item is a field.

TYPE StudentRecord
    DECLARE StudentID : STRING
    DECLARE Name : STRING
    DECLARE Mark : INTEGER
    DECLARE Paid : BOOLEAN
ENDTYPE

DECLARE Student : StudentRecord
Student.Name ← "Hira"
Student.Mark ← 78

// An array of records stores a whole class
DECLARE Class : ARRAY[1:30] OF StudentRecord
Class[1].Mark ← 65

Arrays

An array is a fixed-size, ordered collection of elements of the same data type, accessed by an index. The lower bound and upper bound are the first and last index values.

DECLARE Scores : ARRAY[1:10] OF INTEGER          // 1D: 10 elements
DECLARE Board : ARRAY[1:3, 1:3] OF CHAR          // 2D: 3 rows × 3 columns
DECLARE Row, Col : INTEGER

FOR Row ← 1 TO 3                                 // nested loops visit every element
    FOR Col ← 1 TO 3
        Board[Row, Col] ← ' '
    NEXT Col
NEXT Row

Linear search

Check each element in turn from the start until the item is found or the end is reached. It works on unsorted data.

DECLARE Index : INTEGER
DECLARE Found : BOOLEAN
Found ← FALSE
Index ← 1
WHILE Index <= 100 AND Found = FALSE
    IF Names[Index] = SearchName THEN
        Found ← TRUE
    ELSE
        Index ← Index + 1
    ENDIF
ENDWHILE
IF Found = TRUE THEN
    OUTPUT "Found at position ", Index
ELSE
    OUTPUT "Not found"
ENDIF

Bubble sort

Compare each pair of neighbouring elements and swap them if they are in the wrong order. After each pass the largest remaining value has "bubbled" to the end, so the next pass can stop one place earlier. A flag records whether any swap happened; if a pass makes no swaps, the array is sorted and the algorithm stops early.

DECLARE Top, J, Temp : INTEGER
DECLARE Swapped : BOOLEAN
Top ← 9                                  // array Numbers[1:10]
REPEAT
    Swapped ← FALSE
    FOR J ← 1 TO Top
        IF Numbers[J] > Numbers[J + 1] THEN
            Temp ← Numbers[J]
            Numbers[J] ← Numbers[J + 1]
            Numbers[J + 1] ← Temp
            Swapped ← TRUE
        ENDIF
    NEXT J
    Top ← Top - 1
UNTIL Swapped = FALSE OR Top = 0

Text files

Data in variables is lost when a program ends. Files store data permanently in secondary storage so it can be used again later or by another program.

// Write (creates the file, or overwrites an existing one)
OPENFILE "Scores.txt" FOR WRITE
WRITEFILE "Scores.txt", "Ali,72"
CLOSEFILE "Scores.txt"

// Append (adds to the end of an existing file)
OPENFILE "Scores.txt" FOR APPEND
WRITEFILE "Scores.txt", "Bina,85"
CLOSEFILE "Scores.txt"

// Read every line until the end of the file
DECLARE Line : STRING
OPENFILE "Scores.txt" FOR READ
WHILE NOT EOF("Scores.txt")
    READFILE "Scores.txt", Line
    OUTPUT Line
ENDWHILE
CLOSEFILE "Scores.txt"

Abstract data types

An abstract data type (ADT) is a collection of data together with a set of operations on that data, described by what it does rather than how it is implemented. At AS you need to know three, and how each can be built from an array and pointers.

Stack (last in, first out)

Items are added (pushed) and removed (popped) at the same end, the top. Uses: storing return addresses when subroutines are called, undo features, backtracking, evaluating expressions.

PROCEDURE Push(NewItem : INTEGER)
    IF TopPointer = 6 THEN
        OUTPUT "Stack full"
    ELSE
        TopPointer ← TopPointer + 1
        Stack[TopPointer] ← NewItem
    ENDIF
ENDPROCEDURE

FUNCTION Pop() RETURNS INTEGER
    DECLARE Item : INTEGER
    IF TopPointer = 0 THEN
        OUTPUT "Stack empty"
        RETURN -1
    ELSE
        Item ← Stack[TopPointer]
        TopPointer ← TopPointer - 1
        RETURN Item
    ENDIF
ENDFUNCTION

Queue (first in, first out)

Items join at the rear and leave from the front. Uses: print queues, keyboard buffers, scheduling processes. In a circular queue, when the rear pointer reaches the end of the array it wraps round to the start, so spaces freed at the front are reused.

Linked list

Each node holds data and a pointer to the next node. A start pointer gives the first node, and the last node has a null pointer. Items can be kept in order without moving data around: inserting or deleting only changes pointers. Unused nodes are kept in a free list with its own heap (free) pointer.

Exam-style questions

TYPE MemberRecord
    DECLARE MemberNo : STRING
    DECLARE Phone : STRING
    DECLARE DateJoined : DATE
    DECLARE MonthlyFee : REAL
    DECLARE Paid : BOOLEAN
ENDTYPE

DECLARE Members : ARRAY[1:200] OF MemberRecord
Members[1].MonthlyFee ← 3500

FUNCTION FindItem(ItemName : STRING) RETURNS INTEGER
    DECLARE Index : INTEGER
    Index ← 1
    WHILE Index <= 50
        IF Stock[Index] = ItemName THEN
            RETURN Index
        ENDIF
        Index ← Index + 1
    ENDWHILE
    RETURN -1
ENDFUNCTION

DECLARE Name : STRING
DECLARE Count : INTEGER
Count ← 0
OPENFILE "Names.txt" FOR READ
WHILE NOT EOF("Names.txt")
    READFILE "Names.txt", Name
    IF TO_UPPER(LEFT(Name, 1)) = "A" THEN
        Count ← Count + 1
    ENDIF
ENDWHILE
CLOSEFILE "Names.txt"
OUTPUT Count, " names begin with A"

Paper 2 is written in Cambridge pseudocode. Exact syntax matters less than clear logic, but using the standard keywords makes your answers easy to mark. This page is your reference for the syntax and the built-in functions.

Variables, constants and assignment

DECLARE Total : INTEGER
DECLARE Price, Discount : REAL
DECLARE Name : STRING
CONSTANT VAT = 0.17                // a constant can't change while the program runs

Total ← 0                          // assignment uses the arrow ←
INPUT Name
OUTPUT "Hello ", Name              // OUTPUT can take several items

Use a constant for a value that never changes during the run (a tax rate, the size of an array). If the value must change one day, it only needs editing in one place, and the program is easier to read.

Operators

A common use of MOD: N MOD 2 = 0 tests whether N is even. N MOD 10 gives the last digit and N DIV 10 removes it.

Built-in functions

Your exam paper comes with an insert listing the functions you may use. The common ones:

Older papers use UCASE and LCASE instead of TO_UPPER and TO_LOWER. Use whichever your paper's insert lists.

Selection

IF Mark >= 50 THEN
    OUTPUT "Pass"
ELSE
    IF Mark >= 40 THEN
        OUTPUT "Resit"
    ELSE
        OUTPUT "Fail"
    ENDIF
ENDIF

CASE OF Choice
    1 : CALL AddRecord()
    2 : CALL DeleteRecord()
    3 TO 5 : OUTPUT "Coming soon"
    OTHERWISE : OUTPUT "Invalid choice"
ENDCASE

Use CASE when one variable is checked against several specific values or ranges; it is neater than many nested IFs.

Iteration

FOR Count ← 10 TO 0 STEP -2        // 10, 8, 6, 4, 2, 0
    OUTPUT Count
NEXT Count

REPEAT                              // validation: always asks at least once
    OUTPUT "Enter a mark from 0 to 100"
    INPUT Mark
UNTIL Mark >= 0 AND Mark <= 100

WHILE Password <> "letmein" AND Attempts < 3
    INPUT Password
    Attempts ← Attempts + 1
ENDWHILE

Procedures and functions

A procedure performs a task. A function performs a task and returns a single value, so it is used inside an expression.

PROCEDURE ShowLine(Symbol : CHAR, Length : INTEGER)
    DECLARE Line : STRING
    DECLARE I : INTEGER
    Line ← ""
    FOR I ← 1 TO Length
        Line ← Line & Symbol
    NEXT I
    OUTPUT Line
ENDPROCEDURE

FUNCTION Area(Width : REAL, Height : REAL) RETURNS REAL
    RETURN Width * Height
ENDFUNCTION

CALL ShowLine('*', 20)               // a procedure is CALLed
Total ← Area(3.5, 2) + Area(1, 1)    // a function is used in an expression

Parameters by value and by reference

BYVAL

A copy of the value is passed. Changes inside the subroutine do not affect the original variable. This is the default.

BYREF

The address (a reference to the original variable) is passed. Changes inside the subroutine change the original.

PROCEDURE Swap(BYREF X : INTEGER, BYREF Y : INTEGER)
    DECLARE Temp : INTEGER
    Temp ← X
    X ← Y
    Y ← Temp
ENDPROCEDURE

Local and global variables

A global variable is declared in the main program and can be used anywhere. A local variable is declared inside a subroutine and exists only while it runs. Prefer local variables: modules are independent, easier to test and reuse, and can't accidentally change data elsewhere.

Why use subroutines?

• The program is split into manageable, named modules that are easier to understand.
• Code is written once and called many times, so programs are shorter.
• Each module can be tested on its own and reused in other programs.
• Several programmers can work on different modules at the same time.

Exam-style questions

FUNCTION CountVowels(ThisString : STRING) RETURNS INTEGER
    DECLARE Count, Index : INTEGER
    DECLARE ThisChar : CHAR
    Count ← 0
    FOR Index ← 1 TO LENGTH(ThisString)
        ThisChar ← TO_LOWER(MID(ThisString, Index, 1))
        IF ThisChar = 'a' OR ThisChar = 'e' OR ThisChar = 'i' OR ThisChar = 'o' OR ThisChar = 'u' THEN
            Count ← Count + 1
        ENDIF
    NEXT Index
    RETURN Count
ENDFUNCTION

FUNCTION ValidPassword(Pwd : STRING) RETURNS BOOLEAN
    DECLARE Index : INTEGER
    DECLARE HasDigit, HasUpper : BOOLEAN
    DECLARE C : CHAR
    IF LENGTH(Pwd) < 8 THEN
        RETURN FALSE
    ENDIF
    HasDigit ← FALSE
    HasUpper ← FALSE
    FOR Index ← 1 TO LENGTH(Pwd)
        C ← MID(Pwd, Index, 1)
        IF C >= '0' AND C <= '9' THEN
            HasDigit ← TRUE
        ENDIF
        IF C >= 'A' AND C <= 'Z' THEN
            HasUpper ← TRUE
        ENDIF
    NEXT Index
    RETURN HasDigit AND HasUpper
ENDFUNCTION

DECLARE N, Result, Digit : INTEGER
N ← 2547
Result ← 0
WHILE N > 0
    Digit ← N MOD 10
    Result ← Result * 10 + Digit
    N ← N DIV 10
ENDWHILE
OUTPUT Result

Real software is planned, designed, built, tested and then maintained for years. This topic covers the stages of that life cycle, the design diagrams Paper 2 uses, and how to choose test data that catches errors.

The program development life cycle

Analysis

Investigate the problem and the current system; identify the requirements with the client (a requirements specification); use abstraction and decomposition.

Design

Plan the solution: structure charts, algorithms (pseudocode, flowcharts), data structures, interface designs, and the test plan.

Coding

Write the program in a programming language, module by module, with iterative testing along the way.

Testing

Run the program with test data to find and remove errors and check it meets the requirements.

Maintenance

After the program is in use: fix errors that appear, adapt it to new needs, and improve it.

Life cycle models

Structure charts

A structure chart shows how a problem is decomposed into modules, arranged as a hierarchy, and the parameters passed between them.

State-transition diagrams

A state-transition diagram shows the states a system can be in, the events (inputs) that cause a change of state, and the transitions between them. The arrow coming from nowhere marks the start state.

Types of error

Syntax error

Breaks the rules of the programming language, such as a misspelt keyword or missing bracket. The translator reports it and the program won't run.

Logic error

The program runs but gives the wrong result because the algorithm is wrong, such as using < instead of <=, or the wrong loop bounds.

Run-time error

Occurs while the program is running and makes it crash, such as dividing by zero, an array index out of range, or opening a file that doesn't exist.

Testing methods

Dry run

Working through an algorithm by hand, recording variable values in a trace table, to check the logic without a computer.

Walkthrough

The programmer explains the code step by step to colleagues, who look for errors.

White-box testing

The tester knows the code and chooses data to test every path through it.

Black-box testing

The code is not looked at; the inputs are tested only against the expected outputs from the specification.

Integration testing

Modules that have been tested separately are combined and tested together, to check they work with each other.

Stub testing

A module that hasn't been written yet is replaced by a simple stub, such as one that just outputs a message or returns a fixed value, so the rest of the program can be tested.

Alpha testing

Carried out in-house by the developers or a test team, before release to users.

Beta testing

A nearly finished version is given to a group of real users outside the company, who report faults.

Acceptance testing

The finished program is tested by the client to check it meets the agreed requirements before it is handed over.

Test data

For an input that must be a whole number from 1 to 100:

A test plan lists each test, the purpose, the test data, the expected result, and (after testing) the actual result.

Maintenance

Corrective

Fixing errors (bugs) found after the program has been released.

Adaptive

Changing the program to meet new requirements or to work in a changed environment, such as new laws, a new operating system or new hardware.

Perfective

Improving the program's performance or usability, even though it already works correctly, such as making it faster or improving the interface.

Exam-style questions

Papers 1 and 2 count for the other 50% of the full A Level, so keep revising the AS topics too: Paper 3 often builds on them.

Topics

How to revise with these notes

• Practise the calculations by hand. Floating point, Boolean simplification, K-maps, RPN and Dijkstra all appear as worked problems. The tools on those pages let you check your working.
• Type the code. For Paper 4, run every Python example yourself and change it. Reading code is not the same as writing it under time pressure.
• Learn the sequences. The TLS handshake, digital signatures and the stages of compilation are frequently asked as ordered descriptions. Get the order right.

This topic extends AS data representation in three directions: designing your own data types, organising files so records can be found quickly, and storing real numbers in floating-point binary.

User-defined data types

Built-in types (INTEGER, STRING …) cannot describe everything a program needs. A user-defined data type is created by the programmer to match the data in the problem, making programs easier to read and helping the translator catch errors.

Non-composite types

A non-composite type is defined without referring to another data type.

// Enumerated: an ordered list of all possible values
TYPE Season = (Spring, Summer, Autumn, Winter)
DECLARE ThisSeason : Season
ThisSeason ← Autumn
IF ThisSeason > Summer THEN          // values have an order
    OUTPUT "Second half of the year"
ENDIF

// Pointer: holds the memory address of a variable of a given type
TYPE TIntPointer = ^INTEGER
DECLARE MyPointer : TIntPointer
DECLARE Number, Copy : INTEGER
Number ← 42
MyPointer ← @Number                  // @ gives the address of Number
Copy ← MyPointer^                    // ^ dereferences: Copy becomes 42
MyPointer^ ← 7                       // changes Number to 7

Composite types

A composite type is made up of other data types.

Record

A collection of related fields of possibly different types (see topic 10).

Set

An unordered collection of distinct values of the same type, supporting set operations: membership (is an item in the set?), union, intersection and difference.

Class

A blueprint for objects, combining attributes (data) and methods (procedures and functions) that act on them (see topic 20).

TYPE LetterSet = SET OF CHAR
DEFINE Vowels ('A', 'E', 'I', 'O', 'U') : LetterSet

File organisation and access

Sequential access

Records are read one after another from the start until the required record is found. Used with serial and sequential files. For a sequential file the search can stop early once the key passes the one being looked for.

Direct access

The record's address is calculated (by hashing the key, or by using an index) and the record is read immediately without reading the others. Used with random files, and with sequential files that have an index.

Hashing

A hashing algorithm calculates a storage address from a record's key, for example Address ← Key MOD 7 for a file with 7 slots. A collision happens when two keys give the same address. Two ways to deal with it:

• Open hashing (linear probing): store the record in the next free slot after the calculated one, wrapping round at the end.
• Overflow area: store the record in a separate overflow area, searched serially when the record isn't at its home address.

To find a record, calculate the hash, then check that slot; if it holds a different key, check the following slots (or the overflow area) until the record or an empty slot is found.

Notice the cluster forming around slot 3. A good hash function spreads keys evenly, and the file should be larger than the number of records so collisions stay rare.

Floating-point representation

A real number is stored as a mantissa and an exponent, both in two's complement:

value = mantissa × 2^exponent

The binary point is assumed to sit just after the first (sign) bit of the mantissa. With an 8-bit mantissa the place values are −1, ½, ¼, ⅛, 1⁄16, 1⁄32, 1⁄64, 1⁄128.

Binary floating point to denary

Another way: move the binary point right by the exponent. 0.1011000 with the point moved 3 places gives 0101.1000 = 5.5. For a negative exponent, move the point left.

Denary to normalised floating point

Example: −6.5 with an 8-bit mantissa and 4-bit exponent.

1. Write +6.5 in binary: 110.1
2. Move the point so the number starts 0.1: 0.1101 × 2³. The exponent is 3 = 0011.
3. Write the positive mantissa in 8 bits: 0.1101000
4. For a negative number, take the two's complement: flip the bits (1.0010111) and add 1, giving 1.0011000
5. Check: −1 + ⅛ + 1⁄16 = −0.8125, and −0.8125 × 8 = −6.5 ✓

Normalisation

A normalised positive mantissa starts 0.1; a normalised negative mantissa starts 1.0. In other words, the first two bits differ. To normalise, shift the mantissa left until they differ, and subtract 1 from the exponent for each place shifted.

Why normalise? It gives the maximum precision for the number of mantissa bits, because no bits are wasted on leading 0s (or 1s). It also means each value has exactly one representation.

Precision, range and errors

• More mantissa bits means greater precision (more significant figures). More exponent bits means a greater range (larger and smaller magnitudes). With a fixed total, increasing one reduces the other.
• Many denary fractions, such as 0.1, have no exact binary representation; they recur, like ⅓ in denary. The stored value is only an approximation, which causes rounding errors that can build up over many calculations.
• Overflow happens when a result is too large to represent: the exponent needed is bigger than the largest the exponent bits allow.
• Underflow happens when a result is too close to zero to represent: the exponent needed is more negative than allowed, so the value becomes 0.

With an 8-bit mantissa and 4-bit exponent, the largest positive value is 0.1111111 × 2⁷ = 127, the most negative is 1.0000000 × 2⁷ = −128, and the smallest positive normalised value is 0.1000000 × 2⁻⁸ = 1⁄512.

Exam-style questions

In questions 1 to 3, the mantissa has 8 bits and the exponent has 4 bits, both in two's complement.

A protocol is a set of rules that devices agree on so they can communicate. This topic covers the TCP/IP protocol suite, the main application protocols, peer-to-peer file sharing with BitTorrent, and the two ways data can travel across a network.

Why protocols are needed

Devices from different manufacturers, running different software, must agree on things like the format of data, how it is addressed, error checking, and how fast it is sent. Protocols set these rules. Splitting the job into layers means each layer deals with one part of the job and only talks to the layers directly above and below; a layer can be changed (say, Wi-Fi replaced by Ethernet) without changing the others.

The TCP/IP protocol suite

Application protocols

HTTP

HyperText Transfer Protocol. The browser sends requests (such as GET or POST) to a web server, which returns web pages and other resources. HTTPS is HTTP made secure with TLS.

FTP

File Transfer Protocol. Uploads and downloads files between a client and a server, often with a login; supports listing, renaming and deleting files on the server.

SMTP

Simple Mail Transfer Protocol. A push protocol: sends email from the client to the sender's mail server, and between mail servers.

POP3

Post Office Protocol 3. A pull protocol: downloads email from the server to one device, and usually deletes it from the server. Mail is then available offline but not synchronised across devices.

IMAP

Internet Message Access Protocol. A pull protocol that keeps email on the server and synchronises it, so the same mailbox, folders and read status appear on every device.

BitTorrent

BitTorrent is a peer-to-peer protocol for sharing large files without one central server doing all the work.

1. The file is split into many small, equal-sized pieces, each with a hash so it can be checked.
2. A small .torrent file holds metadata: the file name and size, the piece hashes, and the address of a tracker.
3. A user's BitTorrent client contacts the tracker, which keeps a list of the peers currently sharing that file (the swarm).
4. The client downloads different pieces from many peers at the same time, checks each piece against its hash, and reassembles the file.
5. As soon as it has a piece, it also uploads that piece to other peers. A seed has the complete file; a leech downloads without uploading much in return.

Benefits: fast downloads for popular files, since there are many sources; no single server is overloaded or a single point of failure. Drawbacks: availability depends on enough seeds being online; it is widely used to share copyrighted material illegally; downloaded files can carry malware.

Circuit switching and packet switching

Circuit switching

A dedicated path (circuit) between sender and receiver is set up before any data is sent. All data follows that path, arrives in order, and the circuit is reserved for the whole communication, then released. Traditional landline telephone calls work this way.

Packet switching

The message is split into packets. Each packet has a header containing the source and destination addresses and a sequence number. Packets travel independently and may take different routes, chosen by routers; they are reassembled in order at the destination. The links are shared with other users' traffic. The internet works this way.

The role of a router in packet switching

A router reads the destination IP address in each packet's header, looks up its routing table to choose the best next hop towards that destination (taking into account traffic and faults), and forwards the packet. Routers exchange information so their tables stay up to date, which is how packets can be rerouted around problems.

Exam-style questions

How processor design affects speed, how many processors can share a job, how one machine can pretend to be another, and the algebra used to simplify and build logic circuits, including the adders and flip-flops inside every CPU.

RISC and CISC

Pipelining

Pipelining is instruction-level parallelism: the fetch-execute cycle is split into stages, and different instructions are at different stages at the same time, like an assembly line. A common five-stage pipeline is: Instruction Fetch (IF), Instruction Decode (ID), Operand Fetch (OF), Instruction Execute (IE), Write Back (WB).

Without pipelining, 4 instructions take 4 × 5 = 20 cycles. With a 5-stage pipeline they take 5 + 3 = 8 cycles: once the pipeline is full, one instruction completes every cycle.

Interrupts in a pipelined processor

When an interrupt occurs, several instructions are partly processed. Either the pipeline is flushed (the partly processed instructions are discarded, except the one in its final stage, which completes) and the normal interrupt routine runs, then the discarded instructions are fetched again later; or the processor keeps a separate program counter for each stage, so the state of every instruction in the pipeline can be saved and restored.

Parallel processing

Flynn's taxonomy classifies computer architectures by the number of instruction streams and data streams.

Massively parallel computers

A massively parallel computer has a very large number of processors (thousands or more), each usually with its own memory, linked by a high-speed interconnection network. A big problem is split into many parts that are processed simultaneously, with the processors communicating to combine results. Used for weather forecasting, scientific simulation and training AI models. The software must be specially written so the problem can be split up; some tasks cannot be parallelised.

Virtual machines

A virtual machine (VM) is software that emulates a complete computer system. A guest operating system runs inside the VM, on top of the host computer and its OS, managed by software called a hypervisor. The Java Virtual Machine is a process VM: it emulates a machine that runs Java bytecode on any host.

• Benefits: several different operating systems can run on one physical computer; software can be tested on different platforms without buying hardware; each VM is isolated, so a crash or malware in the guest doesn't affect the host; old (legacy) software can run on new hardware; servers can be consolidated, saving cost and energy.
• Drawbacks: the guest runs more slowly than it would on real hardware, because of the extra layer of emulation; it needs a powerful host with lots of memory; it is complex to set up and manage; if the host fails, every VM on it fails.

Boolean algebra

A bar over a term means NOT. A dot means AND and a plus means OR, so A.B + C means (A AND NOT B) OR C.

De Morgan's laws in words: to break a bar, change the operator under it (AND becomes OR, OR becomes AND) and put a bar over each term.

Worked simplification

Try typing (A AND B) OR (B AND C) into the builder: the output column is identical, which proves the simplification.

Karnaugh maps

A K-map is a grid version of a truth table, laid out so that neighbouring cells differ in exactly one variable (the column labels use Gray code: 00, 01, 11, 10). Grouping adjacent 1s removes the variable that changes within the group.

Rules for grouping

• Groups contain only 1s, and must be rectangles of 1, 2, 4, 8 or 16 cells.
• Make each group as large as possible, and use as few groups as possible.
• Groups may overlap, and may wrap around the edges (the left and right edges are adjacent, as are the top and bottom).
• For each group, keep only the variables that stay the same throughout it.

Example: X is 1 for the inputs ABC = 001, 011, 101, 110, 111.

The group of four (outlined in the accent colour) has C = 1 throughout, while A and B change, so it gives C. The pair (outlined in red) has A = 1 and B = 1, while C changes, so it gives A.B. The result is X = C + A.B.

Benefits of K-maps: simplification is quicker and less error-prone than algebra, and they guarantee the minimum sum-of-products expression when grouped correctly.

Adders

Half adder

Adds two bits, A and B, giving a sum bit S and a carry bit C: S = A XOR B, C = A AND B.

Full adder

Adds three bits: A, B and a carry-in C_in from the previous column. It is built from two half adders and an OR gate: the first half adder adds A and B; the second adds that sum to C_in; the two carry outputs are ORed to give C_out. Chaining full adders adds multi-bit numbers.

S = A XOR B XOR Cin   Cout = A.B + Cin.(A XOR B)

Flip-flops

A flip-flop is a circuit with two stable states, so it can store one bit. Its output depends on its inputs and its previous state (it is sequential, not combinational). Flip-flops are the storage elements in registers and in SRAM.

SR flip-flop

Built from two cross-coupled NOR gates (or NAND gates): each gate's output feeds back into the other's input.

JK flip-flop

A JK flip-flop adds a clock input, so the state only changes on a clock pulse (synchronised with the rest of the circuit), and it removes the invalid state: when J = K = 1, the output toggles.

Exam-style questions

At A Level you need to know how the operating system shares the processor and memory between many processes, and what happens inside a compiler, including how grammars are defined and how expressions are evaluated with Reverse Polish Notation.

What the OS is for

The operating system aims to make the best use of the computer's resources (processor, memory, storage, I/O devices) and to provide a user interface that hides the complexity of the hardware, through a GUI or command line and through system calls (APIs) that programs use instead of controlling hardware directly.

The kernel is the core of the OS. It stays in memory and manages processes, memory, interrupts and device drivers.

Process management

A process is a program that has started executing. Multitasking means several processes appear to run at the same time: the scheduler switches the processor between them so quickly that each makes progress.

Running

The process is being executed by the processor. Only one process per core can be running.

Ready

The process could run and is waiting in the ready queue for processor time.

Blocked

The process is waiting for an event, such as input/output to finish. It can't use the processor even if it is free.

A blocked process can't go straight to running: when its event completes it goes back to ready and must wait to be scheduled. A ready process can't become blocked, because only a running process can request I/O.

Scheduling

The low-level scheduler decides which ready process gets the processor next. A pre-emptive algorithm can stop a running process to give the processor to another; a non-pre-emptive one lets each process run until it finishes or blocks.

Worked example: P1 needs 5 time units, P2 needs 3 and P3 needs 1. All arrive at time 0, in that order.

Waiting time = finish time − burst time (since all arrive at 0). In RR, P3 finishes at 5, P2 at 8 and P1 at 9.

Interrupt handling

When an interrupt arrives, the OS saves the state of the current process (its registers, in its process control block), identifies the interrupt source, runs the correct interrupt service routine, then the scheduler decides which process runs next, which may not be the one that was interrupted.

Memory management

Paging

Logical memory (the program) is divided into fixed-size pages, and physical memory into frames of the same size. Pages can be placed in any free frames, not necessarily together. A page table maps each page number to its frame. Space at the end of the last page may be wasted (internal fragmentation).

Segmentation

The program is divided into variable-size segments that match its logical parts (such as a procedure or a block of data). A segment table holds each segment's base address and length. Free memory can be left in gaps too small to use (external fragmentation).

Virtual memory

Secondary storage is used as if it were extra RAM. Only the pages currently needed are kept in RAM; others are held on disk and swapped in when required. This lets programs larger than RAM run, and lets more programs be open at once.

Disk thrashing

When RAM is too full, pages are swapped in and out so often that the computer spends more time moving pages than executing instructions, and performance drops sharply. The point where this starts is the thrash point.

Page replacement

When a new page is needed and RAM is full, the OS chooses a page to swap out, for example the one that has been in memory longest (first in, first out) or the one used least recently (LRU).

How an interpreter runs a program

An interpreter doesn't produce a translated version. It reads each statement of the source code, analyses it (checks the syntax and works out what it means), then executes it immediately by calling its own pre-written, already-compiled routines that carry out that kind of statement. It then moves on to the next statement, so a statement inside a loop is analysed again each time.

The stages of compilation

1. Lexical analysis

Removes whitespace and comments. Splits the source code into tokens (keywords, identifiers, operators, literals). Keywords are looked up in a keyword table; identifiers are added to the symbol table with information such as their data type and address.

2. Syntax analysis

Parses the token stream, checking it against the grammar rules of the language. Builds a parse tree and reports syntax errors.

3. Code generation

Produces object code (machine code or an intermediate code) from the parse tree.

4. Optimisation

Improves the object code so it runs faster or uses less memory, without changing what it does: removing redundant or unreachable code, moving calculations that don't change out of loops, replacing a constant expression such as 60 * 60 with its value.

Grammars: BNF and syntax diagrams

Backus-Naur Form defines the rules (syntax) of a language. ::= means "is defined as", | means "or", and items in angle brackets are non-terminals (defined by other rules). Recursion lets a rule repeat.

<digit>      ::= 0|1|2|3|4|5|6|7|8|9
<letter>     ::= A|B|C| … |Z
<identifier> ::= <letter> | <identifier><letter> | <identifier><digit>

So an identifier is a letter followed by any number of letters and digits: A, X2 and TOTAL9 are valid; 9X is not. The same rule as a syntax diagram:

Reverse Polish Notation

In Reverse Polish Notation (RPN) each operator comes after its operands: a + b becomes a b +. RPN needs no brackets and no precedence rules, so a computer can evaluate it in one left-to-right pass with a stack. Compilers convert expressions to RPN for this reason.

• To evaluate RPN: read tokens left to right. Push each operand onto the stack. For an operator, pop the top two values, apply the operator (the first popped is the right-hand operand), and push the result. At the end, the stack holds the answer.
• Infix to RPN: (a + b) * (c − d) becomes a b + c d − *. Draw an expression tree and read it in post-order (left, right, root), or use the converter below.

Exam-style questions

<digit>  ::= 0|1|2|3|4|5|6|7|8|9
<letter> ::= A|B|C|D
<code>   ::= <letter><digit> | <letter><code>

Encryption keeps data confidential, and the same key mathematics also proves who sent a message and that it hasn't been changed. Learn the purpose of each key, then the TLS handshake and the digital signature process in order.

Encryption terms

Plaintext

The original, readable data.

Ciphertext

The encrypted data, which can't be understood without the key.

Encryption algorithm

The method (cipher) used with a key to turn plaintext into ciphertext, and back.

Key

A value used by the algorithm. Longer keys mean far more possible keys, so a brute-force attack takes much longer.

Encryption does not stop data being intercepted; it stops intercepted data being understood.

Symmetric and asymmetric encryption

Which key does what?

• For confidentiality: the sender encrypts with the recipient's public key. Only the recipient's private key can decrypt it, so only the intended recipient can read the message.
• For authentication (signatures): the sender encrypts with their own private key. Anyone can decrypt with the sender's public key, which proves it came from the owner of the private key.

Quantum cryptography

Quantum cryptography uses the properties of photons (particles of light) to exchange an encryption key securely, a process called quantum key distribution. Each bit is sent as a photon with a particular polarisation. Measuring a photon changes its state, so if an eavesdropper intercepts the key, errors appear and both parties know the key has been compromised.

• Benefits: eavesdropping can always be detected; keys are effectively unbreakable by computation; very long keys can be exchanged; it remains secure against future quantum computers.
• Drawbacks: needs expensive specialist hardware and dedicated fibre-optic links; the distance a key can be sent is limited because photons are lost or their polarisation changes in the cable; the rate of key exchange is relatively low.

SSL and TLS

TLS (Transport Layer Security), the successor to SSL, provides secure communication between a client and a server. It gives encryption (privacy), authentication (the server is who it claims to be) and data integrity (data hasn't been altered). TLS is made of two layers: the handshake protocol, which sets up the secure session, and the record protocol, which encrypts the data sent during it. It is used in HTTPS, email, VoIP and online banking.

The TLS handshake

1. The client (browser) sends a message to the server requesting a secure connection, listing the TLS versions and encryption algorithms (cipher suites) it supports.
2. The server replies with the version and cipher suite it has chosen, and sends its digital certificate, which contains its public key.
3. The client checks that the certificate is valid and was signed by a trusted Certificate Authority.
4. The client and server establish a shared session key: for example, the client generates one, encrypts it with the server's public key and sends it; only the server can decrypt it with its private key.
5. Both sides now use the symmetric session key to encrypt all data for the rest of the session (the record protocol). The session key is discarded when the session ends.

Digital certificates

A digital certificate is an electronic document, issued by a trusted Certificate Authority (CA), that links a public key to the identity of its owner. It lets you trust that a public key really belongs to the organisation it claims to.

A certificate contains: the owner's name or organisation, the owner's public key, the name of the issuing CA, a serial number, the dates it is valid from and to, the algorithms used, and the CA's own digital signature.

How one is obtained: the organisation sends its public key and proof of identity to a CA; the CA checks the identity; the CA creates the certificate and signs it with the CA's private key. Browsers already hold CA public keys, so they can verify the CA's signature on any certificate.

Digital signatures

A digital signature proves who sent a message (authentication), that it wasn't altered (integrity), and that the sender can't deny sending it (non-repudiation). The message itself is not encrypted by this process.

Exam-style questions

This topic covers two halves of AI: searching a graph for the best route with Dijkstra's algorithm and A*, and machine learning, where a system improves by learning from data rather than following hand-written rules.

Graphs in AI

A graph is a set of nodes (vertices) connected by edges. Edges may be weighted (a cost, distance or time) and may be directed (one way). Graphs let AI model problems as states and moves: places on a map, positions in a game, or concepts in a knowledge network. Finding the best solution then becomes finding the lowest-cost path through the graph.

Dijkstra's algorithm

Dijkstra's algorithm finds the shortest path from a start node to every other node in a graph with non-negative weights.

1. Give the start node a distance of 0 and every other node ∞. Mark all nodes unvisited.
2. Choose the unvisited node with the smallest distance and mark it visited. Its distance is now final.
3. For each unvisited neighbour, calculate the distance through the current node (current distance + edge weight). If that is smaller than the neighbour's recorded distance, update it and record the current node as its previous node.
4. Repeat from step 2 until every node has been visited (or the destination has been visited).
5. Trace back through the previous nodes from the destination to find the route.

The A* algorithm

A* finds the shortest path to one goal more efficiently by also using a heuristic: an estimate of the remaining distance to the goal, such as the straight-line distance on a map. For each node it calculates:

f(n) = g(n) + h(n)

where g(n) is the actual cost from the start to n, and h(n) is the heuristic estimate from n to the goal. A* always expands the open node with the lowest f, so it heads towards the goal and usually explores far fewer nodes than Dijkstra. If the heuristic never overestimates the true distance, A* is guaranteed to find the shortest path.

Worked example: the same graph as above, from A to F, with heuristic values h(A) = 9, h(B) = 7, h(C) = 8, h(D) = 5, h(E) = 3, h(F) = 0.

Machine learning

Machine learning is a branch of AI in which a system learns from data and improves its performance at a task without being explicitly programmed with rules for every case.

Artificial neural networks

An artificial neural network (ANN) is loosely modelled on the brain. It has an input layer, one or more hidden layers and an output layer of nodes (artificial neurons). Each connection has a weight. A node multiplies each input by its weight, adds them up, and passes the total through an activation function to produce its output. Learning means adjusting the weights so the network's outputs become correct. ANNs have driven recent progress in machine learning because they can learn very complex, non-linear patterns from examples, rather than needing a programmer to write the rules.

Deep learning

Deep learning uses neural networks with many hidden layers. Each layer learns more abstract features: in an image, edges, then shapes, then whole objects. It can work on raw data (pixels, sound) without people choosing the features. It needs very large amounts of training data and processing power (GPUs), and is used for image recognition, speech recognition, translation and language models.

Back propagation of errors

1. Training data is fed forward through the network and the output is compared with the expected (correct) output to calculate the error.
2. The error is sent backwards through the network, layer by layer, working out how much each weight contributed to it.
3. Each weight is adjusted slightly to reduce the error (gradient descent).
4. This is repeated over many training examples and many rounds (epochs) until the error is acceptably small.

Regression

Regression is a supervised method that predicts a continuous numeric value by finding the relationship between input variables and the output, for example fitting a line of best fit to predict a house's price from its floor area. The model is adjusted to minimise the difference between its predictions and the real values in the training data.

Exam-style questions

The standard searching and sorting algorithms, how to implement the abstract data types, how to compare algorithms with Big O notation, and recursion. Paper 4 expects you to code all of this, so the examples are in pseudocode and Python.

Searching

Linear search

Checks each item in turn. Works on unsorted data. Worst case: n comparisons, so O(n). See topic 10 for the pseudocode.

Binary search

Works only on sorted data. Look at the middle item: if it is the target, stop; if the target is larger, discard the lower half; otherwise discard the upper half. Repeat on the remaining half. Each comparison halves the search space, so the worst case is about log₂ n comparisons: O(log n). For 1000 items that's at most 10 comparisons, against up to 1000 for a linear search.

FUNCTION BinarySearch(SearchItem : INTEGER) RETURNS INTEGER
    DECLARE Low, High, Mid : INTEGER
    Low ← 1
    High ← 100                         // global array Data[1:100], sorted
    WHILE Low <= High
        Mid ← (Low + High) DIV 2
        IF Data[Mid] = SearchItem THEN
            RETURN Mid
        ELSE
            IF Data[Mid] < SearchItem THEN
                Low ← Mid + 1
            ELSE
                High ← Mid - 1
            ENDIF
        ENDIF
    ENDWHILE
    RETURN -1                          // not found
ENDFUNCTION

def binary_search(items, target):
    low, high = 0, len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Sorting

Insertion sort

Builds a sorted section at the start of the array. Each new item is taken out and inserted into its correct place in the sorted section by shifting larger items one place right. Efficient for small or nearly sorted data (best case O(n)); worst case O(n²).

PROCEDURE InsertionSort()
    DECLARE I, J, Key : INTEGER
    FOR I ← 2 TO 10                    // global array Items[1:10]
        Key ← Items[I]
        J ← I - 1
        WHILE J >= 1 AND Items[J] > Key
            Items[J + 1] ← Items[J]
            J ← J - 1
        ENDWHILE
        Items[J + 1] ← Key
    NEXT I
ENDPROCEDURE

def insertion_sort(items):
    for i in range(1, len(items)):
        key = items[i]
        j = i - 1
        while j >= 0 and items[j] > key:
            items[j + 1] = items[j]
            j -= 1
        items[j + 1] = key

The bubble sort from topic 10 is also O(n²) in the worst case, and O(n) in the best case when a flag stops it early. In practice insertion sort usually makes fewer comparisons and moves.

Implementing abstract data types

Stack and queue

Both can be built from an array with pointers (see topic 10). A circular queue uses MOD so the pointers wrap round to the start of the array:

SIZE = 5
queue = [None] * SIZE
front, rear, count = 0, -1, 0

def enqueue(item):
    global rear, count
    if count == SIZE:
        return False                     # queue full
    rear = (rear + 1) % SIZE
    queue[rear] = item
    count += 1
    return True

def dequeue():
    global front, count
    if count == 0:
        return None                      # queue empty
    item = queue[front]
    front = (front + 1) % SIZE
    count -= 1
    return item

Linked list

In Paper 4 a linked list is usually an array of nodes, each with a data field and a pointer field. A start pointer marks the first node, a free pointer marks the first unused node, and −1 means null. The free nodes are themselves linked together into a free list.

NULL = -1

class Node:
    def __init__(self):
        self.data = ""
        self.pointer = NULL

nodes = [Node() for _ in range(10)]
for i in range(9):
    nodes[i].pointer = i + 1             # link all nodes into the free list
start, free = NULL, 0

def insert(item):                        # keeps the list in ascending order
    global start, free
    if free == NULL:
        print("List is full")
        return
    new = free
    free = nodes[free].pointer           # take the first free node
    nodes[new].data = item
    previous, current = NULL, start
    while current != NULL and nodes[current].data < item:
        previous, current = current, nodes[current].pointer
    if previous == NULL:                 # insert at the start
        nodes[new].pointer = start
        start = new
    else:                                # insert between previous and current
        nodes[new].pointer = current
        nodes[previous].pointer = new

def output_list():
    current = start
    while current != NULL:
        print(nodes[current].data)
        current = nodes[current].pointer

To delete a node: find it, keeping track of the previous node; set the previous node's pointer to the deleted node's pointer (or move the start pointer if it was first); then add the deleted node to the front of the free list.

Binary tree

Each node has a left pointer and a right pointer. In a binary search tree, everything in a node's left subtree is smaller than it and everything in its right subtree is larger, so searching, like a binary search, halves the possibilities at each step.

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def insert(node, data):
    if node is None:
        return TreeNode(data)
    if data < node.data:
        node.left = insert(node.left, data)
    else:
        node.right = insert(node.right, data)
    return node

def in_order(node):
    if node is not None:
        in_order(node.left)
        print(node.data)
        in_order(node.right)

root = None
for value in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, value)
in_order(root)

Graphs and dictionaries

A graph ADT can be stored as an adjacency matrix (a 2D array where cell [i, j] holds the weight of the edge from i to j, or 0) or an adjacency list (each node stores a list of its neighbours). A dictionary ADT stores key-value pairs and looks values up by key; it is usually implemented as a hash table, giving close to O(1) lookup.

graph = {"A": {"B": 4, "C": 2}, "B": {"A": 4, "C": 1, "D": 5}}   # adjacency list
phone_book = {"Sara": "0300-1234567"}                             # dictionary
phone_book["Ali"] = "0321-7654321"
print(phone_book["Sara"])

Comparing algorithms: Big O

Big O notation describes how an algorithm's time (or memory) requirement grows as the size of the input, n, grows. It shows the worst-case order of growth, ignoring constants. Time complexity is about the number of steps; space complexity is about the memory needed.

Recursion

A recursive subroutine is defined in terms of itself: it calls itself. Every recursive subroutine needs:

• a base case: a condition where it returns a value without calling itself, which stops the recursion;
• a general (recursive) case: where it calls itself with a different argument;
• each call must move closer to the base case.

FUNCTION Factorial(N : INTEGER) RETURNS INTEGER
    IF N = 0 THEN
        RETURN 1                           // base case
    ELSE
        RETURN N * Factorial(N - 1)        // general case
    ENDIF
ENDFUNCTION

How a compiler implements recursion

Each call pushes a stack frame onto the call stack, holding the return address, the parameters and the local variables for that call. When the base case is reached, frames are popped one at a time as each call returns its value to the call below it (unwinding). If the recursion is too deep (or never reaches a base case), the stack runs out of memory: a stack overflow.

Recursion vs iteration: recursive solutions can be shorter and more natural for problems that are recursive by nature (tree traversal, divide and conquer). But they use more memory, because of the stack frames, and are often slower because of the call overhead.

Exam-style questions

numbers = [12, 5, 33, 7, 21, 9, 40, 1, 18, 26]

def insertion_sort_descending():
    for i in range(1, len(numbers)):
        key = numbers[i]
        j = i - 1
        while j >= 0 and numbers[j] < key:
            numbers[j + 1] = numbers[j]
            j -= 1
        numbers[j + 1] = key

FUNCTION Calc(N : INTEGER) RETURNS INTEGER
    IF N = 0 THEN
        RETURN 0
    ELSE
        RETURN (N MOD 10) + Calc(N DIV 10)
    ENDIF
ENDFUNCTION

A programming paradigm is a style of programming, with its own way of structuring a solution. This topic covers object-oriented programming in depth (a Paper 4 favourite), declarative programming with Prolog-style facts and rules, random-access files and exception handling.

Programming paradigms

Low-level

Programming close to the hardware in assembly language, using the processor's instruction set and addressing modes: immediate, direct, indirect, indexed and relative (see topic 4).

Imperative (procedural)

The program is a sequence of statements that change the program's state, organised into procedures and functions. You state how to solve the problem step by step (see topic 11).

Object-oriented

The program is built from objects that combine data (attributes) and the methods that act on that data, modelling things in the problem.

Declarative

You state what is true (facts and rules) and what you want to find (a goal), and the language works out how to satisfy it. Prolog and SQL are declarative.

Object-oriented programming

Class

A blueprint or template defining the attributes and methods that its objects will have.

Object (instance)

A single example of a class, created from it, with its own values for the attributes. Creating one is called instantiation.

Attribute (property)

A data item stored in an object.

Method

A procedure or function defined in a class that acts on an object's data.

Constructor

The method that runs when an object is created, usually to set its initial attribute values.

Encapsulation

Keeping an object's attributes and methods together in the class, and making attributes private so they can only be accessed through the object's public methods. This protects the data from being changed in invalid ways.

Getter and setter

Public methods that return (get) or change (set) a private attribute. A setter can validate the new value first.

Inheritance

A subclass (derived class) takes on all the attributes and methods of its superclass (base class) and can add its own, so code is reused rather than rewritten.

Polymorphism

A method with the same name behaves differently depending on the class of the object it belongs to, because a subclass overrides the inherited method with its own version.

Containment (aggregation)

One class contains objects of another class as attributes: a "has a" relationship, such as a Department that has Employees.

In Cambridge pseudocode

CLASS Employee
    PRIVATE Name : STRING
    PRIVATE HourlyRate : REAL
    PUBLIC PROCEDURE NEW(GivenName : STRING, GivenRate : REAL)
        Name ← GivenName
        HourlyRate ← GivenRate
    ENDPROCEDURE
    PUBLIC FUNCTION GetName() RETURNS STRING
        RETURN Name
    ENDFUNCTION
    PUBLIC PROCEDURE SetHourlyRate(NewRate : REAL)
        IF NewRate > 0 THEN
            HourlyRate ← NewRate
        ENDIF
    ENDPROCEDURE
    PUBLIC FUNCTION CalculatePay(Hours : REAL) RETURNS REAL
        RETURN Hours * HourlyRate
    ENDFUNCTION
ENDCLASS

CLASS Manager INHERITS Employee
    PRIVATE Bonus : REAL
    PUBLIC PROCEDURE NEW(GivenName : STRING, GivenRate : REAL, GivenBonus : REAL)
        SUPER.NEW(GivenName, GivenRate)
        Bonus ← GivenBonus
    ENDPROCEDURE
    PUBLIC FUNCTION CalculatePay(Hours : REAL) RETURNS REAL
        RETURN SUPER.CalculatePay(Hours) + Bonus
    ENDFUNCTION
ENDCLASS

DECLARE Boss : Manager
Boss ← NEW Manager("Ayesha", 2000, 15000)
OUTPUT Boss.CalculatePay(40)

In Python

class Employee:
    def __init__(self, name, hourly_rate):    # constructor
        self.__name = name                     # __ makes an attribute private
        self.__hourly_rate = hourly_rate

    def get_name(self):                        # getter
        return self.__name

    def set_hourly_rate(self, rate):           # setter with validation
        if rate > 0:
            self.__hourly_rate = rate

    def calculate_pay(self, hours):
        return hours * self.__hourly_rate


class Manager(Employee):                       # inheritance
    def __init__(self, name, hourly_rate, bonus):
        super().__init__(name, hourly_rate)
        self.__bonus = bonus

    def calculate_pay(self, hours):            # overrides the inherited method
        return super().calculate_pay(hours) + self.__bonus


class Department:                              # containment
    def __init__(self, name):
        self.__name = name
        self.__staff = []

    def add_employee(self, employee):
        self.__staff.append(employee)

    def total_pay(self, hours):
        total = 0
        for person in self.__staff:            # polymorphism: each object uses
            total += person.calculate_pay(hours)   # its own calculate_pay
        return total


sales = Department("Sales")
sales.add_employee(Employee("Bilal", 1500))
sales.add_employee(Manager("Ayesha", 2000, 15000))
print(sales.total_pay(40))                     # 60000 + 95000 = 155000

Declarative programming

A declarative program is a knowledge base of facts (things that are true) and rules (how new facts can be worked out). You then ask a goal (query), and the system searches the knowledge base for values that make it true. Constants start with a lower-case letter; variables start with an upper-case letter.

01 parent(ali, sara).
02 parent(ali, omar).
03 parent(sara, zain).
04 parent(sara, hina).
05 male(ali).
06 male(omar).
07 male(zain).
08 female(sara).
09 female(hina).
10 father(X, Y) IF parent(X, Y) AND male(X).
11 grandparent(X, Z) IF parent(X, Y) AND parent(Y, Z).

Cambridge papers usually write rules with IF and AND. In real Prolog these are written :- and a comma: father(X, Y) :- parent(X, Y), male(X).

Instantiation

Giving a variable a value while trying to satisfy a goal. For grandparent(ali, G), Y is first instantiated to sara by clause 01.

Backtracking

When part of a goal fails, or to find further solutions, the system goes back to the most recent choice point and tries the next possible value. After finding G = zain and G = hina with Y = sara, it backtracks and tries Y = omar; parent(omar, Z) has no match, so there are no more solutions.

File processing

Text files store lines of characters (see topic 10). To store records, a random file lets a program jump straight to the record at a given position, which is how a hashed file from topic 13 is implemented.

DECLARE Student : StudentRecord
DECLARE Address : INTEGER
OPENFILE "Students.dat" FOR RANDOM

// write a record to the position given by a hash of its key
Address ← Hash(Student.StudentID)
SEEK "Students.dat", Address
PUTRECORD "Students.dat", Student

// read the record back from that position
SEEK "Students.dat", Address
GETRECORD "Students.dat", Student

CLOSEFILE "Students.dat"

In Python, objects can be written to and read from a binary file with the pickle module:

import pickle

def save_records(records, filename):
    with open(filename, "wb") as file:          # "wb" = write binary
        for record in records:
            pickle.dump(record, file)

def load_records(filename):
    records = []
    try:
        with open(filename, "rb") as file:      # "rb" = read binary
            while True:
                records.append(pickle.load(file))
    except EOFError:                            # reached the end of the file
        pass
    except FileNotFoundError:
        print("The file", filename, "does not exist.")
    return records

Exception handling

An exception is an unexpected event that happens while a program is running and disrupts its normal flow, such as a missing file, invalid input, division by zero or an index out of range. If it isn't handled, the program crashes. Exception handling catches the exception and runs code to deal with it, so the program can show a useful message, recover, or close safely without losing data.

def get_age():
    while True:
        try:
            age = int(input("Enter your age: "))   # may raise ValueError
            if age < 0:
                raise ValueError("Age can't be negative")
            return age
        except ValueError:
            print("Please enter a whole number of 0 or more.")

try:
    with open("scores.txt") as f:
        scores = [int(line) for line in f]
    print("Average:", sum(scores) / len(scores))  # may raise ZeroDivisionError
except FileNotFoundError:
    print("scores.txt was not found.")
except ZeroDivisionError:
    print("The file is empty.")
finally:
    print("Finished.")                             # always runs

Exam-style questions

class Book:
    def __init__(self, title, author):
        self.__title = title
        self.__author = author
        self.__on_loan = False

    def get_title(self):
        return self.__title

    def get_author(self):
        return self.__author

    def get_on_loan(self):
        return self.__on_loan

    def lend_book(self):
        if self.__on_loan:
            return False
        self.__on_loan = True
        return True

def get_quantity():
    while True:
        try:
            quantity = int(input("Number of items: "))
            if quantity > 0:
                return quantity
            print("The number must be positive.")
        except ValueError:
            print("That is not a whole number.")

FUNCTION GetItem(Position : INTEGER) RETURNS StockItem
    DECLARE Item : StockItem
    OPENFILE "Stock.dat" FOR RANDOM
    SEEK "Stock.dat", Position
    GETRECORD "Stock.dat", Item
    CLOSEFILE "Stock.dat"
    RETURN Item
ENDFUNCTION