Advanced Algorithms: Searching, Sorting and Path-Finding - Worksheets, Questions and Revision

12 original exam-style questions - 12 pages of questions with a full mark scheme - free printable PDF.

Download PDF Jump to mark scheme (page 13)Read the revision guide

Next in this strand

Revision Library

revisionlibrary.co.uk

A-Level · Component 02: Algorithms and Programming

A2.6 Advanced Algorithms: Searching, Sorting and Path-Finding

OCR H446 · Calculators not allowed · about 155 minutes

Total Marks

Name: _______________________________ Date: ____ / ____ / ______

Answer ALL questions. Show all your working.

A vintage record shop in Brighton stores its catalogue of vinyl records as an array of catalogue numbers, kept sorted in ascending order. All arrays in this paper are indexed from 0, so an array with n items has indices 0 to n - 1. Pseudocode follows OCR's Exam Reference Language conventions (assignment <-, iteration FOR ... NEXT / WHILE ... ENDWHILE, selection IF ... ENDIF).

catalogueNumbers = [102, 118, 125, 130, 144, 151, 168, 172, 190, 205, 211, 230] (indices 0 to 11)

FUNCTION BinarySearch(list, target) RETURNS INTEGER
  low <- 0
  high <- LEN(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
    ELSE
      high <- mid - 1
    ENDIF
  ENDWHILE
  RETURN -1
ENDFUNCTION

(a)State one precondition that must be true about an array before binary search can be used on it correctly.(1)

(b)Complete the trace table below for the call BinarySearch(catalogueNumbers, 172).

low	high	mid	list[mid]	comparison result

(4)

(c)State the value returned by the function call, and the number of comparisons of list[mid] with the target that were made.(2)

(d)The shop's catalogue grows to 2000 records, kept sorted. Using the formula ceil(log2(n + 1)) for the maximum number of comparisons binary search needs on a sorted list of n items, calculate the maximum number of comparisons needed to search the 2000-record catalogue.(2)

(e)Calculate the maximum number of comparisons linear search would need on the same 2000-record catalogue if a scanned record is not present, and state, with a reason based on Big O notation, which search algorithm is more time-efficient for this catalogue.(3)

(Total for Question 1 is 12 marks)

Both bubble sort and insertion sort can be optimised to recognise when a list is fully sorted and stop early. The list [1, 2, 3, 8, 4, 5] is nearly sorted: only the value 8 is out of place.

PROCEDURE BubbleSort(list)
  n <- LEN(list)
  DO
    swapped <- FALSE
    FOR i <- 0 TO n - 2
      IF list[i] > list[i + 1] THEN
        temp <- list[i]
        list[i] <- list[i + 1]
        list[i + 1] <- temp
        swapped <- TRUE
      ENDIF
    NEXT i
    n <- n - 1
  UNTIL swapped = FALSE
ENDPROCEDURE

FUNCTION InsertionSort(list)
  FOR i <- 1 TO LEN(list) - 1
    current <- list[i]
    j <- i - 1
    WHILE j >= 0 AND list[j] > current
      list[j + 1] <- list[j]
      j <- j - 1
    ENDWHILE
    list[j + 1] <- current
  NEXT i
ENDFUNCTION

(a)Complete the trace table below for BubbleSort([1, 2, 3, 8, 4, 5]), showing the list contents, whether any swap occurred, at the end of each pass, and the total number of comparisons made in that pass.

pass	list at end of pass	swapped	comparisons this pass
1
2

(4)

(b)Complete the trace table below for InsertionSort([1, 2, 3, 8, 4, 5]), showing the value of current and the number of comparisons made against list[j] for each value of i. (For i = 1, 2 and 3, current is already in the correct place and no shifts occur.)

i	current	comparisons made	list at end of this iteration
1	2	1	[1, 2, 3, 8, 4, 5]
2	3	1	[1, 2, 3, 8, 4, 5]
3	8	1	[1, 2, 3, 8, 4, 5]
4
5

(4)

(c)State the total number of comparisons made by each algorithm across the whole sort, and state which algorithm required fewer comparisons to sort this nearly-sorted list.(3)

(d)Explain, with reference to your answers to part (c), why insertion sort is often preferred over bubble sort when sorting data that is already nearly in order, even though both algorithms have the same O(n²) worst-case time complexity.(2)

(Total for Question 2 is 13 marks)

The table below covers the searching and sorting algorithms studied so far in this topic.

(a)Complete the table below, giving the worst-case time complexity and the best-case time complexity (assuming any early-exit optimisation is used) of each algorithm, using Big O notation.

Algorithm	Worst-case	Best-case
Linear search
Binary search
Bubble sort
Insertion sort
Merge sort

(5)

(b)State which of the five algorithms in the table are described as adaptive (perform noticeably better on data that is already sorted or nearly sorted than their worst case), and explain why merge sort does not have this property.(3)

(Total for Question 3 is 8 marks)

The maximum number of key comparisons needed by merge sort to fully sort a list of n elements (where n is a power of 2) satisfies the recurrence relation:

C(n) = 2 x C(n / 2) + (n - 1), with C(1) = 0

This reflects recursively sorting two half-lists, each needing C(n/2) comparisons, and then merging the two sorted halves together using at most (n - 1) comparisons.

(a)Use the recurrence relation to calculate C(2), C(4) and C(8), showing your working at each stage.(3)

(b)It can be shown that, for n a power of 2, C(n) = n x log2(n) - n + 1. Verify that this formula gives the same value for C(8) as your answer to part (a).(2)

(c)Use the closed-form formula from part (b) to calculate C(16) and C(64), without using the recurrence relation directly.(4)

(d)A list of 64 elements is sorted using merge sort, then a second list of 64 elements is sorted using an O(n²) algorithm such as bubble sort, which needs up to n(n - 1) / 2 comparisons in the worst case. Calculate this worst-case number of comparisons for n = 64, and comment on what the comparison with your answer for C(64) shows about the relative growth rates of O(n log n) and O(n²).(3)

(Total for Question 4 is 12 marks)

The list [8, 3, 10, 1, 6, 14, 4] is sorted using the version of quicksort below, which always chooses the first element of the current list as the pivot.

FUNCTION QuickSort(list) RETURNS ARRAY
  IF LEN(list) <= 1 THEN
    RETURN list
  ENDIF
  pivot <- list[0]
  less <- []
  greaterEq <- []
  FOR i <- 1 TO LEN(list) - 1
    IF list[i] < pivot THEN
      APPEND(less, list[i])
    ELSE
      APPEND(greaterEq, list[i])
    ENDIF
  NEXT i
  RETURN QuickSort(less) + [pivot] + QuickSort(greaterEq)
ENDFUNCTION

(a)State the pivot used, and the resulting less and greaterEq lists, for the first call QuickSort([8, 3, 10, 1, 6, 14, 4]).(3)

(b)The algorithm then recursively calls QuickSort(less) and QuickSort(greaterEq). Complete the table below giving the pivot and the resulting less and greaterEq lists produced at each further recursive call on a list of more than one element.

call	input list	pivot	less	greaterEq
2	[3, 1, 6, 4]
3	[6, 4]
4	[10, 14]

(4)

(c)State the final sorted list returned by QuickSort([8, 3, 10, 1, 6, 14, 4]), and calculate the total number of element-to-pivot comparisons made across the whole sort (i.e. summing the comparisons made in every recursive call).(3)

(d)State the average-case time complexity of quicksort, and explain briefly why this typically holds when, as in this example, the pivot splits the list into two roughly similar-sized parts at each level of recursion.(2)

(Total for Question 5 is 12 marks)

The same QuickSort algorithm from the previous question (pivot always chosen as list[0]) is now applied to a list that is already sorted in ascending order: [2, 5, 7, 9, 12, 15] (6 elements).

(a)State the pivot, and the resulting less and greaterEq lists, for the first call QuickSort([2, 5, 7, 9, 12, 15]).(2)

(b)Explain why, for this sorted input with this pivot-choice strategy, every recursive call will produce an empty less list and a greaterEq list containing all of the remaining elements.(2)

(c)Complete the table below showing the number of element-to-pivot comparisons made at each level of recursion, continuing until the list is fully sorted, and state the total number of comparisons made overall.

level	list size at this level	comparisons made
1	6	5
2	5
3	4
4	3
5	2
6	1

(3)

(d)Show that, in general, this worst-case total number of comparisons for a sorted list of n elements is n(n - 1) / 2, and state the resulting Big O time complexity.(3)

(e)State two different strategies for choosing the pivot that would make this particular worst-case scenario (an already-sorted list) far less likely to occur in practice.(2)

(Total for Question 6 is 12 marks)

A courier company's road network is modelled as a weighted graph. Vertices A to F represent depots, and edge weights represent journey times in minutes between directly connected depots:

Edges: A-B: 4, A-C: 2, B-C: 1, B-D: 5, C-D: 8, C-E: 10, D-E: 2, D-F: 6, E-F: 3

Dijkstra's algorithm is used to find the shortest journey time from depot A to every other depot.

(a)State one condition that all edge weights in a graph must satisfy for Dijkstra's algorithm to correctly find shortest paths.(1)

(b)Complete the table below to trace Dijkstra's algorithm starting from A. At each step, give the vertex settled and the current shortest known distance to each vertex (write "-" if a distance is not yet known). The first row is completed for you.

step	vertex settled	A	B	C	D	E	F
1	A	0	4	2	-	-	-
2
3
4
5
6

(5)

(c)State the shortest journey time from A to F, and give the corresponding path of depots visited.(2)

(d)Explain how the path found in part (c) can be reconstructed from the completed table, without the algorithm needing to store the whole path directly as it runs.(2)

(Total for Question 7 is 10 marks)

Dijkstra's algorithm can be implemented in different ways, giving different overall time complexities. Let V be the number of vertices and E the number of edges in the graph.

(a)State the overall time complexity of Dijkstra's algorithm when implemented using an adjacency matrix, where finding the next unvisited vertex with the smallest tentative distance requires scanning all V vertices, and this scan is repeated once for each of the V vertices settled.(2)

(b)State the overall time complexity of Dijkstra's algorithm when implemented using an adjacency list together with a min-heap (priority queue) to select the next vertex, where each of the E edges may cause one O(log V) update to the heap.(2)

(c)The courier network in the previous question has V = 6 vertices and E = 9 edges. Calculate the approximate number of operations each implementation from parts (a) and (b) would require.(4)

(d)State, with a reason, which implementation would be expected to show a clearer advantage as the size of the network grows very large, assuming the network stays sparse (E grows roughly in proportion to V, rather than to V²).(2)

(Total for Question 8 is 10 marks)

The same courier network from the previous two questions is now searched using the A* algorithm to find the shortest journey time from A to F. Straight-line distance estimates (heuristic values) to F are given below, and are known to be admissible (never greater than the true remaining journey time to F):

h(A) = 9, h(B) = 7, h(C) = 8, h(D) = 4, h(E) = 2, h(F) = 0

At each step, A* expands the vertex in the open list with the smallest value of f(vertex) = g(vertex) + h(vertex), where g(vertex) is the shortest distance found so far from A to that vertex.

(a)Calculate f(A) at the start of the search, given g(A) = 0.(1)

(b)A is expanded first. Calculate g, h and f for its neighbours B and C once A has been expanded.(2)

(c)Complete the table below to continue the A* trace, showing which vertex is expanded at each step and the resulting g and f values of any vertices whose distance is improved as a result. The first two steps are shown.

step	vertex expanded	updated vertices (g, f)
1	A	B: g=4, f=11 ; C: g=2, f=10
2	C	B: g=3, f=10 ; D: g=10, f=14 ; E: g=12, f=14
3
4
5
6

(4)

(d)State the total journey time and the path found by A* from A to F, and compare this result with the result obtained using Dijkstra's algorithm in the earlier question.(3)

(e)State the total number of vertices expanded by A* in this trace, and comment on whether this shows an efficiency advantage over Dijkstra's algorithm for this particular graph.(3)

(Total for Question 9 is 13 marks)

A satnav app calculates driving routes across a national road network containing millions of junctions.

(a)Discuss the relative advantages of using Dijkstra's algorithm compared with the A* algorithm for calculating a single driving route between two specific junctions in this network, and describe one situation in which Dijkstra's algorithm would still be the more appropriate choice.(8)

(Total for Question 10 is 8 marks)

An admissible heuristic h(v) for a search from vertex v to a goal G never overestimates the true shortest remaining distance from v to G, i.e. h(v) ≤ actualDistance(v, G) always. A consistent (monotone) heuristic additionally satisfies h(u) ≤ cost(u, v) + h(v) for every edge (u, v). A* is only guaranteed to find the shortest path when its heuristic is admissible.

(a)In the courier network used earlier in this paper, the true shortest remaining journey time from D to F is 5 minutes, and from E to F is 3 minutes. State, with a reason, whether the heuristic values h(D) = 4 and h(E) = 2 used earlier are each admissible.(2)

(b)Show that the heuristic values h(D) = 4 and h(E) = 2 satisfy the consistency condition for the edge D-E (weight 2).(2)

(c)A much simpler graph has three vertices: S (start), X, and G (goal), plus a fourth vertex Y. Edges: S-X weight 1, X-G weight 5, S-Y weight 1, Y-G weight 1. The true shortest distance from S to G is therefore 2 (via Y: S-Y-G), not 6 (via X: S-X-G). Suppose A* is run using the heuristic values h(X) = 0 and h(Y) = 10 (note: h(Y) = 10 is NOT admissible, since the true remaining distance from Y to G is only 1). Complete the trace below to show which vertex A* expands at each step, and state the path and total distance A* returns.

step	vertex expanded	g, f of vertices reached
1	S	X: g=1, f=1 ; Y: g=1, f=11
2
3

(6)

(d)State what this example demonstrates about the importance of the admissibility condition for A* to guarantee an optimal (shortest) result.(1)

(Total for Question 11 is 11 marks)

A warehouse robot navigates a grid-shaped map with R rows and C columns of cells. Each cell is connected to its (up to 4) directly adjacent cells (up, down, left, right), forming a graph where each cell is a vertex.

(a)State, in terms of R and C, the number of vertices V in this graph.(1)

(b)Show that the number of edges E in this grid graph is given by E = R(C - 1) + C(R - 1).(2)

(c)The warehouse grid has R = 100 and C = 100 (a 100 x 100 grid). Calculate V and E for this grid.(3)

(d)Using the adjacency-list-with-min-heap implementation of Dijkstra/A*, with time complexity O((V + E) log V), calculate an estimate for the number of operations needed to find a route across this 100 x 100 grid. Give your answer to 3 significant figures.(3)

(e)In practice, A* with a well-chosen heuristic (such as Manhattan distance, |x1 - x2| + |y1 - y2|, between grid coordinates) typically explores far fewer than V vertices when finding a route between two specific cells, even though the algorithm's worst-case time complexity calculated in part (d) is the same as Dijkstra's. Explain why this is the case.(2)

(Total for Question 12 is 11 marks)

Mark scheme · A2.6 Advanced Algorithms: Searching, Sorting and Path-Finding

Question 1

(a) B1 the array must already be sorted (in ascending or descending order) (oe)
(a) Answer: The array must already be sorted into order.
(b) B1 row 1: low=0, high=11, mid=5, list[5]=151, 151 < 172 so low <- 6
(b) B1 row 2: low=6, high=11, mid=8, list[8]=190, 190 > 172 so high <- 7
(b) B1 row 3: low=6, high=7, mid=6, list[6]=168, 168 < 172 so low <- 7
(b) B1 row 4: low=7, high=7, mid=7, list[7]=172, 172 = 172 so RETURN 7
(b) Answer: Row1: low0,high11,mid5(151,<,low<-6). Row2: low6,high11,mid8(190,>,high<-7). Row3: low6,high7,mid6(168,<,low<-7). Row4: low7,high7,mid7(172,=,return7).
(c) B1 7 ft from (b)
(c) B1 4 comparisons ft from (b)
(c) Answer: 7 is returned; 4 comparisons are made.
(d) M1 log2(2001) = awrt 10.97
(d) A1 ceil(10.97) = 11 cao
(d) Answer: 11
(e) B1 2000
(e) B1 binary search (oe)
(e) B1 because it needs far fewer comparisons (11 compared with 2000), as O(log n) grows far more slowly than O(n) as n increases (oe)
(e) Answer: 2000 comparisons for linear search; binary search is far more time-efficient, needing only 11 comparisons compared with 2000, reflecting O(log n) growing much more slowly than O(n).

Question 2

(a) B1 pass 1: list = [1, 2, 3, 4, 5, 8]
(a) B1 pass 1: swapped = TRUE, comparisons = 5
(a) B1 pass 2: list = [1, 2, 3, 4, 5, 8] (unchanged)
(a) B1 pass 2: swapped = FALSE, comparisons = 4
(a) Answer: Pass1: [1,2,3,4,5,8], swapped=TRUE, 5 comparisons. Pass2: [1,2,3,4,5,8], swapped=FALSE, 4 comparisons.
(b) B1 i=4: current = 4
(b) B1 i=4: 2 comparisons made, list = [1, 2, 3, 4, 8, 5]
(b) B1 i=5: current = 5
(b) B1 i=5: 2 comparisons made, list = [1, 2, 3, 4, 5, 8]
(b) Answer: i=4: current=4, 2 comparisons, list=[1,2,3,4,8,5]. i=5: current=5, 2 comparisons, list=[1,2,3,4,5,8].
(c) B1 bubble sort: 9 comparisons ft from (a)
(c) B1 insertion sort: 1+1+1+2+2 = 7 comparisons ft from (b)
(c) B1 insertion sort required fewer comparisons (7 compared with 9)
(c) Answer: Bubble sort: 9 comparisons. Insertion sort: 7 comparisons. Insertion sort needed fewer.
(d) B1 insertion sort only performs comparisons where they are actually needed to find the correct insertion point for each element, so an element already in its correct position (like the first three here) costs only a single comparison
(d) B1 bubble sort must still compare every adjacent pair on each full pass, regardless of how many elements are already in order, which cost it 2 more comparisons than insertion sort on this example (9 vs 7)
(d) Answer: Insertion sort only compares as far back as needed to find each element's correct position, so already-placed elements cost just one comparison each; bubble sort must still compare every adjacent pair on every pass regardless, which is why it needed more comparisons (9) than insertion sort (7) on this nearly-sorted list.

Question 3

(a) B1 linear search: worst O(n), best O(1)
(a) B1 binary search: worst O(log n), best O(1)
(a) B1 bubble sort: worst O(n²), best O(n)
(a) B1 insertion sort: worst O(n²), best O(n)
(a) B1 merge sort: worst O(n log n), best O(n log n)
(a) Answer: Linear search: O(n)/O(1). Binary search: O(log n)/O(1). Bubble sort: O(n²)/O(n). Insertion sort: O(n²)/O(n). Merge sort: O(n log n)/O(n log n).
(b) B1 linear search, binary search, bubble sort and insertion sort are all adaptive (their best case is better than their worst case)
(b) B1 merge sort is not adaptive: its best case equals its worst case, O(n log n)
(b) B1 because standard merge sort always fully splits the list down to single elements and always fully merges every sub-list back together, regardless of whether the input was already in order (oe)
(b) Answer: Linear search, binary search, bubble sort and insertion sort are all adaptive. Merge sort is not, because it always performs the same full sequence of splits and merges (O(n log n)) no matter how the input list is initially ordered.

Question 4

(a) M1 C(2) = 2 x C(1) + (2 - 1) = 2 x 0 + 1 = 1
(a) M1 C(4) = 2 x C(2) + (4 - 1) = 2 x 1 + 3 = 5
(a) A1 C(8) = 2 x C(4) + (8 - 1) = 2 x 5 + 7 = 17 cao
(a) Answer: C(2) = 1, C(4) = 5, C(8) = 17
(b) M1 substitutes n = 8: C(8) = 8 x log2(8) - 8 + 1 = 8 x 3 - 8 + 1
(b) A1 = 17, matching part (a) cao
(b) Answer: C(8) = 8 x 3 - 8 + 1 = 17, matching part (a).
(c) M1 log2(16) = 4, so C(16) = 16 x 4 - 16 + 1
(c) A1 C(16) = 49 cao
(c) M1 log2(64) = 6, so C(64) = 64 x 6 - 64 + 1
(c) A1 C(64) = 321 cao
(c) Answer: C(16) = 49, C(64) = 321
(d) M1 64 x 63 / 2
(d) A1 = 2016 cao
(d) B1 valid comment: bubble sort needs more than six times as many comparisons as merge sort (2016 compared with 321) at this size, showing O(n²) grows substantially faster than O(n log n) as n increases (oe)
(d) Answer: 2016 comparisons for bubble sort, compared with 321 for merge sort; O(n²) clearly grows much faster than O(n log n) as n increases.

Question 5

(a) B1 pivot = 8
(a) B1 less = [3, 1, 6, 4]
(a) B1 greaterEq = [10, 14]
(a) Answer: pivot = 8; less = [3, 1, 6, 4]; greaterEq = [10, 14]
(b) B1 call 2 ([3,1,6,4]): pivot = 3, less = [1], greaterEq = [6, 4]
(b) B1 call 3 ([6,4]): pivot = 6, less = [4], greaterEq = []
(b) B1 call 4 ([10,14]): pivot = 10, less = [], greaterEq = [14]
(b) B1 correctly recognises that lists of 0 or 1 elements (e.g. [1], [4], [14], []) are base cases and are returned immediately with no further partitioning
(b) Answer: Call2 ([3,1,6,4]): pivot=3, less=[1], greaterEq=[6,4]. Call3 ([6,4]): pivot=6, less=[4], greaterEq=[]. Call4 ([10,14]): pivot=10, less=[], greaterEq=[14].
(c) B1 [1, 3, 4, 6, 8, 10, 14] ft
(c) M1 6 (call 1) + 3 (call 2) + 1 (call 3) + 1 (call 4) shown
(c) A1 11 comparisons cao
(c) Answer: [1, 3, 4, 6, 8, 10, 14]; 11 comparisons in total.
(d) B1 O(n log n) cao
(d) B1 when partitions are roughly balanced, the list size roughly halves at each level, giving about log2(n) levels of recursion, and each level does a total of about n comparisons across all its calls, giving n x log n overall (oe)
(d) Answer: O(n log n): with roughly balanced partitions, there are about log2(n) levels of recursion, and each level does a total of about n comparisons, giving n x log n overall.

Question 6

(a) B1 pivot = 2, less = []
(a) B1 greaterEq = [5, 7, 9, 12, 15]
(a) Answer: pivot = 2; less = []; greaterEq = [5, 7, 9, 12, 15]
(b) B1 the pivot chosen (list[0]) is always the smallest of the remaining elements, since the list is sorted in ascending order
(b) B1 so every other remaining element is greater than or equal to the pivot, meaning nothing can ever go into less, and the recursion becomes a single, highly unbalanced chain rather than two roughly equal halves (oe)
(b) Answer: Because the list is sorted, the first element (chosen as pivot) is always the smallest of what remains, so every other element is greater than or equal to it; this means less is always empty and greaterEq always contains everything else, giving one very unbalanced recursive branch instead of two balanced halves.
(c) B1 levels 2-6: comparisons = 4, 3, 2, 1, 0 respectively
(c) B1 recognises the pattern: comparisons made equal (list size at that level) - 1
(c) B1 total = 5 + 4 + 3 + 2 + 1 + 0 = 15 cao
(c) Answer: Comparisons per level: 5, 4, 3, 2, 1, 0. Total = 15.
(d) M1 total comparisons = (n - 1) + (n - 2) + ... + 1 + 0, the sum of the first (n - 1) positive integers
(d) A1 this arithmetic series sums to n(n - 1) / 2; verifying for n = 6 gives 6 x 5 / 2 = 15, matching part (c)
(d) B1 O(n²)
(d) Answer: Total comparisons = n(n - 1) / 2, which is O(n²). For n = 6 this gives 15, matching part (c).
(e) B1 choosing the pivot at random from the current list
(e) B1 choosing the pivot as the median of the first, middle and last elements ("median-of-three"), or equivalently choosing the middle element of the list
(e) Answer: Choosing the pivot at random, or choosing it as the median-of-three (or middle element) of the current list.

Question 7

(a) B1 all edge weights must be non-negative (zero or positive)
(a) Answer: All edge weights must be non-negative.
(b) B1 step 2: settles C; distances A=0, B=3, C=2, D=10, E=12, F=-
(b) B1 step 3: settles B; distances A=0, B=3, C=2, D=8, E=12, F=-
(b) B1 step 4: settles D; distances A=0, B=3, C=2, D=8, E=10, F=14
(b) B1 step 5: settles E; distances A=0, B=3, C=2, D=8, E=10, F=13
(b) B1 step 6: settles F; distances unchanged, F=13
(b) Answer: Step2: settle C (B=3,C=2,D=10,E=12). Step3: settle B (D=8). Step4: settle D (E=10,F=14). Step5: settle E (F=13). Step6: settle F (13).
(c) B1 13 minutes ft
(c) B1 A-C-B-D-E-F ft
(c) Answer: 13 minutes, via the path A-C-B-D-E-F.
(d) B1 for each vertex, the algorithm can record which neighbouring vertex it was reached from at the moment its shortest distance was last updated (its "predecessor")
(d) B1 starting at the destination, following the predecessor links backwards until reaching the source gives the path, in reverse order
(d) Answer: By storing, for every vertex, the predecessor it was reached from when its shortest distance was last set; starting at F and following predecessors back to A reconstructs the path in reverse.

Question 8

(a) B1 O(V²)
(a) B1 V vertices are settled, and each requires an O(V) scan to find the next closest unvisited vertex, giving V x V = V² (oe)
(a) Answer: O(V²): V vertices are settled, each needing an O(V) scan, giving V x V operations.
(b) B1 O((V + E) log V)
(b) B1 extracting the minimum V times costs O(V log V), and each of the E edges can trigger one O(log V) heap update, giving O((V + E) log V) overall (oe)
(b) Answer: O((V + E) log V): V extractions each cost O(log V), and E possible heap updates each cost O(log V).
(c) M1 adjacency matrix: V² = 6²
(c) A1 = 36 cao
(c) M1 adjacency list + heap: (V + E) x log2(V) = (6 + 9) x log2(6) = 15 x awrt 2.585
(c) A1 awrt 39 (accept 38-39)
(c) Answer: Adjacency matrix: approximately 36 operations. Adjacency list + heap: approximately 39 operations.
(d) B1 the adjacency list with min-heap implementation
(d) B1 because in a sparse graph E grows only linearly with V, so (V + E) log V grows far more slowly than V² as V becomes large, meaning the matrix implementation's V² term comes to dominate for large sparse graphs (oe)
(d) Answer: The adjacency list with min-heap, because for a sparse, large graph (V + E) log V grows far more slowly than V², so the matrix approach becomes comparatively far less efficient as V grows.

Question 9

(a) B1 f(A) = 0 + 9 = 9
(a) Answer: f(A) = 9
(b) B1 B: g = 0 + 4 = 4, h = 7, f = 11
(b) B1 C: g = 0 + 2 = 2, h = 8, f = 10
(b) Answer: B: g=4, h=7, f=11. C: g=2, h=8, f=10.
(c) B1 step 3: expand B (lowest f = 10); D updates to g=8, f=12
(c) B1 step 4: expand D (lowest f = 12); E updates to g=10, f=12; F: g=14, f=14 (newly reached)
(c) B1 step 5: expand E (lowest f = 12); F updates to g=13, f=13
(c) B1 step 6: expand F (lowest f = 13); F is the goal, so the search stops
(c) Answer: Step3: expand B, D updates g8/f12. Step4: expand D, E updates g10/f12, F newly g14/f14. Step5: expand E, F updates g13/f13. Step6: expand F, goal reached, stop.
(d) B1 13 minutes ft
(d) B1 A-C-B-D-E-F ft
(d) B1 this is identical to the distance and path found by Dijkstra's algorithm, confirming both algorithms found the true shortest path
(d) Answer: 13 minutes via A-C-B-D-E-F, identical to the result found by Dijkstra's algorithm.
(e) B1 6 vertices expanded (A, C, B, D, E, F), the same number settled by Dijkstra's algorithm
(e) B1 no efficiency advantage is shown in this particular example, as both algorithms expanded/settled all 6 vertices in the same order
(e) B1 valid reason: because F lies at the far end of this small, densely connected graph, almost every vertex lies on or close to the shortest path towards it, giving the heuristic little opportunity to avoid expanding any vertex; A*'s advantage is typically far greater on larger graphs, or when many vertices lie well away from the goal (oe)
(e) Answer: 6 vertices were expanded, exactly the same as Dijkstra settled, in the same order; no advantage is shown here because F lies at the far end of this small graph, so nearly every vertex lies on a shortest path towards it. A*'s benefit is normally much clearer on larger graphs.

Question 10

(a) L1 (1-3): Basic, isolated points are made about Dijkstra's algorithm and/or A*, with little or no reference to time complexity, heuristics or the given scenario. The answer may simply name both algorithms with little justification, or fail to identify any valid situation where Dijkstra is preferable.
(a) L2 (4-6): Some relevant points are made about the efficiency of A* compared with Dijkstra, with limited or partly-accurate reference to heuristics and time complexity. Some link is made to the scale of the scenario (millions of junctions), and a situation favouring Dijkstra is attempted but may be only partially justified.
(a) L3 (7-8): A clear, well-justified discussion is given, correctly explaining how A*'s heuristic reduces the number of junctions explored compared with Dijkstra for a single specific route, supported by accurate technical detail (e.g. admissibility). A valid, clearly justified situation where Dijkstra remains the more appropriate choice is identified and linked to the scenario.
(a) Answer: Best answers recommend A* for a single specific route, using an admissible heuristic such as straight-line distance to prioritise the search and expand far fewer junctions than Dijkstra, but correctly identify that Dijkstra is preferable when shortest paths to all destinations are needed simultaneously (e.g. depot-to-everywhere precomputation), since A*'s heuristic gives no benefit in that case.

Question 11

(a) B1 h(D) = 4 is admissible because 4 ≤ 5 (the true shortest distance from D to F)
(a) B1 h(E) = 2 is admissible because 2 ≤ 3 (the true shortest distance from E to F)
(a) Answer: Both are admissible: h(D)=4 ≤ 5, and h(E)=2 ≤ 3.
(b) M1 checks h(D) ≤ cost(D, E) + h(E): 4 ≤ 2 + 2
(b) A1 4 ≤ 4 is true (holds, with equality), so the heuristic is consistent for this edge cao
(b) Answer: h(D) = 4 ≤ cost(D,E) + h(E) = 2 + 2 = 4, so the condition holds (with equality).
(c) B1 step 2: expands X (lowest f = 1, since f(Y) = 11)
(c) B1 step 2: G is reached via X with g = 1 + 5 = 6, f = 6 + 0 = 6
(c) B1 step 3: expands G (f = 6, now the lowest in the open list, since f(Y) = 11)
(c) B1 G is the goal, so A* terminates, returning the path S-X-G with total distance 6
(c) B1 recognises this is NOT the true shortest path, which is S-Y-G with total distance 2
(c) B1 recognises Y was never expanded before the search terminated
(c) Answer: Step2: expand X, G reached with g=6, f=6. Step3: expand G (lowest f=6, since f(Y)=11), goal reached, A* returns path S-X-G, distance 6. This is not the true shortest path (S-Y-G, distance 2); Y was never expanded.
(d) B1 if a heuristic overestimates the true remaining distance for even one vertex, A* can terminate having found a suboptimal path, because that vertex is wrongly deprioritised (given a high f value) and so is never explored before the algorithm stops; an admissible heuristic is therefore essential for A*'s optimality guarantee
(d) Answer: It shows that an inadmissible (overestimating) heuristic can cause A* to terminate with a suboptimal path, because the vertex leading to the true shortest path is wrongly given a low priority and never explored before the search stops.