A static data structure has a fixed size set at creation time. It cannot grow or shrink. Arrays are static in most languages.

A dynamic data structure can grow and shrink during execution by allocating and freeing memory as needed. Linked lists, trees, and graphs are dynamic.

A 1D array is a list. Imagine a row of numbered boxes:

scores ← [85, 72, 90, 68, 95]
         index: 0   1   2   3   4

scores[2] = 90   ← access element at index 2
scores[0] = 85   ← first element is index 0

A 2D array is a grid (rows and columns), accessed by two indices [row][column]:

grid ← [[1, 2, 3],
        [4, 5, 6],
        [7, 8, 9]]

grid[1][2] = 6   ← row 1, column 2

2D arrays represent matrices, game boards, images (pixels), and spreadsheets. The spec says a 2D array is a way to represent a matrix.

Linear queue implemented with an array: maintain two pointers — front (index of first item) and rear (index of last item). When you dequeue, front moves right. Problem: even when items are removed, the space at the front of the array can never be reused — you run out of space even when there's conceptually room.

Circular queue solves this: the array "wraps around" — when rear reaches the end, it goes back to index 0 if that space has been freed. Use modulo arithmetic:

rear ← (rear + 1) MOD capacity

This reuses space that was freed by dequeuing from the front. The queue is full when (rear + 1) MOD capacity = front.

Items are assigned a priority when added. The item dequeued is not necessarily the one at the "front" — it's the one with the highest priority. Equal-priority items are dequeued in FIFO order.

Implementation: an array plus an integer topPointer starting at -1 (empty). Push increments it and stores the value; Pop reads the value and decrements it.

stack ← [_, _, _, _, _]   (capacity 5, all empty)
topPointer ← -1

Push(10): stack[0] ← 10, topPointer ← 0
Push(20): stack[1] ← 20, topPointer ← 1
Push(30): stack[2] ← 30, topPointer ← 2
Pop():    returns stack[2] = 30, topPointer ← 1

Adjacency matrix: a 2D array where row i, column j = 1 (or the weight) if there's an edge from vertex i to vertex j, otherwise 0.

     A  B  C  D
A  [ 0, 1, 0, 1 ]
B  [ 1, 0, 1, 0 ]
C  [ 0, 1, 0, 1 ]
D  [ 1, 0, 1, 0 ]

Adjacency list: each vertex has a list of its neighbours.

A: [B, D]
B: [A, C]
C: [B, D]
D: [A, C]

A rooted tree has one designated root node (the top). Every other node has exactly one parent and zero or more children. Nodes with no children are leaves.

A binary tree is a rooted tree where each node has at most two children, called the left child and the right child.

A binary search tree (BST) is a binary tree where for every node: all values in the left subtree are less than the node's value, and all values in the right subtree are greater. This ordering enables efficient search, insertion, and deletion.

        50
       /  \
      30    70
     / \   / \
    20  40 60  80

To search for 60: start at 50 → 60 > 50, go right to 70 → 60 < 70, go left to 60 → found. Only 3 comparisons for an 8-node tree.

A hash table maps keys to values using a hash function. The hash function takes a key and computes an index into an array. This gives O(1) average lookup — you jump directly to where the value should be.

Example hash function: index = key MOD tableSize

Table size = 7
Key "Alice" → hash → 3
Key "Bob"   → hash → 5
Key "Carol" → hash → 1

table[3] = "Alice's data"
table[5] = "Bob's data"
table[1] = "Carol's data"

Collision: when two different keys hash to the same index. This will happen. Two resolution strategies:

1. Chaining: each slot in the table is a linked list. Colliding entries are added to the list at that slot. Lookup: hash the key, go to slot, search the (hopefully short) list.

2. Open addressing / rehashing: if a slot is occupied, probe the next slot (or next+1, or next+n²) until an empty slot is found. Linear probing: try slot, slot+1, slot+2, etc.

A vector is an ordered list of numbers, all drawn from the same field (usually ℝ, the real numbers). A vector with n components is called an n-vector over ℝ, written ℝⁿ.

Example: the 4-vector [2.0, 3.14, -1.0, 2.72]

Representations:

• As a list: [2.0, 3.14, -1.0, 2.72]
• As a 1D array: Dim v(3) As Single in VB.Net
• As a dictionary (function interpretation): {0: 2.0, 1: 3.14, 2: -1.0, 3: 2.72} — maps index to value
• Geometrically: as an arrow from the origin to the point (x, y) in 2D space

Vector operations:

Convex combination of vectors u and v: αu + βv where α ≥ 0, β ≥ 0, and α + β = 1. This describes all points on the line segment between u and v.

BFS explores all neighbours of the current vertex before moving deeper. It processes vertices level by level. Uses a queue.

Algorithm:

1. Create an empty queue and a "visited" set
2. Add the start vertex to the queue and mark it visited
3. While queue is not empty:
     a. Dequeue the front vertex, process it
     b. For each unvisited neighbour: mark visited, enqueue it

DFS explores as far as possible along one branch before backtracking to try other branches. Uses a stack (or recursion).

Algorithm:

1. Create an empty stack and a "visited" set
2. Push the start vertex. Mark visited.
3. While stack is not empty:
     a. Pop the top vertex, process it
     b. For each unvisited neighbour: mark visited, push it

Standard mathematical notation (infix) puts the operator between operands: 3 + 4. This requires brackets to show order: (3 + 4) × 5 vs 3 + (4 × 5).

Reverse Polish Notation (RPN) / postfix puts the operator after its operands. Crucially, brackets are never needed — the order of operations is unambiguous from the notation itself.

To convert infix to RPN (Shunting-yard algorithm): use a stack for operators. Push operands directly to output. For operators, pop operators of higher/equal precedence from stack to output first, then push the new one. At end, pop remaining operators to output.

To evaluate RPN using a stack:

1. Read tokens left to right
2. If a number: push to stack
3. If an operator: pop two values, apply the operator, push the result
4. The final stack value is the answer

Check each element in turn from the start until the target is found or the list ends.

FOR i ← 0 TO length(list) - 1
    IF list[i] = target THEN
        RETURN i
    ENDIF
ENDFOR
RETURN -1   ← not found

Works on: any list, sorted or unsorted. Time complexity: O(n) — in the worst case you check every element. Simple but slow for large lists.

Requires a sorted list. Repeatedly halve the search space by comparing the target to the middle element.

low ← 0
high ← length(list) - 1
WHILE low ≤ high
    mid ← (low + high) DIV 2
    IF list[mid] = target THEN
        RETURN mid
    ELSE IF list[mid] < target THEN
        low ← mid + 1    ← target must be in upper half
    ELSE
        high ← mid - 1   ← target must be in lower half
    ENDIF
ENDWHILE
RETURN -1

Time complexity: O(log n). Each step halves the remaining items. For 1 billion items, worst case = only 30 comparisons (log₂(10⁹) ≈ 30).

Repeatedly step through the list, comparing adjacent pairs and swapping them if out of order. After each pass, the largest unsorted element "bubbles" to its correct position.

FOR passNum ← 1 TO length - 1
    swapped ← False
    FOR i ← 0 TO length - 1 - passNum
        IF list[i] > list[i+1] THEN
            SWAP list[i], list[i+1]
            swapped ← True
        ENDIF
    ENDFOR
    IF NOT swapped THEN RETURN   ← early exit: already sorted
ENDFOR

Time complexity: O(n²) worst/average case. O(n) best case (already sorted, with early exit flag). Included in the spec as an example of an inefficient sort. Fine for small lists or nearly-sorted data.

Divide-and-conquer approach. Recursively split the list in half until you have single elements (trivially sorted), then merge pairs of sorted sublists back together.

FUNCTION mergeSort(list)
    IF length(list) ≤ 1 THEN
        RETURN list   ← base case: single element is sorted
    ENDIF
    mid ← length(list) DIV 2
    left ← mergeSort(list[0..mid-1])   ← sort left half
    right ← mergeSort(list[mid..end])  ← sort right half
    RETURN merge(left, right)           ← merge sorted halves
ENDFUNCTION

The merge step: compare the front elements of both sorted halves, take the smaller one, advance that pointer. Repeat until both halves are exhausted.

Time complexity: O(n log n) always — even for the worst case. Space: O(n) — needs temporary space for merging. Better than bubble sort for large datasets.

Finds the shortest path from a source vertex to all other vertices in a weighted, directed or undirected graph with non-negative weights.

Algorithm:

1. Set distance to source = 0, all other distances = ∞
2. Create a set of unvisited nodes (all nodes)
3. While unvisited nodes remain:
     a. Pick the unvisited node with smallest current distance (call it current)
     b. For each neighbour of current that is still unvisited:
         calculate tentative_distance = dist[current] + edge_weight
         if tentative_distance < dist[neighbour]: update dist[neighbour] and record current as the predecessor
     c. Mark current as visited (remove from unvisited)

Graph:
A --(4)-- B --(2)-- D
|         |
(2)       (5)
|         |
C --(1)-- D

From source A:
Initial: dist = {A:0, B:∞, C:∞, D:∞}

Visit A (dist=0): 
  Neighbour B: 0+4=4 < ∞ → dist[B]=4, pred[B]=A
  Neighbour C: 0+2=2 < ∞ → dist[C]=2, pred[C]=A

Visit C (dist=2, smallest unvisited):
  Neighbour D: 2+1=3 < ∞ → dist[D]=3, pred[D]=C

Visit D (dist=3):
  Neighbour B: 3+2=5 > 4 → no update (B already has a better path)

Visit B (dist=4): done.

Shortest paths from A: A=0, C=2, D=3, B=4
Path to D: A → C → D

Big-O notation describes how an algorithm's resource requirements (time or space) grow as the input size n increases. It gives the worst-case growth rate, ignoring constant factors and lower-order terms.

Why ignore constants? We care about how fast things grow. An algorithm doing 3n steps and one doing 1000n steps are both O(n) — as n gets huge, both grow linearly. What matters is the shape of the growth, not the coefficient.

A Finite State Machine is a model of computation with:

• A finite set of states (drawn as circles)
• One designated start state (shown with an arrow pointing into it)
• One or more accept/final states (drawn as double circles)
• Transitions between states triggered by input symbols (drawn as labelled arrows)

An FSM accepts a string if, starting in the start state and reading the string left to right, you end in an accept state. Otherwise it rejects it.

States: S0 (start), S1, S2 (accept)
Transitions:
  S0 --0--> S1
  S0 --1--> S0
  S1 --0--> S1
  S1 --1--> S2
  S2 --0--> S1
  S2 --1--> S0

Test "1001": S0→S0→S1→S0→... wait:
  '1': S0→S0
  '0': S0→S1
  '0': S1→S1
  '1': S1→S2  ← ends in accept state → ACCEPTED

Test "10": S0→S0→S1 → not accept → REJECTED

State transition table: a grid where rows = current states, columns = inputs, cells = next state. Same information as the diagram, in tabular form.

Mealy machines (A-level addition): FSMs that produce output on each transition, not just accept/reject. The output is written on the transition arrow alongside the input: input/output.

A set is an unordered collection of distinct values (no duplicates). Notation: A = {1, 2, 3, 4, 5}

Set comprehension: A = {x | x ∈ ℕ ∧ x ≥ 1} — read as "the set of all x such that x is a natural number AND x ≥ 1".

The symbol | means "such that". ∈ means "is a member of". ∧ means AND.

Compact set notation: {0ⁿ1ⁿ | n ≥ 1} = the set of all strings with n zeros followed by n ones: {01, 0011, 000111, ...}

Finite vs infinite sets: The set {1,2,3} is finite. ℕ (natural numbers) is infinite. Countably infinite: can be put in one-to-one correspondence with ℕ (e.g. all integers). ℝ is not countable — there are more real numbers than natural numbers.

A regular expression (regex) is a compact notation for describing a set of strings. It defines a regular language — the set of all strings it matches.

Some languages cannot be described by regular expressions. For example, the language of balanced brackets {(), (()), ((())), ...} requires keeping count — which an FSM (finite memory) cannot do. These require a more powerful description: context-free grammars, written in BNF.

BNF production rules:

• <non-terminal> — a symbol that can be further expanded (in angle brackets)
• terminal — a literal character that cannot be further expanded
• ::= means "is defined as"
• | means "or"

<digit>   ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<integer> ::= <digit> | <integer><digit>
<letter>  ::= a | b | c | ... | z
<identifier> ::= <letter> | <identifier><letter> | <identifier><digit>

The second rule says: an integer is either a single digit, OR an integer followed by a digit. This recursive definition captures any length of integer.

Syntax diagrams (also called railroad diagrams) express the same rules graphically. Follow the tracks through boxes (non-terminals) and text (terminals) to build valid strings.

A Turing machine is a theoretical model of computation proposed by Alan Turing in 1936. It is not a physical device — it's a mathematical tool for understanding what computers can and cannot do in principle.

Components:

• An infinitely long tape divided into cells. Each cell contains a symbol (or is blank).
• A read/write head that scans one cell at a time and can move left or right.
• A state register storing the machine's current state.
• A transition function (the "program"): given (current state, symbol under head) → (new symbol to write, direction to move, new state).

Tape: 1 0 1 _ _ _   (binary 5, head starts at rightmost 1)
State: q0 = scanning for rightmost digit
State: q1 = adding 1

Transition:
(q0, 1) → (0, LEFT, q0)   ← flip 1 to 0, carry left
(q0, 0) → (1, HALT)       ← flip 0 to 1, done
(q0, _) → (1, HALT)       ← tape end: write 1, done

The halting problem asks: is there an algorithm that, given any program P and any input I, can determine whether P will eventually halt (stop) or run forever?

Turing proved in 1936 that no such algorithm can exist. This is not a practical limitation — it's a mathematical proof.

Proof by contradiction (simplified):

1. Assume HALTS(P, I) exists — a program that returns True if P halts on I, False if it runs forever.
2. Construct program D:
   • If HALTS(D, D) = True: loop forever
   • If HALTS(D, D) = False: halt immediately
3. Now ask: what does HALTS(D, D) return?
   If True (D halts on D): D's code says loop forever — contradiction.
   If False (D doesn't halt on D): D's code says halt — contradiction.
4. Contradiction either way → HALTS cannot exist.

A number base defines how many distinct digit symbols exist and what position values are used.

• Base 10 (decimal): digits 0–9. Position values: 1, 10, 100, 1000, …
• Base 2 (binary): digits 0–1. Position values: 1, 2, 4, 8, 16, 32, 64, 128, …
• Base 16 (hexadecimal): digits 0–9 then A=10, B=11, C=12, D=13, E=14, F=15. Position values: 1, 16, 256, 4096, …

Decimal → Binary: repeatedly divide by 2, collect remainders from bottom up.

42 ÷ 2 = 21 r 0
21 ÷ 2 = 10 r 1
10 ÷ 2 = 5  r 0
 5 ÷ 2 = 2  r 1
 2 ÷ 2 = 1  r 0
 1 ÷ 2 = 0  r 1
42₁₀ = 101010₂  (read remainders bottom to top)

Binary → Decimal: multiply each bit by its place value and sum.

101010₂ = 1×32 + 0×16 + 1×8 + 0×4 + 1×2 + 0×1
        = 32 + 8 + 2 = 42

Binary → Hex: group into nibbles (4 bits) from the right. Each nibble → one hex digit.

10101110₂ = 1010 1110 = A E = AE₁₆

Hex → Binary: expand each hex digit to its 4-bit binary equivalent.

3F₁₆ = 0011 1111₂

Unsigned binary: all n bits represent magnitude. Range: 0 to 2ⁿ−1.

Binary addition rules: 0+0=0, 0+1=1, 1+0=1, 1+1=10 (write 0, carry 1), 1+1+1=11 (write 1, carry 1).

  01101101  (109)
+ 00110101  ( 53)
----------
  10100010  (162)

Overflow occurs when the result exceeds the number of bits available. The extra bit is lost, giving a wrong answer. This is a critical error to be aware of.

Two's complement is the standard way to represent negative integers in binary. The most significant bit (MSB) has a negative place value: −2ⁿ⁻¹.

For 8-bit two's complement:

• Range: −128 to +127
• MSB = 0 → positive; MSB = 1 → negative

Converting decimal to two's complement:

1. If positive: just convert normally
2. If negative: convert the absolute value to binary, then flip all bits, then add 1

Converting two's complement to decimal: if MSB=0, normal conversion. If MSB=1, the value = -(flip all bits and add 1).

Subtraction using two's complement: A − B = A + (−B). Convert B to its two's complement, then add to A.

12 = 0000 1100
-7: 7 = 0000 0111, flip = 1111 1000, add 1 = 1111 1001

  0000 1100
+ 1111 1001
----------
  0000 0101 = 5 ✓  (the overflow bit is discarded)

A binary point is inserted at a fixed position. Bits to the right have fractional values: ½, ¼, ⅛, ¹⁄₁₆, …

Format: 4 bits integer, 4 bits fraction
Binary: 0101.1100

Integer part:  0×8 + 1×4 + 0×2 + 1×1 = 5
Fraction part: 1×½ + 1×¼ + 0×⅛ + 0×¹⁄₁₆ = 0.75
Total: 5.75

Decimal to fixed-point binary: convert integer part normally. For the fraction: repeatedly multiply by 2, take the integer part as the next bit.

ASCII (American Standard Code for Information Interchange): uses 7 bits to encode 128 characters — uppercase and lowercase letters, digits 0-9, punctuation, and 32 control characters (newline, tab, etc.). Examples: 'A'=65, 'a'=97, '0'=48.

Extended ASCII extends to 8 bits (256 characters) but has many incompatible variants for different scripts.

Unicode was introduced to handle all world writing systems — over 1 million possible code points, covering Arabic, Chinese, emoji, and everything else. UTF-8 is the most common encoding: backwards-compatible with ASCII (ASCII characters use 1 byte, others use 2-4 bytes). UTF-16 uses 2 or 4 bytes. UTF-32 uses exactly 4 bytes.

Parity bit: an extra bit added to make the total number of 1s even (even parity) or odd (odd parity). Detects single-bit errors in transmission.

Data: 1001011 (4 ones)
Even parity bit: 0 (total ones = 4 → already even)
Transmitted: 10010110

If received as: 10010100 (one bit flipped)
Count ones: 3 (odd) → ERROR DETECTED

Majority voting: each bit sent 3 times. The receiver takes whichever value appears in at least 2 of the 3 copies. Can correct single-bit errors.

Sent: 111 000 111 000 → 1 0 1 0
Received: 101 000 110 001
Majority: 1   0   1   0   ← correct!

Check digit: a digit calculated from the other digits and appended to data (ISBN, barcodes, bank account numbers). The receiver recalculates and compares. Detects transcription errors.

Analogue data is continuous — it can take any value within a range. Sound waves, temperature, voltage are analogue. The real world is analogue.

Digital data is discrete — it can only take specific values from a defined set. Computers process digital data: sequences of 0s and 1s.

ADC (Analogue-to-Digital Converter): samples an analogue signal at regular time intervals (the sample rate), measures the amplitude at each sample point, and rounds to the nearest digital value (quantisation). Used when recording audio, measuring sensors.

DAC (Digital-to-Analogue Converter): takes a sequence of digital values and reconstructs an analogue signal. Used when playing back audio through speakers, controlling motors.

A bitmap stores an image as a grid of pixels (picture elements). Each pixel's colour is stored as a binary number.

File size calculation (ignoring metadata):

File size (bits) = Width (px) × Height (px) × Colour depth (bits)
File size (bytes) = File size (bits) ÷ 8

Example: 800 × 600 pixels, 24-bit colour
= 800 × 600 × 24 = 11,520,000 bits
= 11,520,000 ÷ 8 = 1,440,000 bytes = 1.44 MB

To store sound digitally, an ADC measures the sound wave's amplitude at regular intervals:

Nyquist theorem: to accurately reproduce a sound containing frequencies up to f Hz, the sample rate must be at least 2f Hz. CDs sample at 44.1 kHz to capture up to 22.05 kHz — slightly above human hearing (~20 kHz).

File size calculation:

File size (bits) = Sample rate × Bit depth × Duration (s) × Channels
Example: 44100 Hz, 16-bit, stereo (2 channels), 3 minutes
= 44100 × 16 × 180 × 2 = 254,016,000 bits ÷ 8 = ~31.75 MB

MIDI (Musical Instrument Digital Interface): does NOT store audio. Stores event messages: "note on", "note off", "pitch", "velocity", "which instrument". A synthesiser interprets these to produce sound. MIDI files are tiny (kilobytes vs megabytes for audio). Easy to edit — change tempo, instrument, transpose key.

Run-length encoding (RLE) — lossless. Replace a run of repeated values with (count, value).

Original: AAAABBBBAACCCCCC (16 chars)
Encoded:  4A4B2A6C          (8 chars) ← 50% smaller
Decoded back: AAAABBBBAACCCCCC ← perfect reconstruction

Works well for simple images with large areas of uniform colour (e.g. icons, cartoons). Bad for photographs (few repeated pixels).

Dictionary-based (LZW, LZ77) — lossless. Build a dictionary of repeated sequences encountered so far. Replace subsequent occurrences with short codes referencing the dictionary. Used in ZIP, GIF, PNG.

Encryption: transforming plaintext (readable) into ciphertext (unreadable) using a cipher and a key. The ciphertext can only be understood by someone who knows how to decrypt it.

Caesar cipher: shift each letter in the plaintext by a fixed number of positions in the alphabet.

Key = 3
A→D, B→E, C→F, ..., X→A, Y→B, Z→C

Plaintext:  HELLO
Ciphertext: KHOOR

Why easily cracked? Only 25 possible keys. An attacker can try all 25 in seconds. Also, letter frequency analysis works: if 'E' is the most common letter in English and 'H' appears most in the ciphertext, the shift is probably 3.

Vernam cipher (one-time pad): XOR each character of the plaintext with the corresponding character of a truly random key of equal length. The key must be used exactly once.

Plaintext:  01001000  ('H' in binary)
Key:        10110101  (random)
XOR (⊕):   11111101  (ciphertext)

To decrypt: 11111101 ⊕ 10110101 = 01001000 → 'H'

Comparison:

An operating system (OS) is the most important piece of system software. It sits between the hardware and user programs. Its two key jobs are:

1. Hiding hardware complexity: Application programs don't need to know whether the computer has a Samsung or Western Digital hard drive, or whether it's running on an Intel or AMD processor. The OS provides a consistent interface (API) that works regardless of the underlying hardware.

2. Resource management: Multiple processes run simultaneously — your browser, music player, antivirus, and system services are all running at once. The OS manages the allocation of:

• Processor time — scheduling which process runs when, for how long (process scheduling)
• Memory — deciding which parts of RAM each process can use
• I/O devices — managing access to keyboard, disk, network card, etc.
• File system — organising files on storage, managing permissions

Examples: Windows, macOS, Linux, Android, iOS.

Utility programs: perform specific system maintenance tasks. Examples: disk defragmenter, backup software, antivirus, file compression tools, disk formatter.

Libraries: collections of pre-written, pre-tested code that programs can call. Instead of writing a square root function from scratch, your program calls math.sqrt() from the maths library. Libraries are shared — many programs use the same library, saving memory and development time.

Translators: programs that convert source code in one language to another form. Three types: compiler, interpreter, assembler — covered in section 4.6.3.

An imperative high-level language is one where you write explicit step-by-step instructions telling the computer how to do something. This distinguishes it from declarative languages (like SQL or Haskell) where you describe what you want without specifying how.

Source code (what the programmer writes) must be translated into a form the computer can execute. Three translation strategies:

Source code: the human-readable program the programmer writes. Object (executable) code: the compiled machine code that the CPU runs directly.

Logic gates are electronic circuits that perform Boolean operations on binary inputs (0=false, 1=true). They are the fundamental building blocks of all digital computers.

Memory tricks:

• AND: both inputs must be 1 → output is 1
• OR: at least one input is 1 → output is 1
• XOR (exclusive OR): exactly one input is 1 → output is 1 (different → 1)
• NAND: NOT AND — everything AND does, NAND does the opposite
• NOR: NOT OR — everything OR does, NOR does the opposite

In circuit diagrams: gates are connected with wires. You must be able to: trace inputs through a circuit to produce a truth table, write a Boolean expression for a circuit, and draw a circuit from a Boolean expression.

Boolean algebra lets you simplify logic expressions algebraically — the same way you simplify 2x + 3x = 5x in regular algebra. This reduces the number of gates needed in a circuit, saving cost and power.

Key identities:

De Morgan's laws — essential for converting between NAND/NOR and AND/OR/NOT:

• NOT(A AND B) = (NOT A) OR (NOT B)
• NOT(A OR B) = (NOT A) AND (NOT B)

All modern computers have the same fundamental components communicating via buses (collections of parallel wires):

This cycle repeats billions of times per second in a modern CPU. Each instruction goes through three stages:

FETCH

1. MAR ← PC: The address held in the Program Counter is copied into the MAR. We're going to fetch from this address.
2. PC ← PC + 1: The PC is incremented immediately so it points to the next instruction. (This happens before the current instruction is even decoded.)
3. MDR/MBR ← Memory[MAR]: The data at the address in MAR is fetched from RAM and placed in the MBR. This travels along the data bus.
4. CIR ← MBR: The instruction is copied from MBR into the CIR, where it stays while being decoded and executed.

DECODE

5. The Control Unit reads the instruction in the CIR. It splits it into the opcode (what operation to do) and the operand (the value or address to operate on). It then activates the appropriate components.

EXECUTE

6. The decoded instruction is carried out — this might involve the ALU (for arithmetic), main memory (for load/store), or I/O. The result may update a register, memory, or the PC (for a branch).

Barcode reader: a light source (LED or laser) illuminates the barcode. Dark bars absorb light; white spaces reflect it. A photodetector converts reflections to a digital signal (0s and 1s representing the bars). This is decoded to the product code.

Digital camera: a lens focuses light onto a CCD (charge-coupled device) or CMOS sensor. The sensor contains millions of light-sensitive cells (pixels). Each cell measures light intensity and converts it to an electrical charge. This is sampled by an ADC and stored as binary data.

Laser printer: 1. A laser beam sweeps across a photosensitive drum, discharging areas where ink should not appear. 2. Charged toner particles stick to the remaining charged areas. 3. Paper rolls past the drum and toner transfers to paper. 4. The fuser unit melts the toner onto the paper permanently.

RFID (Radio Frequency Identification): a reader emits a radio signal that powers a passive tag (no battery needed). The tag responds by transmitting its stored ID. Used in contactless payment, access cards, stock tracking. Active tags have their own power source and longer range.

Secondary storage is needed because RAM is volatile (data lost when power off) and expensive. Secondary storage is non-volatile, persistent, and cheaper per gigabyte.

When a software engineer writes a recommendation algorithm for social media, they make decisions about what values the system encodes: engagement? truthfulness? user wellbeing? These decisions affect billions of people. The engineer has moral responsibility for those choices.

Key considerations:

• Algorithmic bias: if training data reflects historical discrimination (e.g. fewer women in senior roles), an AI hiring tool trained on it will perpetuate that bias. The engineer who didn't correct for this has made a moral choice, intentionally or not.
• Intended vs actual use: a tool built for communication can be used for coordination of harm. What responsibility does the builder have?
• Scale: a bug affecting 0.1% of 1 billion users affects 1 million people. The same negligence that would be minor in a small business becomes catastrophic at scale.
• Intellectual property: software can be copied infinitely at zero cost. This creates tensions between creators' right to profit and others' desire to access.
• Privacy: collecting data about users without meaningful consent. The right to be forgotten. Data minimisation.

Computing enables:

• Mass surveillance: CCTV with facial recognition, mobile phone tracking, GCHQ mass data collection (revealed by Snowden). Who watches the watchers?
• Data harvesting: social media companies collect detailed personal profiles used for targeted advertising, political micro-targeting (Cambridge Analytica), and sold to third parties.
• Information dissemination: anyone can publish globally. Misinformation spreads as fast as truth. "Fake news" can influence elections.
• Automation and employment: jobs disappearing to automation (manufacturing, admin, potentially professional roles). Who benefits from the productivity gains?
• Digital divide: unequal access to technology creates unequal opportunity. The elderly, the poor, and those in developing countries are disadvantaged.

Relevant UK legislation (know the purpose, not specific sections):

Why legislation struggles:

• Technology changes faster than law: by the time a law is passed and implemented, the technology has moved on.
• Jurisdiction: a company in the USA serving UK users — which country's law applies? Enforcing laws across borders is extremely difficult.
• Anonymity: it's hard to identify and prosecute those who break laws online.
• Technical complexity: legislators often don't fully understand the technology they're trying to regulate.

• Cultural imperialism: dominant tech companies (mostly American) shape global culture through the platforms and defaults they choose. The English language is favoured. Western values are embedded in algorithms.
• Filter bubbles: recommendation algorithms show you content similar to what you've already engaged with. Over time, people see only views they already agree with, deepening polarisation.
• Impact on human behaviour: social media designed for engagement exploits psychological vulnerabilities (variable reward schedules, social comparison). Linked to anxiety, depression, reduced attention spans.
• Cultural heritage: the internet has preserved vast amounts of human knowledge and culture, but digital formats become obsolete. Who maintains digital archives?

Data must travel from one place to another as electrical signals. Two fundamental approaches:

Parallel transmission: multiple bits sent simultaneously, each on its own wire. A byte (8 bits) sent over 8 wires at once. Sounds faster — but:

• Skew: each wire has slightly different electrical properties. Bits that were sent simultaneously arrive at slightly different times. At high speeds or over long distances, this makes it impossible to tell which bits belong together.
• Crosstalk: electrical signals in adjacent wires interfere with each other (electromagnetic induction). Causes errors.
• Requires more wires — more expensive cable, more connectors.

Serial transmission: bits sent one at a time, in sequence, over a single channel. Slower bit-by-bit but avoids skew and crosstalk completely. Modern serial interfaces (USB 3.2, PCIe 4.0, SATA) achieve far higher speeds than older parallel standards (IDE parallel ATA) despite sending fewer bits simultaneously, because they can clock much faster.

For receiver to interpret bits correctly, it must know when each bit starts and ends. Two approaches:

Synchronous transmission: sender and receiver share a common clock signal. Data flows as a continuous stream, with each bit occupying exactly one clock period. The receiver samples the line on each clock tick. Efficient for bulk data transfer (HDMI, Ethernet). Requires clock synchronisation between devices.

Asynchronous transmission: no shared clock. Data is sent in short bursts at any time. Each character (or byte) is wrapped in:

• Start bit (always 0): signals "a character is coming — get ready". The receiver detects the change from idle (1) to 0 and starts its internal timer.
• The data bits (usually 7 or 8)
• Stop bit(s) (always 1, sometimes 2): signals "character complete, line returning to idle".

Idle: 1 1 1 1 | START: 0 | DATA: 1 0 0 0 0 0 1 0 | STOP: 1 | Idle: 1 1

Start/stop bits add overhead (10 bits to transmit 8 bits of data) but allow devices to communicate without synchronising clocks first. Used in older serial ports, UART.

Physical star topology: every device connects to a central switch via its own dedicated cable. The switch is intelligent — it maintains a table of (MAC address → port number) and forwards each frame only to the correct destination port.

Logical bus topology: data from any device is broadcast to all devices. Each device checks whether the data is addressed to it; if not, it discards it. This describes how early Ethernet worked and how a hub works today (a hub is essentially a repeater — it broadcasts all received data to all ports).

Crucially: a network can be physically wired as a star (all cables go to a central device) but behave logically as a bus if that central device is a hub rather than a switch. The physical layout describes the cables; the logical layout describes how data flows.

Wi-Fi (IEEE 802.11 family): a wireless LAN standard. Devices need a wireless network adapter (NIC with antenna) and connect to a wireless access point (WAP), which connects to the wired network infrastructure.

The SSID (Service Set Identifier) is the network's human-readable name (e.g. "Home WiFi"). The WAP broadcasts this name so devices can find and connect to it. Disabling SSID broadcast hides the name from automatic scans — devices must know the name to connect. This is a minor security measure; the network is still discoverable by scanning with the right tools.

Why wireless needs Collision Avoidance rather than Detection:

Wired Ethernet uses CSMA/CD (Collision Detection) — if a device detects a collision while transmitting, it stops and retries. Wireless devices cannot detect collisions while transmitting because they can't hear themselves over the power of their own outgoing signal. So wireless uses CSMA/CA (Collision Avoidance) — try to prevent collisions rather than detect them.

CSMA/CA without RTS/CTS:

1. Before transmitting, listen (carrier sense) — is the channel in use?
2. If idle: wait a random backoff period (reduces chance two devices start simultaneously)
3. Transmit
4. Wait for an acknowledgement (ACK) from the receiver
5. No ACK within timeout → assume collision occurred → wait a new random backoff → retry

CSMA/CA with RTS/CTS (Request to Send / Clear to Send):

1. Sender sends a short RTS frame to the access point
2. Access point broadcasts a CTS frame that all devices in range can hear
3. All devices that hear the CTS go silent for the specified duration
4. The sender transmits without interference risk
5. Receiver sends ACK

Why RTS/CTS? The hidden node problem: Device A and Device B are both connected to AP, but can't hear each other (they're on opposite sides of the AP, out of range of each other). Without RTS/CTS, both might detect the channel as idle and transmit simultaneously, causing a collision at the AP that neither detects. RTS/CTS solves this because the CTS is broadcast by the AP — both A and B hear it and know to stay quiet.

Wireless security measures:

• WPA2 / WPA3: encrypt all data transmitted over the wireless link. Uses AES encryption. WPA2 replaced the broken WEP standard. WPA3 is the latest standard.
• SSID broadcast disabled: hides network name from casual discovery.
• MAC address allow list: WAP only accepts connections from pre-approved MAC addresses. Note: MAC addresses can be "spoofed" (faked), so this isn't a strong security measure alone.

Before packet switching, the telephone network used circuit switching: when you made a call, a dedicated physical circuit was established between you and the other person for the entire duration. All resources on that path were reserved, even during silences.

Packet switching works differently: data is broken into small chunks called packets. Each packet is routed independently across the network — different packets from the same transmission may take completely different paths. At the destination, they're reassembled in the correct order.

Packet structure:

A router is a device that forwards packets between networks. Every router maintains a routing table — a list of known network addresses and the best "next hop" to send packets towards their destination. Routers operate at Layer 3 (network layer), using IP addresses.

When a packet arrives at a router:

1. Router reads the destination IP address from the packet header
2. Looks up the routing table to find the best path
3. Forwards the packet to the next router (next hop) on that path
4. The next router repeats this process until the packet reaches its destination

A gateway is a more general concept: a node that allows data to pass between networks that may use different protocols. Your home router is a gateway — it connects your LAN (using private IP addresses) to the internet (using public IP addresses) and handles the protocol translation (NAT).

Computers communicate using IP addresses. Humans prefer domain names like google.com. DNS (Domain Name System) translates between them. It's a globally distributed, hierarchical database — no single server holds all records.

Domain name hierarchy:

www . bbc . co . uk
 ↑    ↑    ↑    ↑
host  domain  SLD  TLD

TLD (Top Level Domain): .uk, .com, .org, .net
Second-level domain (SLD): co (in .co.uk), bbc
Subdomain: www

A Fully Qualified Domain Name (FQDN) specifies the complete host identity: www.bbc.co.uk.
A URL (Uniform Resource Locator) adds the protocol and path: https://www.bbc.co.uk/news/article1.

DNS resolution — step by step:

A firewall monitors and filters incoming and outgoing network traffic based on predetermined security rules. It sits at the boundary between a trusted internal network and an untrusted external network (the internet).

Symmetric encryption: one key used for both encryption and decryption. The same secret key is needed by both parties.

• Fast — efficient algorithms (AES is symmetric)
• Problem: the key distribution problem. How do you securely share the key with the other party? If you send it over an insecure channel, an eavesdropper gets it. If you need a secure channel to share the key, you already have what you need.

Asymmetric encryption: a mathematically linked key pair — public key and private key. What one encrypts, only the other can decrypt. The public key can be shared with anyone; the private key is kept secret.

• Encrypting a message: sender encrypts with recipient's public key. Only the recipient's private key can decrypt it. Even the sender can't decrypt what they just sent.
• Solves key distribution: the public key can be shared openly — there's no risk in anyone knowing it.
• Slower than symmetric encryption — the mathematics (RSA, ECC) are computationally expensive.

A digital certificate is an electronic document that binds a public key to an identity (a website's domain name). It's issued and signed by a trusted Certificate Authority (CA) (e.g. DigiCert, Let's Encrypt). When you visit https://bbc.co.uk, your browser checks: is this certificate signed by a CA I trust? If yes, the public key in the certificate genuinely belongs to bbc.co.uk. Prevents man-in-the-middle attacks.

A digital signature proves a message came from who it claims and hasn't been tampered with:

1. Sender takes the message and computes its hash (a fixed-length "fingerprint" of the content)
2. Sender encrypts the hash with their own private key — this is the digital signature
3. Sender sends: original message + digital signature
4. Receiver decrypts the signature using sender's public key → recovers the hash
5. Receiver independently computes the hash of the received message
6. If the two hashes match → message is authentic and unmodified

Addressing malware — the spec requires knowing three approaches:

• Improved code quality: fewer bugs = fewer vulnerabilities to exploit. Code reviews, testing, formal verification.
• Monitoring: intrusion detection systems, log analysis, anomaly detection to spot attack patterns.
• Protection: antivirus software, firewalls, sandboxing (run suspicious code in an isolated environment), regular security patches.

A socket is a specific communication endpoint, identified by a combination of IP address and port number: 151.101.0.81:443. Every TCP/UDP connection has a source socket and a destination socket. This allows multiple simultaneous connections to the same server — your browser can have many open connections to bbc.co.uk, each with a different client port.

Well-known ports: 0–1023. Reserved for standard services. Require elevated privileges to bind to (on Unix-like systems).

Ephemeral (client) ports: 1024–65535. Assigned temporarily to the client side of a connection. Your browser uses one of these when connecting to a server — e.g. your connection to bbc.co.uk:443 uses bbc.co.uk:443 as destination, and something like 192.168.1.5:52891 as source.

TCP 3-way handshake establishes a connection before data is sent:

IPv4: 32-bit address, written as 4 decimal octets (0–255): 192.168.1.100. Total of 2³² ≈ 4.3 billion unique addresses — exhausted. Every IP address has a network identifier (which network) and host identifier (which device on that network).

IPv6: 128-bit address, written in hexadecimal groups: 2001:0db8:85a3::8a2e:0370:7334. 2¹²⁸ ≈ 3.4×10³⁸ addresses — effectively unlimited. Introduced specifically to solve IPv4 exhaustion.

Subnet mask: defines which part of an IP address is the network ID and which is the host ID. 255.255.255.0 means the first 24 bits are the network, the last 8 bits are the host. All devices sharing the same network portion can communicate directly; others must go via a router.

DHCP (Dynamic Host Configuration Protocol): automatically assigns IP addresses, subnet masks, gateway addresses, and DNS server addresses to devices joining the network. Without DHCP, you'd manually configure every device. The DHCP server maintains a pool of available addresses and leases them for a fixed time.

NAT (Network Address Translation): private IP addresses (e.g. 192.168.x.x) are not routable on the internet — they're used internally only. Your router uses NAT to translate between your private internal addresses and your single public IP address. This also provides a security benefit — external devices can't directly address internal machines.

Port forwarding: when an external request arrives at your router on a specific port, port forwarding tells the router to pass it to a specific internal device. Example: to host a game server on your laptop (192.168.1.50) on port 27015, configure port forwarding: "incoming UDP:27015 → 192.168.1.50:27015". External players connect to your public IP:27015; your router forwards it to your laptop.

WebSocket: standard HTTP is request-response — the client always initiates. The server can't push data to the client unprompted. WebSocket upgrades an HTTP connection to a persistent, full-duplex TCP connection — both sides can send data at any time. Used for live chat, live stock prices, collaborative editing, online games, real-time dashboards.

Web server: serves web pages as text (HTML, CSS, JavaScript). A client requests a URL; the server responds with the file contents.

Web browser: retrieves web pages (via HTTP/HTTPS), interprets HTML/CSS/JavaScript, fetches additional resources (images, scripts), and renders the result visually.

CRUD applications: most web apps perform four basic operations on a database:

REST (Representational State Transfer): an architectural style for building web APIs. The browser's JavaScript calls the REST API on the server using HTTP methods. The server performs the database operation and returns data as JSON or XML.

JSON vs XML comparison:

Thin vs thick client:

An entity is a real-world thing about which data is stored. Entities become tables. Examples: Student, Course, Order, Product.

An attribute is a property of an entity. Attributes become columns (fields) in the table. For a Student entity: StudentID, FirstName, LastName, DateOfBirth.

A primary key (PK) is an attribute (or combination of attributes) that uniquely identifies each row in a table. Rules: must be unique, must not be null (empty), must not change over time. Example: StudentID = 10042 uniquely identifies one student.

A foreign key (FK) is an attribute in one table that refers to the primary key of another table. It creates a link (relationship) between the two tables.

Student table:
StudentID (PK) | FirstName | LastName | DateOfBirth
10042          | Alice     | Smith    | 2007-09-14
10043          | Bob       | Jones    | 2007-11-22

Enrolment table:
EnrolmentID (PK) | StudentID (FK) | CourseCode (FK) | Year
E001             | 10042          | CS01            | 2024
E002             | 10042          | MA01            | 2024
E003             | 10043          | CS01            | 2024

Referential integrity: the rule that every foreign key value must match an existing primary key value in the referenced table. You cannot add an enrolment for StudentID 99999 if no student with that ID exists. Referential integrity prevents "orphaned" records — data that refers to something that doesn't exist.

Composite key: a primary key made from two or more attributes, neither of which is unique on its own, but together they uniquely identify a row. Example: in a table recording which students are in which classes, (StudentID, ClassID) together form a composite key — one student can be in many classes, one class has many students, but no student appears in the same class twice.

An E-R diagram shows entities as rectangles, attributes as ovals (or listed inside the rectangle), and relationships as diamonds or labelled lines. The key feature is the multiplicity — the cardinality of each relationship:

First Normal Form (1NF)

A table is in 1NF if:

• Every cell contains a single, atomic (indivisible) value — no lists of values in one cell
• There are no repeating groups (no multiple columns for the same type of data, e.g. Phone1, Phone2, Phone3)
• All rows are uniquely identifiable (there is a primary key)

NOT 1NF: OrderID | CustomerName | Products
         001     | Alice        | "Pen, Pencil, Ruler"   ← multiple values in one cell

1NF:     OrderID | CustomerName | Product
         001     | Alice        | Pen
         001     | Alice        | Pencil
         001     | Alice        | Ruler

Second Normal Form (2NF)

A table is in 2NF if it is in 1NF AND every non-key attribute is fully functionally dependent on the whole primary key. Partial dependencies (where an attribute depends on only part of a composite key) must be removed.

2NF is only relevant when the primary key is composite — if the PK is a single attribute, and the table is in 1NF, it is automatically in 2NF.

OrderLine(OrderID, ProductID, ProductName, Quantity)
PK = (OrderID, ProductID) — composite

ProductName depends only on ProductID — not on OrderID.
This is a PARTIAL DEPENDENCY → violates 2NF.

Fix — split into:
OrderLine(OrderID, ProductID, Quantity)    ← PK = (OrderID, ProductID)
Product(ProductID, ProductName)            ← PK = ProductID

Third Normal Form (3NF)

A table is in 3NF if it is in 2NF AND there are no transitive dependencies — where a non-key attribute depends on another non-key attribute (rather than directly on the key).

Student(StudentID, CourseID, CourseName, LecturerName)
PK = StudentID

CourseName → depends on CourseID (not on StudentID directly)
LecturerName → depends on CourseID (transitive dependency)

Fix — split into:
Student(StudentID, CourseID)         ← PK = StudentID
Course(CourseID, CourseName, LecturerName)  ← PK = CourseID

-- Basic SELECT
SELECT column1, column2 FROM table WHERE condition;

-- Select all columns
SELECT * FROM Student WHERE LastName = 'Smith';

-- Comparison operators: =, <>, <, >, <=, >=
SELECT * FROM Student WHERE Age >= 16 AND Age <= 18;

-- LIKE for pattern matching: % = any sequence, _ = any single char
SELECT * FROM Student WHERE LastName LIKE 'S%';   -- starts with S
SELECT * FROM Student WHERE Email LIKE '%@school.ac.uk';

-- ORDER BY
SELECT FirstName, LastName FROM Student ORDER BY LastName ASC;
SELECT * FROM Product ORDER BY Price DESC;

-- Wildcard SELECT with condition
SELECT StudentID, FirstName FROM Student
WHERE DateOfBirth BETWEEN '2006-09-01' AND '2007-08-31'
ORDER BY LastName;

JOIN — combining tables

An INNER JOIN returns only rows where there is a matching value in both tables:

SELECT Student.FirstName, Student.LastName, Course.CourseName
FROM Student
INNER JOIN Enrolment ON Student.StudentID = Enrolment.StudentID
INNER JOIN Course ON Enrolment.CourseCode = Course.CourseCode
WHERE Course.CourseName = 'Computer Science'
ORDER BY Student.LastName;

This connects three tables. The ON clause specifies which columns to match. Rows with no match in the other table are excluded.

-- INSERT a new row
INSERT INTO Student (StudentID, FirstName, LastName, DateOfBirth)
VALUES (10044, 'Charlie', 'Brown', '2007-03-05');

-- UPDATE existing rows — ALWAYS use WHERE or you update every row!
UPDATE Student
SET Email = '[email protected]'
WHERE StudentID = 10044;

-- DELETE rows — ALWAYS use WHERE or you delete everything!
DELETE FROM Enrolment
WHERE StudentID = 10044;

A transaction is a sequence of database operations that must be treated as a single, indivisible unit. Example: a bank transfer — debit one account, credit another. Both must happen or neither must happen.

Structured data: has a predefined schema (format) — rows and columns, fixed data types. Easily stored in relational databases. Easy to query with SQL. Example: a database table of customer orders.

Semi-structured data: has some structure (tags or keys) but doesn't fit neatly into tables. Examples: JSON files, XML documents, emails (headers are structured, body is not).

Unstructured data: no predefined format. Cannot be stored meaningfully in a relational database without losing information. Examples: video files, audio recordings, social media posts, images, natural language text, sensor data streams.

Approximately 80–90% of the world's data is unstructured. Processing it requires different tools — machine learning, natural language processing, computer vision — rather than SQL.

MapReduce is a programming model for processing large datasets across a distributed cluster. It was popularised by Google and is the foundation of Apache Hadoop. It works in two phases:

Map phase: The input data is split into chunks. Each chunk is processed by a separate mapper (running on a different machine) which applies a map function to each item, producing (key, value) pairs as output.

Reduce phase: All the (key, value) pairs with the same key are grouped together (shuffle and sort) and passed to a reducer, which combines them to produce the final result.

Input (split across machines):
  Machine 1: "the cat sat on the mat"
  Machine 2: "the cat sat on a hat"

MAP phase — each machine emits (word, 1) for each word:
  Machine 1: (the,1)(cat,1)(sat,1)(on,1)(the,1)(mat,1)
  Machine 2: (the,1)(cat,1)(sat,1)(on,1)(a,1)(hat,1)

SHUFFLE — group by key:
  "the": [1,1,1]   "cat": [1,1]   "sat": [1,1]
  "on":  [1,1]     "mat": [1]     "a":   [1]   "hat": [1]

REDUCE phase — sum each group:
  "the": 3   "cat": 2   "sat": 2   "on": 2
  "mat": 1   "a": 1     "hat": 1

The key insight: the Map phase runs entirely in parallel across all machines. The Reduce phase also runs in parallel (one reducer per unique key group). The framework handles distributing data, coordinating machines, and recovering from individual machine failures — the programmer only writes the map and reduce functions.

Machine learning is a technique where a system learns patterns from data rather than being explicitly programmed with rules. This is central to Big Data because the volume and complexity of the data makes manually writing rules impossible.

Supervised learning: the model is trained on labelled examples (input + correct output). It learns the mapping from input to output. Examples: spam filter (email + spam/not-spam label), image classifier (image + label), fraud detection (transaction + fraud/not-fraud).

Unsupervised learning: the model finds patterns in unlabelled data. Examples: customer segmentation (grouping customers with similar purchasing behaviour without being told how many groups to find), anomaly detection.

Training, validation, and test sets: a dataset is split into three parts. The model is trained on the training set, tuned using the validation set, and its final accuracy measured on the test set (which it has never seen before). This prevents overfitting — a model that memorises the training data but fails on new examples.

A pure function always returns the same output for the same input, and has no side effects — it does not modify any external state, write to disk, print to screen, or change any variable outside itself.

Referential transparency: because pure functions always produce the same output for the same input, a function call can be replaced by its result anywhere in the program without changing the program's behaviour. double 5 can always be replaced by 10. This makes programs easier to reason about and test.

In functional programming, functions are first-class values — they can be:

• Passed as arguments to other functions
• Returned as results from other functions
• Stored in variables or data structures
• Defined anonymously without a name (lambda expressions)

A higher-order function is one that takes a function as an argument, or returns a function as its result (or both).

-- apply takes a function f and a value x, and applies f to x
apply f x = f x

apply double 5     → 10
apply (add 3) 7   → 10

-- A function can be returned:
makeAdder n = \x -> x + n    -- returns a new function
add3 = makeAdder 3
add3 7  → 10

Map

map applies a function to every element of a list and returns a new list of the same length containing the transformed values.

-- Haskell:
map double [1,2,3,4,5]  →  [2,4,6,8,10]
map (*3)   [1,2,3,4,5]  →  [3,6,9,12,15]
map even   [1,2,3,4]    →  [False,True,False,True]

-- Python equivalent:
list(map(lambda x: x*2, [1,2,3,4,5]))  →  [2,4,6,8,10]

Filter

filter takes a predicate (a function that returns True or False) and a list, and returns a new list containing only the elements for which the predicate returns True.

-- Haskell:
filter even [1,2,3,4,5,6]   →  [2,4,6]
filter (>3) [1,2,3,4,5,6]   →  [4,5,6]
filter odd  [1,2,3,4,5]     →  [1,3,5]

-- Python equivalent:
list(filter(lambda x: x % 2 == 0, [1,2,3,4,5,6]))  →  [2,4,6]

Fold / Reduce

foldr (fold right) and foldl (fold left) combine all elements of a list into a single value using an accumulator function and a starting value.

-- foldr f start [a,b,c] = f a (f b (f c start))
foldr (+) 0 [1,2,3,4,5]   →  15   (sum: 1+2+3+4+5)
foldr (*) 1 [1,2,3,4,5]   →  120  (factorial: 5!)
foldr (:) [] [1,2,3]      →  [1,2,3]  (copies the list)

-- Python equivalent (reduce):
from functools import reduce
reduce(lambda acc, x: acc + x, [1,2,3,4,5], 0)  →  15

foldr (+) 0 [1,2,3]
= 1 + (foldr (+) 0 [2,3])
= 1 + (2 + (foldr (+) 0 [3]))
= 1 + (2 + (3 + (foldr (+) 0 [])))
= 1 + (2 + (3 + 0))
= 1 + (2 + 3)
= 1 + 5
= 6

A lambda expression defines a function without giving it a name. Useful when you need a simple function in one place and don't want to define it separately.

-- Haskell lambda syntax: \parameter -> expression
\x -> x * 2         -- a function that doubles its input
\x y -> x + y       -- a function that adds two numbers

-- Usage:
map (\x -> x * 2) [1,2,3,4,5]   →  [2,4,6,8,10]
filter (\x -> x > 3) [1..6]     →  [4,5,6]

-- Python lambda syntax: lambda parameter: expression
double = lambda x: x * 2
add = lambda x, y: x + y
double(5)  →  10

Partial application: providing fewer arguments than a function expects, producing a new function that takes the remaining arguments.

-- add takes two arguments
add x y = x + y

-- Partially apply add with 3 → get a new function "add 3"
add3 = add 3       -- add3 is now a function: y -> 3 + y
add3 7   →  10
add3 20  →  23

-- This is extremely useful with map:
map (add 10) [1,2,3,4,5]   →  [11,12,13,14,15]

Currying: transforming a function that takes multiple arguments into a chain of functions that each take one argument. In Haskell, all functions are automatically curried — add x y = x + y is actually a function that takes x and returns a function that takes y.

-- Non-curried (tuple argument):
addPair (x, y) = x + y
addPair (3, 4)  →  7   -- must pass both arguments at once

-- Curried (automatic in Haskell):
add x y = x + y
add 3 4    →  7         -- pass both
add 3      →  function   -- pass one: partial application

In Haskell, lists are fundamental. A list is either empty [] or a head (first element) followed by a tail (the rest of the list, itself a list).

List ranges: [1..5] → [1,2,3,4,5]. [2,4..10] → [2,4,6,8,10]. [5,4..1] → [5,4,3,2,1].

Recursive functions on lists: FP uses recursion instead of loops. The pattern is: base case (empty list) and recursive case (process head, recurse on tail).

-- Compute the sum of a list recursively:
mySum []     = 0                    -- base case: empty list sums to 0
mySum (x:xs) = x + mySum xs        -- x is head, xs is tail

mySum [1,2,3,4,5]
= 1 + mySum [2,3,4,5]
= 1 + 2 + mySum [3,4,5]
= 1 + 2 + 3 + mySum [4,5]
= 1 + 2 + 3 + 4 + mySum [5]
= 1 + 2 + 3 + 4 + 5 + mySum []
= 1 + 2 + 3 + 4 + 5 + 0
= 15

The pattern (x:xs) in a function definition is called pattern matching. It simultaneously matches the list structure (head:tail) and binds x to the head and xs to the tail.

Purpose: Fully understand the problem before attempting to solve it. Many failed projects failed because the wrong problem was solved.

Activities: Identify the problem and its scope. Gather requirements from stakeholders through interviews, questionnaires, observation. Separate functional requirements (what the system must DO — "the system must allow users to log in") from non-functional requirements (how well it must do it — "the system must respond within 2 seconds"). Create a data model — an abstraction of the real-world objects involved.

Output: A requirements specification. Each requirement must be specific, measurable, and testable. This document becomes the success criteria evaluated against at the end.

Purpose: Plan the solution before implementing it. Translate requirements into a concrete blueprint.

Activities:

• Data structures: what data needs to be stored and how? Records, arrays, database tables?
• Algorithms: design algorithms in pseudocode before coding them. Trace them manually to verify correctness.
• Modular structure: use hierarchy charts to show how the program breaks into subroutines and how they relate. Each module has clearly defined inputs and outputs.
• User interface design: wireframes and mockups of screens. Good UI design reduces user errors and training time.
• Test plan: design tests at the design stage, not after — ensures requirements are actually testable.

Output: Design documentation — pseudocode algorithms, hierarchy charts, data dictionary (description of all data items), UI wireframes, test plan.

Purpose: Translate the design into working code.

Activities: Write code in the chosen language, following the design. Use meaningful identifier names. Add comments explaining non-obvious logic. Test incrementally — test each module as it's written rather than waiting until everything is done (unit testing). Use version control to track changes.

Good practice during implementation:

• Meaningful variable/function names — calculateTotalCost() not calc()
• Consistent indentation and formatting
• Comment complex logic — explain why, not just what
• Modular code — each subroutine does one thing well
• Avoid magic numbers — use named constants

Output: Working, documented source code.

Purpose: Verify the implementation is correct and robust — it produces the right output for all valid inputs, handles edge cases gracefully, and rejects invalid inputs.

Three categories of test data:

Types of testing:

• Unit testing: test each subroutine/module in isolation
• Integration testing: test how modules work together
• System testing: test the complete system against all requirements
• User acceptance testing (UAT): stakeholders confirm the system meets their needs
• Alpha/beta testing: internal vs external user testing before full release

Output: Test evidence — for each test: input data, expected output, actual output, pass/fail, corrective action taken if failed.

Purpose: Assess the finished system against the original requirements. Identify what works well, what doesn't, and what could be improved.

Evaluation criteria:

Output: Evaluation report — for each original requirement, state whether it was met and provide evidence. Identify limitations and suggest future improvements.