9618 Computer Science Hub — Paper 3 + Paper 4 + AI Tutor

Decimal	Binary	Hex
0–9	0000–1001	0–9
10	1010	A
15	1111	F
255	1111 1111	FF

Topology	Pros	Cons
Star	Failure of one node doesn't bring down the network	Central switch is a single point of failure
Bus	Cheap, simple	One break breaks everything
Mesh	Highly resilient (multiple paths)	Expensive, complex routing

Gate	Symbol notation	Output is 1 when…
AND	A · B	both inputs are 1
OR	A + B	at least one input is 1
NOT	Ā	input is 0
NAND	(A · B)'	NOT both inputs are 1
NOR	(A + B)'	both inputs are 0
XOR	A ⊕ B	inputs differ

Medium	How it stores	Examples
Magnetic	Magnetised regions on a spinning platter	HDD, magnetic tape
Optical	Pits and lands read by a laser	CD, DVD, Blu-ray
Solid-state	Floating-gate transistors	SSD, USB drive, SD card

Mode	Operand means…
Immediate	The actual value (e.g. `LDM #5`)
Direct	The address that holds the value (`LDD 100`)
Indirect	The address that holds the address (`LDI 100`)
Indexed	Address = base + index register (`LDX 100`)

Type	Behaviour	Use
Compiler	Translates the whole program once → executable.	Production builds.
Interpreter	Translates and runs line-by-line.	Scripting, interactive use.
Assembler	Translates assembly → machine code.	Low-level programming.

Validation	Verification
Checks data is reasonable: range check, type check, length check, format check, presence check, check digit.	Checks data has been copied accurately: double-entry, visual check, parity bit, checksum.

Form	Rule
1NF	No repeating groups; each cell holds a single atomic value.
2NF	1NF, and every non-key attribute depends on the whole primary key.
3NF	2NF, and no transitive dependencies (non-key attributes depend only on the key).

Type	Holds
INTEGER	whole numbers
REAL	numbers with a decimal point
CHAR	a single character
STRING	a sequence of characters
BOOLEAN	TRUE / FALSE
DATE	calendar date

Strategy	What it does
Black-box	Test by input/output only — no view of internals.
White-box	Use knowledge of code paths; aim for branch / statement coverage.
Alpha	Internal testing inside the developing organisation.
Beta	Public / limited-user testing before release.
Acceptance	By the client to confirm the contract is met.

These notes are AI-assisted study material. Always cross-check against the official 9618 syllabus or your teacher before relying on them in an exam.

13Data Representation

Numbers, characters, images, and sound — how a computer stores them.

Number bases

Computers use binary (base 2). Humans often use hexadecimal (base 16) as a compact way to write binary because 4 binary digits = 1 hex digit.

Binary	Decimal	Hex
0000	0	0
1010	10	A
1111	15	F
11111111	255	FF

Two's complement (signed integers)

Two's complement: the standard way to represent negative integers. The most significant bit has a negative place value; everything else is positive.

For 8-bit two's complement, the MSB has value −128. So 10000000 = −128, 11111111 = −1, 01111111 = +127.

To negate a number:

Invert all bits (one's complement)
Add 1

Worked example

+5 in 8-bit: 00000101 → invert: 11111010 → add 1: 11111011 = −5

Binary Coded Decimal (BCD)

Each decimal digit (0–9) is encoded as 4 bits. Used in calculators and electronic displays where precise decimal arithmetic matters.

ASCII vs Unicode

ASCII	Unicode
7 bits (128 chars)	16+ bits (millions of chars)
English alphabet only	All world scripts
Small files	Larger files

14User-Defined Data Types

Building your own types: composite, non-composite, classes, pointers.

Non-composite types (enumerated, pointer)

Enumerated type: a user-defined list of named values with implicit ordering.
Example: TYPE TDayOfWeek = (Mon, Tue, Wed, Thu, Fri, Sat, Sun)

Pointer type: stores a memory address. TYPE TIntPtr = ^INTEGER declares a pointer to an integer.

Composite types (record, set, class)

Record

TYPE TStudent
   DECLARE Name : STRING
   DECLARE Age  : INTEGER
   DECLARE Mark : REAL
ENDTYPE

Records group different data types under one name. Each field has its own type. Access using dot notation: student.Name.

Set

A collection of unique values of the same type with set operations like union (∪), intersection (∩), difference (−).

Class

A blueprint for objects (covered in Topic 20.1 — OOP).

When to use each

Type	Use when
Enumerated	Fixed list of named options (months, suits)
Pointer	Building linked lists, trees, dynamic structures
Record	Grouping mixed fields about one thing
Set	Unique items, mathematical set operations

15File Organisation & Access

Serial, sequential, random, index-sequential — and hashing.

File organisation methods

Method	Order	Best for
Serial	Order of arrival	Logs, transaction files
Sequential	Sorted by key	Payroll, batch processing
Index-sequential	Sorted + index	Fast lookups + range queries
Random (direct)	By hash address	Fast direct lookups

Hashing

Hashing algorithm: a function that converts a key into a storage address. Example: address = key MOD table_size

Collisions

When two keys hash to the same address. Resolution methods:

Linear probing — try next slot, then next, until empty.
Chaining — store a linked list at each address.
Rehashing — apply a second hash function.

A poor hash function creates many collisions and degrades to O(n) performance. Use a function that distributes keys evenly.

16Floating-Point Numbers

How real numbers are stored — mantissa, exponent, normalisation.

Form

A floating-point number = mantissa × 2^exponent. Both stored in two's complement.

Example layout (8-bit mantissa, 4-bit exponent)M = 0.5 × 2³ = 4

Normalisation

Normalised form: the mantissa's first two bits are different (01… for positive, 10… for negative). This gives maximum precision.

Why normalise?

Unique representation for each value
Maximum precision in the available bits
Easier comparison

Errors

Error	Cause
Overflow	Number too large for the exponent
Underflow	Number too small (very close to 0)
Rounding error	Mantissa truncated
Loss of precision	Subtracting very similar numbers

17Communication & Networking

Protocols, TCP/IP, packet switching, circuit switching.

TCP/IP protocol stack (4 layers)

Layer	Role	Examples
Application	User-facing protocols	HTTP, FTP, SMTP, DNS
Transport	End-to-end delivery, reliability	TCP, UDP
Internet	Routing, IP addressing	IP, ICMP
Link (Network access)	Physical transmission	Ethernet, Wi-Fi

Packet switching

Data broken into small packets with headers
Each packet routed independently through the network
Reassembled at the destination
Resilient — failed links cause re-routing, not failure

Circuit switching

Dedicated end-to-end path for the whole call (old telephone networks). Wastes bandwidth when idle, but no congestion once connected.

BitTorrent (peer-to-peer)

Files split into pieces shared between many peers. A tracker manages who has which piece. Reduces server load and is resilient.

18Hardware

CISC vs RISC, pipelining, parallel processing, virtual machines.

RISC vs CISC

RISC	CISC
Few simple instructions	Many complex instructions
Each instruction one cycle	Variable cycles
Fixed-length instructions	Variable-length
Hardwired control	Microcoded
Lower power, mobile devices	Desktops, x86

Pipelining

The processor fetches the next instruction while still executing the current one — like an assembly line. Stages typically: Fetch → Decode → Execute → Memory → Write-back.

Pipelining increases throughput, not the speed of any single instruction. A branch can stall (flush) the pipeline.

Parallel processing

SISD — single instruction, single data (classical)
SIMD — same instruction on many data items (graphics, vectors)
MIMD — different instructions on different data (modern multi-core)
Massively parallel — supercomputers, weather simulation

Virtual machines

Software that emulates a computer. Benefits: run multiple OSes on one host, isolated sandboxes, server consolidation. Drawbacks: slower than native, needs more RAM, single point of failure.

19System Software

OS functions, memory management, interrupts, scheduling, translation.

Operating system functions

Memory management
File management
Input/output management
Process / CPU scheduling
Security / access control
Provide user interface
Interrupt handling

Memory management

Paging

Physical memory divided into fixed page frames; programs divided into matching pages. A page table maps logical → physical pages.

Segmentation

Memory divided into variable-size segments matching logical units (code, stack, data). May cause external fragmentation.

Virtual memory

Uses disk as if it were RAM. Page fault = required page not in RAM → swap in from disk. Thrashing = excessive paging that slows the whole system.

Interrupts

Interrupt: a signal that pauses normal CPU execution so a higher-priority task can be handled.

Handling: save state on stack → run ISR (interrupt service routine) → restore state → resume. Sources: I/O, timer, hardware error, software exception.

Scheduling

Algorithm	Idea
FCFS	First-come, first-served
SJF	Shortest job first
Round robin	Each gets a time slice (quantum)
Multilevel feedback	Multiple queues, dynamic priority

Translation: compiler vs interpreter vs assembler

	Compiler	Interpreter	Assembler
Input	High-level source	High-level source	Assembly
Output	Object code	Runs line-by-line	Machine code
Speed	Fast at runtime	Slow at runtime	Fast
Debug	Harder	Easier	Hard

Compilation phases

Lexical analysis — break source into tokens; build symbol table
Syntax analysis — check tokens fit grammar; build parse tree
Semantic analysis — check meaning (types, declarations)
Code generation — produce object code
Optimisation — improve efficiency

20Security, Privacy & Data Integrity

Encryption, hashing, digital certificates, SSL/TLS, DRM.

Symmetric vs asymmetric encryption

Symmetric	Asymmetric
Same key for encrypt/decrypt	Public key + private key
Fast	Slower
Key distribution problem	No shared secret needed
AES, DES	RSA

Digital signatures

Sender hashes message → message digest
Encrypts digest with their private key → signature
Receiver decrypts with sender's public key → expected digest
Receiver hashes message themselves and compares

SSL / TLS handshake

Client sends "ClientHello" + supported ciphers
Server responds with certificate + chosen cipher
Client verifies certificate via Certificate Authority
Both agree a symmetric session key (using asymmetric encryption)
Rest of session uses fast symmetric encryption

Digital certificates

A document signed by a trusted Certificate Authority binding a public key to an identity. Contains: name, public key, validity period, CA's signature.

21Artificial Intelligence

Machine learning, neural networks, deep learning.

Machine learning types

Type	Data	Example
Supervised	Labelled inputs/outputs	Spam detection, image classification
Unsupervised	Unlabelled — find clusters	Customer segmentation
Reinforcement	Rewards from environment	Game-playing agents

Neural network

Layers of nodes (neurons). Each connection has a weight. Input × weight summed → activation function → output. Training adjusts weights to minimise error using back-propagation.

Input layer — receives raw data
Hidden layers — extract features
Output layer — produces prediction

Deep learning = neural network with many hidden layers.

22Boolean Algebra & Logic Circuits

Truth tables, K-maps, flip-flops, half/full adders.

Boolean laws

Law	Form
Identity	A·1 = A, A+0 = A
Null	A·0 = 0, A+1 = 1
Idempotent	A·A = A, A+A = A
Complement	A·A̅ = 0, A+A̅ = 1
De Morgan 1	(A·B)̅ = A̅ + B̅
De Morgan 2	(A+B)̅ = A̅ · B̅
Distributive	A·(B+C) = A·B + A·C

Karnaugh maps (K-maps)

A grid arrangement of a truth table where adjacent cells differ by one variable (Gray code order). Group 1s in rectangles of size 1, 2, 4, 8… to simplify Boolean expressions.

Half adder

Two inputs (A, B), two outputs: Sum = A⊕B, Carry = A·B.

Full adder

Three inputs (A, B, Cin), two outputs: Sum = A⊕B⊕Cin, Cout = (A·B) + (Cin·(A⊕B)).

Flip-flops

SR flip-flop

S=1, R=0 → Q=1 (set). S=0, R=1 → Q=0 (reset). S=R=0 → hold. S=R=1 → invalid.

JK flip-flop

Fixes SR's invalid state. J=K=1 → Q toggles. Clock-triggered.

Flip-flops are 1-bit memory cells — combine many to build registers.

23BNF & RPN

Defining language grammars and evaluating expressions.

Backus-Naur Form (BNF)

BNF: a notation for defining context-free grammars. Uses ::= for "is defined as" and | for alternatives. Terminals are literal characters; non-terminals are wrapped in < >.

<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<integer> ::= <digit> | <digit><integer>

The recursion in <integer> lets it match strings of any length.

Reverse Polish Notation (RPN)

Operators come after their operands. No brackets needed.

Infix	RPN
3 + 4	3 4 +
(3 + 4) × 5	3 4 + 5 ×
3 + 4 × 5	3 4 5 × +

Evaluating RPN with a stack

Read left to right
If number → push onto stack
If operator → pop top two, apply, push result
Final stack value = answer

Example: 3 4 + 5 ×

Push 3 → [3]
Push 4 → [3,4]
+ → pop 4 and 3, push 7 → [7]
Push 5 → [7,5]
× → pop 5 and 7, push 35 → [35]
Answer: 35

These notes are AI-assisted study material. Always cross-check against the official 9618 syllabus or your teacher before relying on them in an exam.

19.1aAlgorithms — Searching

Linear search and binary search.

Linear search

Check each item until found — works on any list, sorted or not.

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

Complexity: O(n) worst case.

Binary search

Halve the search range each step. Requires sorted data.

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

Complexity: O(log n).

If the array is not sorted, binary search gives wrong answers. State this requirement explicitly in exams.

19.1bAlgorithms — Sorting

Bubble sort and insertion sort.

Bubble sort

Repeatedly compare adjacent items and swap if out of order. After each pass the largest unsorted element "bubbles" to the end.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

Complexity: O(n²) worst, O(n) best (with early-exit flag).

Insertion sort

Build a sorted list one element at a time by inserting each new element in the right place.

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

Complexity: O(n²) worst, O(n) best. Often faster than bubble in practice.

19.1cADTs — Stack & Queue

LIFO and FIFO collections.

Stack (LIFO)

Operations: push, pop, peek, isEmpty.

class Stack:
    def __init__(self):
        self.__items = []
    def push(self, x): self.__items.append(x)
    def pop(self):
        if self.is_empty(): raise Exception("Stack underflow")
        return self.__items.pop()
    def peek(self): return self.__items[-1]
    def is_empty(self): return len(self.__items) == 0

Uses: function call stack, undo, expression evaluation, RPN.

Queue (FIFO)

class Queue:
    def __init__(self):
        self.__items = []
    def enqueue(self, x): self.__items.append(x)
    def dequeue(self):
        if self.is_empty(): raise Exception("Queue underflow")
        return self.__items.pop(0)
    def is_empty(self): return len(self.__items) == 0

Uses: print queue, breadth-first search, task scheduling, message buffers.

19.1dADTs — Linked List & Binary Tree

Pointer-based dynamic structures.

Linked list

A chain of nodes. Each node holds data and a pointer to the next node. The head points to the first node; the last node points to None.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
    def insert(self, data):
        n = Node(data); n.next = self.head; self.head = n
    def find(self, target):
        cur = self.head
        while cur:
            if cur.data == target: return True
            cur = cur.next
        return False

Binary search tree (BST)

Each node has up to two children. Rule: left child < parent < right child. In-order traversal visits values in sorted order.

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

19.1eDictionary & Graph

Dictionary

Key → value pairs. Average O(1) lookup. In Python use {}.

contacts = {"Alice": "1234", "Bob": "5678"}
print(contacts["Alice"])

Graph (knowledge only — no code required)

A set of nodes (vertices) connected by edges. Edges can be directed/undirected and weighted/unweighted.

Uses: social networks, maps, computer networks, dependency graphs.

Implemented as an adjacency list (dictionary of neighbours) or adjacency matrix (2D array).

19.1fBig O Complexity

Algorithm	Best	Average	Worst
Linear search	O(1)	O(n)	O(n)
Binary search	O(1)	O(log n)	O(log n)
Bubble sort	O(n)	O(n²)	O(n²)
Insertion sort	O(n)	O(n²)	O(n²)

Space complexity

How much extra memory the algorithm uses. Bubble sort = O(1) extra (in-place). Merge sort = O(n) extra.

19.2Recursion

A function that calls itself.

Essential features

Base case — when to stop
Recursive call — heading toward the base case
Unwinding — calls return back up the chain

def factorial(n):
    if n == 0:                  # base case
        return 1
    return n * factorial(n - 1) # recursive call

Stack frames

Each recursive call adds a new stack frame holding local variables and return address. Too many frames → stack overflow.

When recursion beats iteration

Tree / graph traversal
Divide-and-conquer (mergesort, quicksort)
Problems with naturally recursive definitions (factorial, Fibonacci, Towers of Hanoi)

Recursion uses more memory than iteration. Always identify the base case explicitly in comments.

20.1aOOP — Classes & Objects

Key terms

Term	Meaning
Class	Blueprint / template
Object (instance)	Actual thing built from class
Attribute (property)	Data stored in object
Method	Function in a class
Constructor	`__init__` — runs at object creation

class Student:
    def __init__(self, name, year):
        self.name = name
        self.year = year
    def greet(self):
        print(f"Hi, I'm {self.name}")

20.1bOOP — Encapsulation & Inheritance

Encapsulation

Hide internal data using __ prefix (private). Provide controlled access via getters and setters (with validation).

class Account:
    def __init__(self, balance):
        self.__balance = balance
    def get_balance(self):
        return self.__balance
    def deposit(self, x):
        if x <= 0: raise Exception("Invalid")
        self.__balance += x

Inheritance ("is-a")

Child class reuses + extends parent.

class Animal:
    def __init__(self, name): self.name = name
    def speak(self): print("sound")

class Dog(Animal):
    def speak(self): print(f"{self.name} says Woof!")

20.1cOOP — Polymorphism & Containment

Polymorphism ("many forms")

Same method name behaves differently on different classes. Achieved by method overriding.

Containment ("has-a") / Aggregation

An object holds another object as an attribute.

class Engine:
    def __init__(self, hp): self.hp = hp

class Car:
    def __init__(self, model, hp):
        self.model = model
        self.engine = Engine(hp)   # car HAS-A engine

Inheritance = "is-a" (Dog IS-A Animal). Containment = "has-a" (Car HAS-A Engine). Memorise the distinction for long-answer questions.

20.2File & Exception Handling

File modes

Mode	Meaning
`"r"`	Read (must exist)
`"w"`	Write (creates/overwrites)
`"a"`	Append (creates if needed)

File access types

Serial — records in order of arrival
Sequential — sorted by key, read in order
Random — direct access by record number / hash

Reading and writing

with open("data.txt", "w") as f:
    f.write("Alice\n")
    f.write("Bob\n")

with open("data.txt", "r") as f:
    for line in f:
        print(line.strip())

Exception handling

try:
    x = int(input())
    print(100 / x)
except ValueError:
    print("Not a number")
except ZeroDivisionError:
    print("Can't divide by zero")
finally:
    print("Always runs")

Raise your own: raise Exception("message").

★Exam Strategy

Evidence document required

Full code listings (copy-paste from IDE)
Screenshots of program running each test case
Contents of any data files used

Test data — three types

Type	Example (age 0-120)
Normal	25
Boundary	0, 120
Erroneous	-1, 121, "abc"

Marks awarded for

Correctness of code
Meaningful identifier names
Comments and structure
Test evidence (screenshots)
Appropriate use of constructs (loops, functions, OOP)

Common pitfalls

Forgetting int(input()) for numeric input
Not using with open (file might not close)
No try/except around risky operations
Missing base case in recursion
Off-by-one errors in loops

9618 Paper 1 — AS Theory

1Data Representation

1.1 Number systems

1.2 Binary Coded Decimal (BCD)

1.3 Negative numbers — two's complement

Example: −5 in 8 bits

1.4 Characters — ASCII and Unicode

1.5 Images and sound

2Communication

2.1 Transmission mode & direction

2.2 Network topologies

2.3 The Internet, protocols, IPs

3Hardware

3.1 Logic gates

3.2 Primary memory

3.3 Secondary & off-line storage

4Processor Fundamentals

4.1 CPU components

4.2 The fetch–execute cycle

4.3 Interrupts

4.4 Assembly language

5System Software

5.1 Operating-system functions

5.2 Utility programs

5.3 Translators

6Security, Privacy & Data Integrity

6.1 Threats

6.2 Defences

6.3 Data validation vs verification

7Ethics & Ownership

8Databases

8.1 The relational model

8.2 Normalisation

8.3 SQL — DDL & DML basics

9618 Paper 2 — Fundamental Problem-solving & Programming

9Algorithm Design & Problem-solving

9.1 The five basic constructs

9.2 Pseudocode style (Cambridge)

9.3 Trace tables & dry-running

9.4 Stepwise refinement

10Data Types & Structures

10.1 Built-in data types

10.2 Arrays

10.3 Records (composite type)

10.4 File handling

11Programming

11.1 Python equivalents of pseudocode

11.2 String handling

11.3 Arrays / lists

11.4 Files

12Software Development

12.1 The development life cycle

12.2 Testing strategies

12.3 Test data choices

12.4 Maintainable code — style rules

9618 Paper 3 — Advanced Theory