Cambridge A‑Level Computer Science (9618) – Complete Revision Notes

---

Table of Contents

1. AS Foundations (Units 1‑12)
   1. 1. Data Representation
   2. 2. Multimedia & Compression
   3. 3. Computer Networks
   4. 4. Computer Architecture & CPU
   5. 5. Assembly Language & Machine Code
   6. 6. Bit‑Manipulation & Boolean Algebra
   7. 7. Operating Systems
   8. 8. Language Translators
   9. 9. Security, Ethics & Legal Issues
   10. 10. Databases (Relational Model & SQL)
   11. 11. Structured Programming – Use Parameters
   12. 12. Software Development Life‑Cycle (SDLC)
2. A‑Level Extensions (Units 13‑20)
   1. 13. User‑Defined Types & Abstract Data Types
   2. 14. File Organisation & Random Access
   3. 15. Floating‑Point Representation & Arithmetic
   4. 16. Communication Protocols & Internet Architecture
   5. 17. Virtual Machines & Managed Runtime Environments
   6. 18. Advanced Algorithms (Divide‑and‑Conquer, Greedy, DP)
   7. 19. Recursion, Exception Handling & Advanced Paradigms
   8. 20. Artificial Intelligence & Machine Learning Basics
3. Assessment Objectives (AO1‑AO3)
4. Practical Component (Paper 4)

---

AS Foundations (Units 1‑12)

1. Data Representation

• Number bases: binary, octal, decimal, hexadecimal – conversion both ways.
• Binary prefixes: kibi (Ki = 2¹⁰), mebi (Mi = 2²⁰), gibi (Gi = 2³⁰) – required for storage calculations.
• Signed integers:
  • Two’s‑complement representation, range calculation (e.g., 8‑bit: –128 … +127).
  • Overflow detection – adding two positive numbers that yields a negative result.
• Character encoding: ASCII (7‑bit), extended ASCII, Unicode (UTF‑8, UTF‑16) – why variable‑length encodings matter.
• Floating‑point basics (single precision, IEEE‑754):
  • Sign bit, exponent (bias = 127), mantissa (23 bits).
  • Special values: zero, infinity, NaN.

Typical exam question: Convert –75 (decimal) to an 8‑bit two’s‑complement binary number.

Worked example (Python):

def twos_complement(value, bits=8):
    if value < 0:
        value = (1 << bits) + value
    return format(value, f'0{bits}b')

print(twos_complement(-75))   # 10110101

---

2. Multimedia & Compression

• Digital representation:
  • Images – bitmap (pixel grid) vs. vector (geometric primitives).
  • Sound – sampling rate, bit‑depth, Nyquist theorem.
  • Video – frame rate, interlacing, colour space (YUV).
• Compression types:
  • Lossless – Run‑Length Encoding (RLE), Huffman coding, LZW.
  • Lossy – JPEG (Discrete Cosine Transform), MP3 (psycho‑acoustic model), MPEG‑4.
• Trade‑off analysis (AO3): effect on file size, quality, processing time.

Sample AO2 task: Explain why a JPEG photograph is usually smaller than a PNG of the same picture.

Python illustration of RLE:

def rle_encode(data):
    encoded = []
    i = 0
    while i < len(data):
        count = 1
        while i + 1 < len(data) and data[i] == data[i+1]:
            count += 1
            i += 1
        encoded.append((data[i], count))
        i += 1
    return encoded

print(rle_encode('AAAABBBCCDAA'))  # [('A',4),('B',3),('C',2),('D',1),('A',2)]

---

3. Computer Networks

• Network topologies: star, bus, ring, mesh – advantages & disadvantages.
• OSI 7‑layer model (mandatory for the syllabus):
  1. Physical – cables, signalling.
  2. Data Link – MAC addresses, error detection (CRC).
  3. Network – IP addressing, routing.
  4. Transport – TCP (reliable), UDP (unreliable).
  5. Session – dialogue control.
  6. Presentation – data translation, encryption.
  7. Application – HTTP, FTP, SMTP, DNS.
• Key protocols: HTTP/HTTPS, FTP, SMTP, POP3/IMAP, TCP, UDP, IP, ARP.
• Performance metrics: bandwidth, latency, throughput, jitter.
• Network security basics: firewalls, NAT, symmetric vs. asymmetric encryption, VPN.

Diagram suggestion: OSI stack with a data packet moving down from Application to Physical layer.

---

4. Computer Architecture & CPU

• Architectural models: Von Neumann (single memory for data & instructions) vs. Harvard (separate memories).
• CPU components:
  • ALU – arithmetic & logical operations.
  • Control Unit – instruction decoding, sequencing.
  • Registers – general‑purpose (e.g., R0‑R7), special‑purpose (PC, IR, MAR, MDR, ACC).
  • Cache hierarchy – L1, L2, L3, cache‑coherency.
  • Bus structures – system bus, address bus, data bus, control bus.
• Instruction cycle: Fetch → Decode → Execute → Store (sometimes split into additional micro‑steps).
• Performance calculations:
  • Clock speed (Hz), CPI (cycles per instruction), MIPS (million instructions per second).
  • Execution time = (Instruction count × CPI) / Clock rate.

Example calculation (AO2):

# 2 × 10⁶ instructions, average CPI = 2.5, clock = 3 GHz
time = (2e6 × 2.5) / 3e9 = 1.67 ms

---

5. Assembly Language & Machine Code

• Two‑pass assembler process:
  1. Pass 1 – builds the symbol table, calculates addresses.
  2. Pass 2 – generates object code using the symbol table.
• Typical instruction set (generic):

  Mnemonic	Operation	Typical format
  LOAD	Load operand into register	LOAD R, address
  STORE	Store register value	STORE R, address
  ADD	R ← R + operand	ADD R, address
  SUB	R ← R – operand	SUB R, address
  JMP	Unconditional branch	JMP label
  BEQ	Branch if equal	BEQ R1,R2,label

• Addressing modes (table for quick reference):

  Mode	Syntax example	Description
  Immediate	#5	Operand is a constant.
  Direct	1000	Operand address is given directly.
  Indirect	@R1	Register contains the address of the operand.
  Indexed	1000(R2)	Base address + index register.

• Loop example (generic assembly):

        LOAD   R1, =0          ; accumulator = 0
        LOAD   R2, =10         ; loop counter = 10
LOOP:   ADD    R1, R1, #1      ; R1 = R1 + 1
        SUB    R2, R2, #1      ; R2 = R2 – 1
        BNE    LOOP            ; branch if R2 ≠ 0

---

6. Bit‑Manipulation & Boolean Algebra

• Bitwise operators (C/Java/Python style):

  &  – AND
  |  – OR
  ^  – XOR
  ~  – NOT (one’s complement)
  << – left shift
  >> – right shift (arithmetic)

• Common tricks:
  • Mask extraction: (value & 0xFF) gets the low byte.
  • Toggle a bit: value ^ (1 << n).
  • Parity check: value ^ (value >> 1) ^ … ^ (value >> 7) & 1.
• Karnaugh maps – simplify up to 4‑variable Boolean expressions.
  • Group 1, 2, 4, or 8 adjacent cells.
  • Derive minimal Sum‑of‑Products (SOP) or Product‑of‑Sums (POS).

Python example (bit‑mask):

# Extract the 3rd byte (bits 16‑23) from an integer
def get_byte(value, n):
    return (value >> (n*8)) & 0xFF

print(hex(get_byte(0x12345678, 2)))   # 0x34

---

7. Operating Systems

• Core functions:
  • Process management – creation, scheduling, termination.
  • Memory management – allocation, paging, segmentation, virtual memory.
  • I/O control – device drivers, buffering.
  • File system – hierarchical directories, permissions, FAT vs. NTFS.
• Process states (state diagram):
  • New → Ready → Running → Blocked → Ready → Terminated.
• Scheduling algorithms (AO3 evaluation):

  Algorithm	Key characteristic	Typical use
  FCFS	First‑come, first‑served	Batch systems
  SJF	Shortest job first (optimal for average wait time)	Non‑preemptive environments
  Round‑Robin	Fixed time‑slice (quantum)	Time‑sharing systems
  Priority	Higher‑priority processes run first	Real‑time tasks

• Memory management details:
  • Paging – fixed‑size pages, page tables, page‑fault handling.
  • Segmentation – variable‑size segments, logical vs. physical address translation.
  • Virtual memory – demand paging, swap space.

---

8. Language Translators (Compilers, Interpreters, Assemblers)

• Compilation phases (mandatory for the syllabus):
  1. Lexical analysis – tokenisation (regular expressions).
  2. Syntax analysis – parsing (context‑free grammar, parse tree).
  3. Semantic analysis – type checking, scope resolution.
  4. Intermediate code generation – three‑address code.
  5. Optimisation – local, global, loop optimisations.
  6. Code generation – target machine instructions.
• Interpreters – execute source line‑by‑line; no separate object code (e.g., Python, BASIC).
• Assemblers – translate mnemonic assembly to machine code; may be one‑pass (simple) or two‑pass (symbol resolution).
• Just‑In‑Time (JIT) compilation – runtime translation used by Java Virtual Machine and .NET CLR for performance gains.

---

9. Security, Ethics & Legal Issues

• Security concepts (AO1‑AO3):
  • Confidentiality – encryption (symmetric: AES, DES; asymmetric: RSA, ECC).
  • Integrity – hashing (SHA‑256, MD5), digital signatures.
  • Availability – redundancy, backups, DDoS mitigation.
• Threats & attacks: malware, phishing, man‑in‑the‑middle, insider threats.
• Ethical frameworks: ACM Code of Ethics, BCS Code of Conduct.
• Legal context (UK focus):
  • Data Protection Act 2018 & GDPR – principles of lawful processing.
  • Computer Misuse Act 1990 – unauthorised access, hacking.
  • Intellectual property – copyright, patents, licences.

---

10. Databases (Relational Model & SQL)

• Relational concepts:
  • Tables, rows, columns, primary key, foreign key.
  • Normalization – 1NF (no repeating groups), 2NF (no partial dependency), 3NF (no transitive dependency).
  • Entity‑Relationship (ER) diagrams – entities, relationships, cardinalities.
• SQL statements:

  Category	Typical commands
  DDL	CREATE, ALTER, DROP
  DML	INSERT, UPDATE, DELETE, SELECT
  DCL	GRANT, REVOKE
  TCL	COMMIT, ROLLBACK, SAVEPOINT

• Joins & sub‑queries – inner, left/right outer, cross join, correlated sub‑query.
• Indexing & ACID properties – improve retrieval, ensure atomicity, consistency, isolation, durability.

Example query (customers with total orders > £500):

SELECT c.name, SUM(o.amount) AS total
FROM Customers c
JOIN Orders o ON c.id = o.cust_id
GROUP BY c.name
HAVING total > 500;

---

11. Structured Programming – Use Parameters

Why Use Parameters?

• Encapsulation – hide implementation details behind a clear interface.
• Reusability – the same procedure works with many data sets.
• Maintainability – changes are confined to the procedure definition.
• Clarity – the parameter list documents required inputs and outputs.

Parameter‑Passing Mechanisms

Mechanism	What is passed?	Effect on caller’s variable	Typical language support (A‑Level)
Call‑by‑value	Copy of the argument’s value	Original variable unchanged	Python, Java (primitives), C, Pascal (value parameters)
Call‑by‑reference	Reference (address) to the original variable	Modifications affect the caller	C++ (reference), Java (object references), Pascal (var parameters)
Call‑by‑name / Call‑by‑need	Expression re‑evaluated each use (lazy)	Depends on the expression; rarely used in mainstream A‑Level languages	Algol, Haskell (call‑by‑need)

Call‑by‑Value Example (Python‑style pseudocode)

def increment(x):
    x = x + 1          # only the local copy changes
    return x

a = 5
b = increment(a)      # a is still 5, b becomes 6

Call‑by‑Reference Example (C++‑style pseudocode)

void doubleValue(int &n) {   // & denotes a reference
    n = n * 2;                // modifies the original variable
}

int a = 4;
doubleValue(a);               // a is now 8

Default Parameters (Python‑style)

def greet(name, greeting="Hello"):
    print(f"{greeting}, {name}!")

greet("Alice")                # Hello, Alice!
greet("Bob", "Hi")            # Hi, Bob!

Parameter Scope & Lifetime

• Parameters are local to the procedure in which they are declared.
• Lifetime starts on entry to the procedure and ends on return.
• When passed by reference, the reference itself has the same lifetime, but it points to a variable that may outlive the call.

Design‑Evaluation Activity (AO3)

1. Write a procedure swap(a, b) that exchanges the values of two integers.
2. Implement it once using call‑by‑value and once using call‑by‑reference.
3. Analyse which version is more efficient and which better satisfies the requirement “the caller’s variables must be swapped”.

Worked Example – Bubble Sort (Pass‑by‑Reference)

proc bubbleSort(arr: list ref):
    n = length(arr)
    repeat
        swapped = false
        for i = 1 to n-1 do
            if arr[i] > arr[i+1] then
                temp = arr[i]
                arr[i] = arr[i+1]
                arr[i+1] = temp
                swapped = true
            end if
        end for
        n = n - 1
    until not swapped
end proc

# Main program
myList = [5, 2, 9, 1, 6]
bubbleSort(myList)   # myList is sorted in‑place

Key Take‑aways

• Parameters enable procedures to operate on external data without hard‑coding values.
• Choose the appropriate passing mechanism to control whether changes affect the caller.
• Default parameters reduce code duplication and improve readability.
• Always respect scope and lifetime when designing procedures.

---

12. Software Development Life‑Cycle (SDLC)

• Waterfall model – sequential phases (Requirements → Design → Implementation → Testing → Maintenance). Advantages: clear documentation, easy to manage. Disadvantages: inflexible, late discovery of errors.
• Iterative / Incremental model – develop a core system, then add functionality in cycles. Advantages: early user feedback, risk reduction. Disadvantages: requires good planning of iterations.
• Rapid Application Development (RAD) – heavy use of prototyping and CASE tools. Advantages: fast delivery, high user involvement. Disadvantages: may compromise on scalability and documentation.
• Agile principles (Scrum) – short sprints, daily stand‑ups, product backlog. Emphasises adaptability and customer collaboration.
• Evaluation criteria (AO3):
  • Project size and complexity.
  • Stakeholder requirements for documentation vs. speed.
  • Resource availability (time, people, tools).
  • Risk profile – safety‑critical vs. commercial web app.

---

A‑Level Extensions (Units 13‑20)

13. User‑Defined Types & Abstract Data Types (ADTs)

• Structures / records – grouping heterogeneous data (e.g., struct Student { id:int; name:string; GPA:float; }).
• Classes (OOP) – encapsulation of data (attributes) and behaviour (methods).
• Abstract Data Types – defined by operations, not implementation (e.g., Stack, Queue, List, Map).
• Encapsulation & information hiding – use of private/public access specifiers.

Example: Stack ADT (pseudocode)

type Stack
    procedure push(s: Stack ref, x)
    procedure pop(s: Stack ref) returns element
    function top(s: Stack) returns element
    function empty(s: Stack) returns boolean
end type

---

14. File Organisation & Random Access

• Sequential files – records stored one after another; efficient for batch processing.
• Random‑access files – direct access via file pointer; requires fixed‑length records or an index.
• Indexing techniques:
  • Primary index – sorted on key field.
  • Secondary index – separate structure for non‑key fields.
  • B‑tree / B+‑tree – balanced tree for large data sets.
• File handling in Python (example):

# Random‑access binary file
import struct

record_format = 'i20s'          # int id, 20‑byte name
size = struct.calcsize(record_format)

def write_record(f, pos, rec_id, name):
    f.seek(pos * size)
    f.write(struct.pack(record_format, rec_id, name.encode('utf‑8')))

def read_record(f, pos):
    f.seek(pos * size)
    data = f.read(size)
    return struct.unpack(record_format, data)

with open('students.dat', 'r+b') as f:
    write_record(f, 0, 101, 'Alice')
    print(read_record(f, 0))   # (101, b'Alice')

---

15. Floating‑Point Representation & Arithmetic

• IEEE‑754 formats:
  • Single precision (32‑bit): 1‑bit sign, 8‑bit exponent (bias = 127), 23‑bit mantissa.
  • Double precision (64‑bit): 1‑bit sign, 11‑bit exponent (bias = 1023), 52‑bit mantissa.
• Normalised vs. denormalised numbers – handling of very small magnitudes.
• Rounding modes – round‑to‑nearest, round‑toward‑zero, etc.
• Arithmetic pitfalls:
  • Loss of significance (catastrophic cancellation).
  • Overflow and underflow.
  • Associativity not guaranteed – use Kahan summation for improved accuracy.

Python demonstration of rounding error

total = sum([0.1] * 10)
print(total)          # 0.9999999999999999 – not exactly 1.0

---

16. Communication Protocols & Internet Architecture

• TCP/IP model – 4 layers (Link, Internet, Transport, Application) and mapping to OSI.
• Key protocols:
  • IP (IPv4/IPv6) – addressing, fragmentation.
  • TCP – reliable, connection‑oriented, flow control (sliding window).
  • UDP – connection‑less, low latency.
  • HTTP/HTTPS – request/response, statelessness, secure sockets.
  • DNS – hierarchical name resolution.
• Routing algorithms – distance‑vector (Bellman‑Ford), link‑state (Dijkstra).
• Network security extensions – TLS handshake, certificates, public‑key infrastructure.

---

17. Virtual Machines & Managed Runtime Environments

• Virtual Machine (VM) concepts – abstraction of hardware, isolation, portability.
• Java Virtual Machine (JVM) – bytecode, just‑in‑time (JIT) compilation, garbage collection.
• .NET Common Language Runtime (CLR) – Intermediate Language (IL), JIT, automatic memory management.
• Advantages – “write once, run anywhere”, security sandboxing.
• Disadvantages – performance overhead, larger memory footprint.

---

18. Advanced Algorithms (Divide‑and‑Conquer, Greedy, Dynamic Programming)

• Divide‑and‑Conquer – recursion, merge sort, quick sort, binary search. Complexity analysis via recurrence relations (Master theorem).
• Greedy algorithms – make the locally optimal choice; examples: Huffman coding, Kruskal’s MST.
• Dynamic Programming (DP) – overlapping sub‑problems, optimal substructure; examples: Fibonacci (memoisation), Knapsack, Longest Common Subsequence.

Example: DP for Fibonacci (Python)

def fib(n, memo={}):
    if n in (0,1):
        return n
    if n not in memo:
        memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

print(fib(10))   # 55

---

19. Recursion, Exception Handling & Advanced Programming Paradigms

• Recursion – base case, recursive case, stack depth, tail recursion optimisation.
• Exception handling – try/catch/finally, custom exception classes, resource cleanup.
• Advanced paradigms:
  • Event‑driven programming – callbacks, listeners.
  <