Cambridge 9618 · International A Level Computer Science · ~20 min read
Notes
Video
Slides
Quiz
Worksheet
Searching Algorithms
Searching is the process of finding a target value within a dataset. Cambridge 9618 requires knowledge of linear search and binary search.
🔍 Linear Search
O(n) average/worstO(1) best caseWorks on unsorted data
Examine each element in turn from first to last until the target is found or all elements have been checked.
Key facts: Works on ANY data (sorted or unsorted). Simple to implement. O(n) average — on average checks n/2 elements. O(1) best case — target is first element. O(n) worst case — target is last or not present.
// Linear search — Cambridge pseudocode FUNCTIONLinearSearch(Arr, n, target) : INTEGER FORi ← 1TOn IFArr[i] = targetTHEN RETURNi// return index of found element ENDIF NEXTi RETURN -1// not found ENDFUNCTION
🎯 Binary Search
O(log n) average/worstO(1) best caseRequires SORTED data
Repeatedly halve the search space. Compare target with the MIDDLE element. If equal → found. If target < middle → search LEFT half. If target > middle → search RIGHT half. Repeat until found or search space is empty.
Key facts: MUCH faster than linear for large datasets. REQUIRES data to be sorted first. O(log n) — halves search space each step. For n=1,000,000: at most 20 comparisons. In-place (no extra memory needed).
Sorted array: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] — search for 23 Step 1: Low=1, High=10, Mid=5 → Arr[5]=16. 23>16 → search RIGHT → Low=6 Step 2: Low=6, High=10, Mid=8 → Arr[8]=56. 23<56 → search LEFT → High=7 Step 3: Low=6, High=7, Mid=6 → Arr[6]=23. 23=23 FOUND at index 6! ✓
A graph is a data structure consisting of a set of vertices (nodes) connected by edges (arcs). Graphs model relationships — social networks, road maps, computer networks.
🕸️ Graph Terminology
Directed graph (digraph): edges have a direction (A→B ≠ B→A). Represents one-way relationships (web hyperlinks, Twitter follows).
Undirected graph: edges have no direction (A—B = B—A). Represents mutual relationships (Facebook friendships, roads).
Weighted graph: each edge has a numerical value (cost, distance, time). Unweighted: all edges equal.
Path: a sequence of edges connecting two vertices. Cycle: a path that starts and ends at the same vertex. Connected graph: there is a path between every pair of vertices.
Graph Representations
Adjacency Matrix
Graph: A—B, A—C, B—C, B—D
A B C D
A [0, 1, 1, 0]
B [1, 0, 1, 1]
C [1, 1, 0, 0]
D [0, 1, 0, 0]
1=edge exists, 0=no edge
Adjacency List
Same graph:
A → [B, C]
B → [A, C, D]
C → [A, B]
D → [B]
Each vertex: list of neighbours
Property
Adjacency Matrix
Adjacency List
Space complexity
O(V²)
O(V + E)
Check edge (u,v) exists?
O(1)
O(degree of u)
Find all neighbours?
O(V)
O(degree of u)
Best for
Dense graphs
Sparse graphs
Weighted graph
Store weight instead of 1
Store (neighbour, weight) pairs
Breadth-First Search (BFS)
🌊 BFS — Breadth-First Search
Uses a QUEUELevel by levelO(V + E)
Explore the graph LEVEL BY LEVEL from the start vertex. Visit all immediate neighbours first, then their unvisited neighbours, and so on. Uses a QUEUE (FIFO).
Applications: Finding the SHORTEST PATH in an unweighted graph, social network friend suggestions (degrees of separation), web crawling level by level, broadcasting in computer networks.
Graph: A—B, A—C, B—D, B—E, C—F. BFS from A:
Start: Queue=[A], Visited=[A] Dequeue A: Visit A. Enqueue unvisited neighbours B, C → Queue=[B, C] Visited=[A,B,C] Dequeue B: Visit B. Enqueue unvisited neighbours D, E → Queue=[C, D, E] Visited=[A,B,C,D,E] Dequeue C: Visit C. Enqueue unvisited neighbour F → Queue=[D, E, F] Visited=[A,B,C,D,E,F] Dequeue D: Visit D. No unvisited neighbours → Queue=[E, F] Dequeue E: Visit E. No unvisited neighbours → Queue=[F] Dequeue F: Visit F. No unvisited neighbours → Queue=[] DONE!
BFS order: A → B → C → D → E → F
// BFS — pseudocode PROCEDUREBFS(Graph, start) Enqueue(Queue, start) MarkVisited(start) WHILENOTIsEmpty(Queue) current ← Dequeue(Queue) Process(current) // e.g. print or record FOR EACHneighbourOFcurrent IF NOTVisited(neighbour) THEN Enqueue(Queue, neighbour) MarkVisited(neighbour) ENDIF NEXT ENDWHILE ENDPROCEDURE
Depth-First Search (DFS)
🌲 DFS — Depth-First Search
Uses a STACK (or recursion)Deep first, then backtrackO(V + E)
Explore AS DEEP AS POSSIBLE along each branch before backtracking. Uses a STACK (LIFO) — or recursion (which uses the call stack implicitly).
Applications: Maze solving (explore one path fully then backtrack), topological sort, cycle detection, solving puzzles, tree traversal (in-order, pre-order, post-order are all DFS), finding strongly connected components.
Same graph: A—B, A—C, B—D, B—E, C—F. DFS from A:
Start: Stack=[A], Visited=[] Pop A: Visit A. Push unvisited neighbours C, B (reversed order) → Stack=[C, B] Visited=[A] Pop B: Visit B. Push unvisited E, D → Stack=[C, E, D] Visited=[A,B] Pop D: Visit D. No unvisited → Stack=[C, E] Visited=[A,B,D] Pop E: Visit E. No unvisited → Stack=[C] Visited=[A,B,D,E] Pop C: Visit C. Push F → Stack=[F] Visited=[A,B,D,E,C] Pop F: Visit F. No unvisited → Stack=[] DONE!
DFS order: A → B → D → E → C → F (order depends on push order)
// DFS iterative (using explicit stack) PROCEDUREDFS(Graph, start) Push(Stack, start) WHILENOTIsEmpty(Stack) current ← Pop(Stack) IF NOTVisited(current) THEN MarkVisited(current) Process(current) FOR EACHneighbourOFcurrent IF NOTVisited(neighbour) THEN Push(Stack, neighbour) ENDIF NEXT ENDIF ENDWHILE ENDPROCEDURE
BFS vs DFS Comparison
Feature
BFS
DFS
Data structure
Queue (FIFO)
Stack (LIFO) or recursion
Explores
Level by level
Depth first, then backtrack
Shortest path?
✅ Yes (unweighted graphs)
❌ Not guaranteed
Memory usage
O(V) — can be large for wide graphs
O(V) — can be large for deep graphs
Time complexity
O(V + E)
O(V + E)
Good for
Shortest path, peer networks
Maze solving, topological sort, cycle detection
Cambridge 9618 exam tip: BFS uses a QUEUE — remember this by thinking "queue up at the door, process people level by level". DFS uses a STACK — "stack of plates, go as deep as possible". When tracing BFS or DFS, always maintain the visited set to avoid revisiting nodes — failure to mark a node visited when it is added to the queue/stack (not when it is processed) causes duplicates. For adjacency matrix vs adjacency list: matrix = O(V²) space but O(1) edge lookup; list = O(V+E) space but better for sparse graphs. Know both representations and be able to draw either from a graph diagram.
⚠️ Common Mistakes
Binary search on unsorted data — binary search ONLY works on sorted data. If data is unsorted, you MUST sort it first (or use linear search). Remember: the whole algorithm depends on knowing which half to discard.
BFS vs DFS data structures confused — BFS = QUEUE (first in, first out → explore level by level). DFS = STACK (last in, first out → go deep first). Many students reverse these in exams.
Not marking nodes visited in BFS/DFS — without a visited set, the algorithm will loop infinitely in cyclic graphs. In BFS, mark a node visited WHEN IT IS ADDED TO THE QUEUE, not when it is dequeued.
Adjacency matrix diagonal — the diagonal of an adjacency matrix (where row = column, i.e. Arr[i][i]) is always 0 for a simple graph (no self-loops). Forgetting this is a common mistake when drawing the matrix.
Binary search mid calculation — Mid = (Low + High) DIV 2. After finding target < mid: set High = Mid - 1 (not Mid). After target > mid: set Low = Mid + 1 (not Mid). Off-by-one errors here cause infinite loops.
✅ Notes completed!
▶
Video coming soon
Click slide or press arrow keys to navigate
Worksheet — 4.4.2 Searching & Graph Algorithms
8 questions · Cambridge 9618 standard
Q1Trace binary search on sorted array [3, 7, 12, 19, 24, 31, 45, 58, 67, 80] searching for 31. Show Low, High, Mid and the comparison at each step.[4]
✅ Mark scheme
Step 1: Low=1, High=10, Mid=(1+10) DIV 2 = 5, Arr[5]=24. 31>24 → Low=6 [1]; Step 2: Low=6, High=10, Mid=(6+10) DIV 2 = 8, Arr[8]=58. 31<58 → High=7 [1]; Step 3: Low=6, High=7, Mid=(6+7) DIV 2 = 6, Arr[6]=31. 31=31 → FOUND at index 6 [1]; Took 3 comparisons (binary search on 10 items takes at most 4 comparisons = ceil(log₂10)) [1]. Award 1 per correct step showing Low/High/Mid values and comparison decision.
Q2State TWO differences between linear search and binary search. For each difference, explain when each is more appropriate.[4]
✅ Mark scheme
Difference 1: Binary search requires SORTED data; linear search works on any (unsorted or sorted) data [1]. Appropriate: linear search is more appropriate when data is not already sorted (sorting to use binary search might cost more than just linearly searching); binary search is more appropriate when data is already sorted and searching is frequent (sort once, search many times efficiently) [1]; Difference 2: Time complexity — linear search is O(n) average; binary search is O(log n) [1]. Appropriate: for very small datasets (<10 elements), linear search is simpler and the difference is negligible; binary search is dramatically better for large datasets (1 million elements: linear≈500,000 comparisons avg; binary≈20 comparisons max) [1].
Q3Draw the adjacency matrix and adjacency list for the following undirected graph: Vertices {A, B, C, D, E}. Edges: A-B, A-C, B-D, C-D, D-E.[4]
✅ Mark scheme
Adjacency matrix (5×5, 0=no edge, 1=edge) [2]: A B C D E / A[0,1,1,0,0] / B[1,0,0,1,0] / C[1,0,0,1,0] / D[0,1,1,0,1] / E[0,0,0,1,0]. Note: matrix is symmetric (undirected graph), diagonal is all 0. Award 1 for correct structure/labels, 1 for all correct values; Adjacency list [2]: A→[B,C] / B→[A,D] / C→[A,D] / D→[B,C,E] / E→[D]. Award 1 for correct structure, 1 for all correct entries. Minor ordering variations acceptable — content must be correct.
Q4Trace BFS on the graph from Q3 starting from vertex A. Show the queue state and visited list at each step.[4]
✅ Mark scheme
Start: Enqueue A. Queue=[A], Visited=[] [1]; Dequeue A, mark visited, enqueue B,C. Queue=[B,C], Visited=[A] [1]; Dequeue B, mark visited, enqueue D (A already visited). Queue=[C,D], Visited=[A,B] [1]; Dequeue C, mark visited. D already in queue. Queue=[D], Visited=[A,B,C] [1]; Dequeue D, mark visited, enqueue E. Queue=[E], Visited=[A,B,C,D]; Dequeue E, mark visited. Queue=[], Visited=[A,B,C,D,E] — DONE. BFS order: A, B, C, D, E. Award 1 per correct step showing queue and visited. Minor variations in order acceptable (B,C vs C,B) if consistent. Key: all neighbours of a level are visited before going deeper.
Q5Trace DFS on the same graph from Q3 starting from vertex A. Show the stack state and visited list at each step. Use alphabetical order when pushing neighbours.[4]
✅ Mark scheme
Start: Push A. Stack=[A], Visited=[] [1]; Pop A: mark visited. Push unvisited neighbours in reverse alpha (C then B, so B pops first). Stack=[C,B], Visited=[A] [1]; Pop B: mark visited. Push D (A visited). Stack=[C,D], Visited=[A,B] [1]; Pop D: mark visited. Push E (B,C in stack or visited). Stack=[C,E], Visited=[A,B,D] [1]; Pop E: mark visited. Stack=[C], Visited=[A,B,D,E]; Pop C: mark visited. Stack=[], Visited=[A,B,D,E,C] — DONE. DFS order: A, B, D, E, C. Key difference from BFS: DFS goes deep (A→B→D→E) before visiting C. Award 1 per correct step showing stack and visited.
Q6Explain why BFS guarantees the shortest path in an unweighted graph, but DFS does not. Give an example to illustrate.[4]
✅ Mark scheme
BFS explores ALL vertices at distance d from the source before exploring any vertex at distance d+1; this means the first time BFS reaches the destination, it must have taken the shortest possible number of edges [1]; BFS uses a FIFO queue — vertices are processed in the order they were discovered, and since all edges are equal weight, earlier-discovered = fewer hops = shorter path [1]; DFS instead dives deep along one path and may reach the destination via a long indirect route before exploring the short direct route [1]; Example: Graph A—B, A—C, C—D, B—D. Shortest path A to D = 2 hops (A→B→D or A→C→D). DFS might explore A→C→D (2 hops ✓) — fine here. But in A—B—C—D with also A—D: DFS might go A→B→C→D (3 hops) before finding A→D (1 hop). BFS always finds A→D first (1 hop) because it processes all distance-1 neighbours before distance-2 [1]. Note: for WEIGHTED graphs, use Dijkstra's algorithm — BFS does not handle weights.
Q7A graph has nodes A, B, C, D, E with edges: A-B, A-C, B-D, C-D, D-E. Perform a Breadth-First Search starting at A. List the order in which nodes are visited and show the queue contents after each step.[5]
✅ Mark scheme
Visit A, enqueue B, C → Queue: [B, C] [1]; Dequeue B, visit B, enqueue D → Queue: [C, D] [1]; Dequeue C, visit C, D already queued → Queue: [D] [1]; Dequeue D, visit D, enqueue E → Queue: [E] [1]; Dequeue E, visit E → Queue: [] [1]; Visit order: A, B, C, D, E. Accept equivalent correct working.
Q8State two differences between Breadth-First Search and Depth-First Search. Explain why BFS is preferred for finding the shortest path in an unweighted graph, and give a real-world application of each algorithm.[6]
✅ Mark scheme
Difference 1: BFS uses a queue (FIFO); DFS uses a stack (LIFO) [1]; Difference 2: BFS explores level by level (all neighbours first); DFS explores as deep as possible along one branch before backtracking [1]; BFS visits all nodes at distance d before visiting any at distance d+1, so the first time it reaches the destination it has taken the shortest path [1]; BFS application: social network friend suggestions (shortest connection between users) [1]; DFS application: maze solving / detecting cycles in a graph / topological sort [1]; award 1 further mark for clear, correct justification of a stated application [1].
Topic Quiz
Question 1 of 10
You scored
out of 10
Card 1 of 8
Click to reveal definition
🎉
All cards reviewed!
Term
Definition
🎯
Mini Test — 4.4.2
10 questions · 10 marks · 10 minutes
⏱ 10:00
Section A — Multiple Choice [5 marks]
Q1Binary search requires data to be in what order?
Q2Which data structure does BFS use to keep track of vertices to visit?
Q3What is the time complexity of binary search?
Q4An adjacency matrix for a graph with V vertices uses how much space?
Q5Which algorithm is most suitable for finding the SHORTEST path in an unweighted graph?
Section B — Short Answer [5 marks]
Q6State the Mid value at each step of binary search on array [10, 20, 30, 40, 50, 60, 70, 80] (indices 1-8) searching for 70. Show Low, High, Mid at each step.
Mark schemeStep 1: Low=1, High=8, Mid=(1+8) DIV 2=4, Arr[4]=40. 70>40 → Low=5 [1]; Step 2: Low=5, High=8, Mid=(5+8) DIV 2=6, Arr[6]=60. 70>60 → Low=7 [1]; Step 3: Low=7, High=8, Mid=(7+8) DIV 2=7, Arr[7]=70. 70=70 → FOUND at index 7 [1]. Three steps/comparisons to find element at index 7 of 8 elements. Award 1 per correct step.
Q7Draw the adjacency list for a directed graph with vertices {P, Q, R, S} and directed edges P→Q, P→R, Q→S, R→Q.
Mark schemeP → [Q, R] [1]; Q → [S] [1]; R → [Q] [1]; S → [] (no outgoing edges) [1]. Note: directed graph — edges are ONE-WAY only. P→Q does NOT mean Q→P. S has no outgoing edges so its list is empty (but S still appears as a vertex). Award 1 per correct row. 3 marks for 3+ correct rows.
Q8Explain why a visited set/array is necessary when running BFS or DFS on a graph that contains cycles.
Mark schemeA cycle in a graph means there is a path from a vertex back to itself; without a visited set, when the algorithm reaches a vertex it has already processed, it will add that vertex (and its neighbours) to the queue/stack again [1]; this leads to an infinite loop — the same vertices are visited repeatedly, the queue/stack never empties, and the algorithm never terminates [1]; the visited set records which vertices have already been explored so the algorithm skips them on subsequent encounters — this ensures each vertex is processed exactly once, giving O(V+E) time complexity [1]. Example: graph with edge A—B and B—A (undirected A—B): without visited, BFS goes A→B→A→B→... forever.
Q9State one advantage of an adjacency list over an adjacency matrix for a SPARSE graph (few edges).
Mark schemeSpace efficiency: an adjacency matrix always requires V² space regardless of the number of edges; for a sparse graph with few edges, most of the V² cells are 0 — wasted space [1]; an adjacency list only stores existing edges: O(V+E) space; for a sparse graph where E << V², this is dramatically smaller [1]. Example: a social network with 1 million users but average 100 friends: matrix = 10¹² cells; list = ~10⁸ entries (10⁶ × 100). Another advantage: iterating over a vertex's neighbours takes O(degree) time in adjacency list vs O(V) time in adjacency matrix — faster for sparse graphs [accept as alternative].
Q10DFS is described as using a stack or recursion. Explain how recursion implements DFS without an explicit stack.
Mark schemeWhen DFS is implemented recursively, each recursive call processes one vertex and then calls DFS on each unvisited neighbour [1]; the CALL STACK of the program acts as the implicit stack — each recursive call is pushed onto the call stack when made, and popped when the function returns; this gives exactly the same LIFO behaviour as an explicit stack [1]; the base case is when a vertex has no unvisited neighbours — the function returns (pops from call stack) and the algorithm backtracks to the previous call automatically [1]. Disadvantage: recursion can cause a stack overflow for very deep graphs (long paths) — O(V) recursive calls deep. Iterative DFS with an explicit stack avoids this.