Define sets and perform union, intersection and difference operations
Explain maps (dictionaries) and use key-value pairs
Represent graphs as adjacency matrices and adjacency lists
Implement breadth-first search (BFS) and depth-first search (DFS) in code/pseudo-code
Sets
Sets in Programming
A set is an unordered collection of unique elements — no duplicates allowed. Sets support mathematical set operations. In Python: A = {1, 2, 3}.
Union A ∪ B
All elements in A OR B (or both). Python: A | B or A.union(B)
Intersection A ∩ B
Only elements in BOTH A AND B. Python: A & B or A.intersection(B)
Difference A − B
Elements in A but NOT in B. Python: A - B or A.difference(B)
Membership
Test if element is in set: x in A. O(1) average time — much faster than searching a list O(n)
Maps (Dictionaries)
Maps: Key-Value Pairs
A map (called a dictionary in Python) stores data as key-value pairs. Each key maps to exactly one value. Keys are unique and immutable; values can be any type. Average O(1) lookup by key using a hash function internally.
d[key] — get value d[key] = val — add/update del d[key] — remove key in d — membership test d.keys() / d.values() — iterate KeyError if key doesn't exist
Graph Representation
Representing Graphs in Code
Adjacency Matrix
2D array. Row i, column j = weight (or 1/0 for unweighted). O(V²) space. Fast to check if an edge exists — O(1). Inefficient for sparse graphs (wastes memory on zeros).
Adjacency List
Dictionary of lists. Each node maps to its neighbours. O(V+E) space — efficient for sparse graphs. Slower to check edge existence — must scan the list. Better for most real-world graphs.
from collections import deque def bfs(graph, start): visited=set(); q=deque([start]) visited.add(start) while q: node=q.popleft() for n in graph[node]: if n not in visited: visited.add(n); q.append(n)
DFS — uses a Stack (or recursion)
def dfs(graph, start, visited=None): if visited is None: visited=set() visited.add(start) for n in graph[start]: if n not in visited: dfs(graph, n, visited) return visited
BFS vs DFS Comparison
When to Use BFS vs DFS
BFS — Breadth-First Search
Uses a queue; explores layer by layer. Guarantees the shortest path in an unweighted graph. Uses more memory (must store all nodes at the current level). Best for: finding nearest neighbour, shortest path problems.
DFS — Depth-First Search
Uses a stack (or recursion); explores as deep as possible before backtracking. Does NOT guarantee shortest path. Uses less memory. Best for: detecting cycles, topological sort, maze solving, connected components.
Both have time complexity O(V+E) for adjacency list representation, where V = vertices and E = edges.
Exam Practice
OCR H446 Style · 4 marks
A social network stores users and their connections as a graph. State and justify which graph representation (adjacency matrix or adjacency list) is more appropriate, and explain which traversal algorithm (BFS or DFS) should be used to find the shortest connection between two users.
[4 marks]
2
Adjacency list — social networks are sparse (each user has relatively few connections compared to total users). An adjacency list uses O(V+E) space versus O(V²) for a matrix. For millions of users, this saves enormous memory. An adjacency matrix would be mostly zeros — a waste of space.
2
BFS — BFS explores all direct connections before moving to second-degree connections etc. This guarantees it finds the shortest path (fewest intermediate connections) between two users in an unweighted graph, since it explores level by level.
Common Mistakes
Don't Lose Marks
!
Saying BFS finds the shortest path in any graph — BFS guarantees shortest path only in unweighted graphs (or graphs where all edge weights are equal). In weighted graphs, Dijkstra's algorithm is needed. Stating "shortest path" without the "unweighted" qualifier is technically incorrect for H446.
!
Confusing sets and lists — sets are unordered and contain unique elements; lists are ordered and allow duplicates. Saying "a set stores elements in insertion order" is wrong. Python 3.7+ dicts maintain insertion order, but sets do not.
!
Choosing adjacency matrix for sparse graphs — students often say "matrix is better because you can look up edges quickly" without considering memory. For sparse real-world graphs (social networks, road maps), adjacency lists are almost always the correct answer in an exam context.