Mission 1 · Spec 4.2.1 – 4.2.2
Data structures, arrays and files
Static and dynamic structures, abstract data types, multi-dimensional arrays, and reading and writing text and binary files.
- Starter 5 min
- Learn 15 min
- Lab 15 min
- Quiz 10 min
- Exam 15 min
Open it in Notepad
Open a .txt file in Notepad and you can read it. Open a .jpg or .exe and you see gibberish. Why?
Reveal
A text file stores characters using a character code. A binary file stores data in the same format it has in memory (e.g. raw integers, pixel values), which isn't meant to be read as text.
Key ideas
Static vs dynamic
Static: fixed size, memory allocated at compile time, can waste space. Dynamic: size changes at run time using the heap, efficient use of memory, but needs pointers and has overhead.
Abstract data types
A logical description of data and the operations on it, independent of how it's implemented, e.g. a queue can be built from an array or a linked list.
Arrays
Fixed-size, same type, accessed by index. Multi-dimensional arrays, e.g. a 2D array for a grid or matrix.
Fields, records and files
A file is made of records, each made of fields. Text files store characters and can be read in any editor; binary files store data as it is held in memory, making them compact and fast to process.
2D array explorer
Static or dynamic?
Exam-style questions
1. Compare static and dynamic data structures.
[4 marks]Mark scheme
- Static has a fixed size; dynamic can grow and shrink at run time (1)
- Static may waste memory if not full / can overflow; dynamic only uses the memory it needs (1)
- Dynamic uses the heap and needs pointers, adding overhead (1)
- Static structures allow direct access by index / are simpler to program (1)
2. Explain the difference between a text file and a binary file.
[2 marks]Mark scheme
- A text file stores data as characters using a character set, readable in an editor (1)
- A binary file stores data in the same format as in memory, not human readable, usually more compact (1)
TUTOR NOTES
- Practical: write the same records to a text file and a binary file and compare sizes.
Mission 2 · Spec 4.2.3 – 4.2.4
Queues and stacks
Linear, circular and priority queues; stacks with push, pop and peek; and their uses.
- Starter 5 min
- Learn 15 min
- Lab 20 min
- Quiz 10 min
- Exam 15 min
A&E
In A&E, patients are not always seen in the order they arrive. What decides who goes next?
Reveal
How urgent their need is. That's a priority queue: items are removed in priority order, and first in, first out only among equal priorities.
Key ideas
Queue (FIFO)
enQueue, deQueue, isEmpty, isFull. Linear: front and rear pointers move along; freed space isn't reused. Circular: pointers wrap round using MOD. Uses: print queues, keyboard buffers, BFS.
Priority queue
Items have a priority; the highest-priority item is removed first. Uses: process scheduling, Dijkstra's algorithm.
Stack (LIFO)
push, pop, peek (top), isEmpty, isFull. A stack pointer tracks the top. Uses: undo, call stacks, evaluating RPN, backtracking.
Stack
Linear and circular queues
Priority queue
Exam-style questions
1. Explain why a circular queue is more efficient than a linear queue when implemented with a fixed-size array.
[2 marks]Mark scheme
- In a linear queue, space freed at the front by dequeuing can't be reused (1)
- In a circular queue the rear pointer wraps round to reuse freed space, so the queue only becomes full when every space is used (1)
2. Describe the steps to pop an item from a stack implemented as an array.
[3 marks]Mark scheme
- Check whether the stack is empty; report underflow if so (1)
- Return the item at the position given by the top pointer (1)
- Decrement the top pointer (1)
TUTOR NOTES
- Exam habit: always mention the empty/full check.
Mission 3 · Spec 4.2.2, 4.2.5 – 4.2.6
Graphs and trees
Graph terminology, adjacency matrices and lists, rooted trees and binary trees.
- Starter 5 min
- Learn 15 min
- Lab 20 min
- Quiz 10 min
- Exam 15 min
Friends of friends
How would you store a social network in a computer so you could find friends of friends quickly?
Reveal
As a graph: people are vertices and friendships are edges. It could be stored as a table of every possible pair (adjacency matrix) or as a list of each person's friends (adjacency list).
Key ideas
Graph terms
Vertex/node, edge/arc, weighted graph, directed and undirected graphs.
Adjacency matrix vs list
Matrix: quick to test whether an edge exists; wastes memory for sparse graphs. List: memory-efficient for sparse graphs; slower to test a specific edge.
Trees
A connected, undirected graph with no cycles. A rooted tree has one root, with parent-child relationships. A binary tree is a rooted tree where each node has at most two children.
Uses
Graphs: networks, maps, social media, state machines. Trees: file systems, syntax trees, binary search trees, decision trees.
Binary search tree
Matrix or list?
Exam-style questions
1. Explain the circumstances in which an adjacency list is more appropriate than an adjacency matrix.
[2 marks]Mark scheme
- When the graph is sparse / has few edges relative to nodes (1)
- as only existing edges are stored, saving memory (1)
2. State two properties that make a graph a tree.
[2 marks]Mark scheme
- It is connected (1)
- It has no cycles / is undirected (1)
TUTOR NOTES
- Practical: represent the same small graph both ways on paper.
Mission 4 · Spec 4.2.7 – 4.2.9
Hash tables, dictionaries and vectors
Hashing and collisions, dictionaries of key-value pairs, and vectors: addition, scalar multiplication, dot product and convex combination.
- Starter 5 min
- Learn 15 min
- Lab 20 min
- Quiz 10 min
- Exam 15 min
Instant lookup
How could a program find one username among 10 million in a single step, without searching?
Reveal
Calculate where it should be. A hash function turns the key into an array index, so the item can be found directly, unless two keys collide.
Key ideas
Hash tables
A hashing algorithm maps a key to an index. Collisions are handled by rehashing, e.g. looking for the next free slot. Good hash functions spread keys evenly and are quick to calculate.
Dictionaries
Collections of key-value pairs where the value is accessed by its key, e.g. counting word frequencies. Often implemented with a hash table.
Vectors
Can be represented as a list of numbers, as a function (index → value), or geometrically as an arrow. A 2-vector over ℝ is written ℝ².
Vector operations
Addition: translation. Scalar multiplication: scaling. Convex combination αu + βv with α, β ≥ 0 and α + β = 1. Dot product u·v = u₁v₁ + u₂v₂, used to find the angle between vectors.
Hash table
Vectors
Exam-style questions
1. Calculate the dot product of [3, −2] and [4, 5].
[1 mark]Mark scheme
- 3 × 4 + (−2) × 5 = 2 (1)
2. Explain what a collision is in a hash table and describe one way of handling it.
[3 marks]Mark scheme
- Two different keys hash to the same index (1)
- Rehashing: search for the next available location, e.g. the next free slot (1)
- When searching, the same process is followed until the item or an empty slot is found (1)
TUTOR NOTES
- Lab prompt: drag α in the vector lab; where does the convex combination point move?