Decision: Algorithms and Graph Theory Depth - Worksheets, Questions and Revision

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

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

Next in this strand

Decision: Linear Programming and Critical Path Depth

Revision Library

revisionlibrary.co.uk

A-Level · Further Decision Mathematics (Algorithms and Graph Theory Depth)

FP.D5 Decision: Algorithms and Graph Theory Depth

EDEXCEL 9FM0 · Calculator allowed · about 120 minutes

Total Marks

Name: _______________________________ Date: ____ / ____ / ______

Answer ALL questions. Show all your working.

The following list of six numbers is to be sorted into ascending order:
8, 3, 10, 5, 1, 7

(a)Perform a bubble sort on the list, comparing and swapping adjacent items from left to right. Show the list in full after each pass, and continue until you have completed one full pass in which no swaps are made.(4)

(b)State the number of comparisons made during the first pass.(1)

(Total for Question 1 is 5 marks)

The lap times, in seconds, recorded for seven laps of a go-kart track, in the order the laps were driven, are:
42, 17, 56, 8, 31, 24, 63

(a)Using the first item of each sublist as the pivot, perform a quicksort on this list to sort it into ascending order. At each stage, state the pivot used and the two resulting sublists (items less than the pivot, and items greater than or equal to the pivot). Continue until every sublist contains at most one item, then state the final sorted list.(5)

(b)State the total number of pivots used to sort the list completely.(1)

(Total for Question 2 is 6 marks)

Kwame runs a small courier company. One morning he must pack parcels of the following weights, in kg, into delivery bins that can each hold a maximum of 30 kg:
13, 8, 19, 11, 6, 14, 9, 17

(a)Calculate a lower bound for the number of bins needed to pack all eight parcels.(2)

(b)Apply the first-fit algorithm to the parcels, in the order given, packing them into bins of capacity 30 kg. State the contents of each bin, and the number of bins used.(3)

(c)Sort the parcel weights into decreasing order and apply first-fit decreasing to the same set of parcels, packing into bins of capacity 30 kg. State the contents of each bin, and the number of bins used.(3)

(Total for Question 3 is 8 marks)

A haulage firm must load crates of the following weights, in kg, onto lorries that can each carry a maximum of 50 kg:
22, 28, 19, 31, 12, 38

(a)Using a full-bin method, find combinations of crates that exactly fill a 50 kg lorry, and show that all six crates can be loaded using exactly three lorries with no wasted capacity.(3)

(b)Calculate a lower bound for the number of lorries required, and state, with a reason, whether the packing found in part (a) is optimal.(2)

(Total for Question 4 is 5 marks)

A water company is planning new pipeline connections between seven reservoirs, A to G. The table below gives the cost, in GBP 1000s, of laying a direct pipeline between each pair of reservoirs that could feasibly be connected:
AB = 7, AC = 9, BC = 5, BD = 8, CD = 6, DE = 4, EF = 3, EG = 9, FG = 6, CE = 10, BE = 11, DF = 12

(a)Use Kruskal's algorithm to find a minimum spanning tree for this network. List the edges in increasing order of cost, stating whether each is accepted or rejected as you reach it, until every reservoir is connected.(5)

(b)State the total cost of the minimum spanning tree found in part (a).(1)

(c)The next edge Kruskal's algorithm would consider is BD, of cost 8. Explain why this edge cannot be selected.(1)

(Total for Question 5 is 7 marks)

Yusuf, a network engineer, is planning fibre-optic cable connections between six towns, P, Q, R, S, T, U. The distance matrix below shows the length, in km, of cable needed for every possible direct connection:

P Q R S T U
P - 6 4 9 11 13
Q 6 - 5 7 10 12
R 4 5 - 3 8 14
S 9 7 3 - 6 9
T 11 10 8 6 - 4
U 13 12 14 9 4 -

(a)Starting at P, apply Prim's algorithm to the matrix to find a minimum spanning tree. At each stage, state the town added to the tree and the length of cable used to connect it.(6)

(b)State the total length of cable required for the minimum spanning tree found.(1)

(Total for Question 6 is 7 marks)

A network of road junctions, A to G, used by a fleet of breakdown-recovery vans, has direct roads with journey times, in minutes: AB = 4, AC = 7, BC = 2, BD = 6, CD = 3, CE = 8, DE = 1, DF = 5, EF = 4, EG = 7, FG = 2

(a)Use Dijkstra's algorithm, starting at A, to find the shortest time from junction A to every other junction. Show clearly the working values considered, and the order in which each junction receives its final (permanent) label.(8)

(b)State the shortest route from A to G, and its length.(2)

(Total for Question 7 is 10 marks)

Deepak, a parks ranger, must inspect every path in Thornfield Park at least once, starting and finishing at the main gate, A. The park's paths form a network with vertices A to H, and path lengths, in metres: AB = 6, AC = 5, AH = 10, BC = 4, BD = 7, CD = 3, CE = 8, DE = 6, DF = 9, EF = 4, EG = 7, FG = 5, FH = 6, GH = 3

(a)Write down the vertices of odd degree in this network.(1)

(b)Find the length of the shortest path between each possible pairing of these four odd vertices into two pairs, and hence state the total length of each of the three possible pairings.(6)

(Total for Question 8 is 7 marks)

This question continues from Question 8, using the same park network and path lengths.

(a)Hence find the length of the shortest route, starting and finishing at A, that covers every path in the park at least once.(2)

(b)State which two paths Deepak must walk along twice during this shortest route.(1)

(Total for Question 9 is 3 marks)

This question concerns further properties of graphs and networks.

(a)A connected planar graph has 9 vertices and 14 edges. Use Euler's formula for planar graphs, v - e + f = 2, to find the number of faces of the graph (including the unbounded outer face).(2)

(b)State what is meant by a bipartite graph, and calculate the number of edges in the complete bipartite graph K(4,5), which has one set of 4 vertices and another set of 5 vertices, with every vertex in one set joined to every vertex in the other set, and no edges within either set.(2)

(c)State what is meant by a Hamiltonian cycle in a graph, and explain how this differs from an Eulerian circuit.(2)

(d)Explain why every tree must be a bipartite graph.(2)

(Total for Question 10 is 8 marks)

This question concerns the efficiency of sorting algorithms as the size of a list, n, increases.

(a)State the order of the bubble sort algorithm, in terms of the number of items n, for the worst-case number of comparisons required.(1)

(b)Given that, in the worst case, a bubble sort on a list of n items requires exactly n(n - 1)/2 comparisons, calculate this number of comparisons for a list of n = 60 items.(2)

(c)A quicksort algorithm has worst-case order O(n²), the same as bubble sort, but average-case order O(n log n). Explain why quicksort is generally preferred over bubble sort in practice, despite sharing the same worst-case order.(2)

(Total for Question 11 is 5 marks)

A logistics manager is planning work on the same road network connecting a depot and several towns, and has three separate problems to solve:
Problem 1: connect every town to the depot using cable of minimum total length (the towns do not need to be able to reach each other quickly afterwards, only to be linked into a single network).
Problem 2: find the quickest possible route for a single van to drive from the depot to one specific town.
Problem 3: find the shortest possible route for a gritting lorry that must drive along every road in the network at least once, starting and finishing at the depot.

Discuss which type of algorithm, a minimum spanning tree algorithm (Kruskal's or Prim's), Dijkstra's algorithm, or the route inspection algorithm, should be used to solve each problem. Your answer should explain what feature of each problem identifies the correct technique, and explain why using an incorrect technique would fail to answer the question actually being asked.

(Total for Question 12 is 6 marks)

Aaliyah is organising a charity obstacle-course event with five checkpoints, P, Q, R, S, T, linked by permanently open trail paths. The distances between checkpoints connected by a trail, in metres, are: PQ = 120, PR = 200, PS = 340, QR = 90, QT = 260, RS = 150, RT = 210, ST = 180 (there is no direct trail between any other pair of checkpoints).

(a)The organisers need to run a single length of event cable connecting all five checkpoints, using the least total length of cable. Use Kruskal's algorithm to find this minimum length, showing the edges you accept and at least one edge you reject, with a reason.(4)

(b)A safety marshal, Owen, must travel from the checkpoint at P to the checkpoint at T, using the original trail network (not necessarily the minimum cable route found in part (a)). Use Dijkstra's algorithm, starting at P, to find the length of the shortest route from P to T. Show the order in which each checkpoint receives its final label, and state the shortest route.(5)

(c)Crates of bottled water, of mass 14, 22, 9, 18, 27, 11 and 16 kg, must be loaded into vans, each with a capacity of 45 kg. Calculate a lower bound for the number of vans required, then apply first-fit decreasing to pack the crates. State the contents of each van, and state whether the lower bound has been achieved.(4)

(Total for Question 13 is 13 marks)

Mark scheme · FP.D5 Decision: Algorithms and Graph Theory Depth

Question 1

(a) M1 pass 1 correct: 3, 8, 5, 1, 7, 10
(a) A1 pass 2 correct: 3, 5, 1, 7, 8, 10
(a) A1 passes 3 and 4 both correct: 3, 1, 5, 7, 8, 10 then 1, 3, 5, 7, 8, 10
(a) B1 a further (5th) pass shown with no swaps, confirming the list is sorted
(a) Answer: Pass 1: 3, 8, 5, 1, 7, 10. Pass 2: 3, 5, 1, 7, 8, 10. Pass 3: 3, 1, 5, 7, 8, 10. Pass 4: 1, 3, 5, 7, 8, 10. Pass 5 (check): 1, 3, 5, 7, 8, 10 (no swaps).
(b) B1 5 comparisons cao
(b) Answer: 5 comparisons.

Question 2

(a) M1 first pivot = 42 identified, with correct sublists {17, 8, 31, 24} (< 42) and {56, 63} (≥ 42)
(a) A1 correct second-stage split on {17, 8, 31, 24}: pivot 17, giving {8} and {31, 24}
(a) A1 correct second-stage split on {56, 63}: pivot 56, giving { } and {63}
(a) A1 correct third-stage split on {31, 24}: pivot 31, giving {24} and { }
(a) B1 correct final sorted list 8, 17, 24, 31, 42, 56, 63 cao, with all four pivots (42, 17, 56, 31) correctly identified
(a) Answer: Final sorted list: 8, 17, 24, 31, 42, 56, 63.
(b) B1 4 pivots cao
(b) Answer: 4 pivots.

Question 3

(a) M1 total weight = 13+8+19+11+6+14+9+17 = 97 kg
(a) A1 lower bound = ceiling(97/30) = 4 cao
(a) Answer: Lower bound = 4 bins.
(b) M1 correct method: each parcel placed in the first bin (in order) with enough remaining space, opening a new bin only when none of the existing bins can fit it
(b) A1 correct bin contents: Bin 1 {13, 8, 6}, Bin 2 {19, 11}, Bin 3 {14, 9}, Bin 4 {17}
(b) B1 4 bins used cao
(b) Answer: Bin 1: 13, 8, 6 (27 kg). Bin 2: 19, 11 (30 kg). Bin 3: 14, 9 (23 kg). Bin 4: 17 (17 kg). 4 bins used.
(c) M1 correct decreasing order: 19, 17, 14, 13, 11, 9, 8, 6
(c) A1 correct bin contents: Bin 1 {19, 11}, Bin 2 {17, 13}, Bin 3 {14, 9, 6}, Bin 4 {8}
(c) B1 4 bins used cao, matching the lower bound found in part (a), so this packing is optimal
(c) Answer: Bin 1: 19, 11 (30 kg). Bin 2: 17, 13 (30 kg). Bin 3: 14, 9, 6 (29 kg). Bin 4: 8 (8 kg). 4 bins used, matching the lower bound.

Question 4

(a) M1 identifies at least one pair of crates summing to exactly 50 kg, e.g. 22 + 28 = 50
(a) A1 all three valid pairs identified: (22, 28), (19, 31) and (12, 38), each summing to exactly 50
(a) A1 states three lorries, each exactly full: Lorry 1 {22, 28}, Lorry 2 {19, 31}, Lorry 3 {12, 38}
(a) Answer: Lorry 1: 22, 28 (50 kg). Lorry 2: 19, 31 (50 kg). Lorry 3: 12, 38 (50 kg). 3 lorries, all exactly full.
(b) B1 total weight = 150 kg, lower bound = ceiling(150/50) = 3
(b) B1 yes, optimal, since the packing in part (a) achieves this lower bound of 3 lorries with no wasted capacity (oe)
(b) Answer: Lower bound = 3 lorries; the packing in part (a) achieves this, so it is optimal.

Question 5

(a) M1 attempts edges in increasing order of cost: EF(3), DE(4), BC(5), CD(6), FG(6), AB(7), ...
(a) A1 accepts EF(3), DE(4), BC(5), each correctly joining a new component with no cycle
(a) A1 accepts CD(6) and FG(6) (either order, since tied), each correctly joining a new component
(a) A1 accepts AB(7), correctly completing the spanning tree
(a) B1 correctly states the tree is complete once 6 edges have been chosen, since a spanning tree of 7 reservoirs requires exactly 6 edges
(a) Answer: Accepted, in order: EF(3), DE(4), BC(5), CD(6), FG(6), AB(7). Tree complete with 6 edges.
(b) B1 31 (i.e. GBP 31,000) cao
(b) Answer: 31 (GBP 31,000).
(c) B1 B and D are already connected via the edges already chosen (the path B-C-D), so adding BD would form a cycle, which Kruskal's algorithm must avoid (oe)
(c) Answer: B and D are already connected (via B-C-D using edges already selected), so BD would create a cycle and must be rejected.

Question 6

(a) M1 starting town P noted; identifies PR = 4 as the least connection available from P
(a) A1 R added, connected via PR = 4
(a) A1 S added, connected via RS = 3 (the least value now available from {P, R} to the remaining towns)
(a) A1 Q added, connected via RQ = 5
(a) A1 T added, connected via ST = 6
(a) A1 U added, connected via TU = 4, completing the tree
(a) Answer: Order added: R (via PR = 4), S (via RS = 3), Q (via RQ = 5), T (via ST = 6), U (via TU = 4).
(b) B1 22 km cao
(b) Answer: 22 km.

Question 7

(a) M1 A permanently labelled with 0; initial working values B = 4 (via A), C = 7 (via A)
(a) A1 B permanently labelled second, with value 4; C updated to 6 (via B, since 4 + 2 = 6 < 7)
(a) A1 C permanently labelled third, with value 6; D = 9 (via C), E = 14 (via C)
(a) A1 D permanently labelled fourth, with value 9; E updated to 10 (via D, since 9 + 1 = 10 < 14), F = 14 (via D)
(a) A1 E permanently labelled fifth, with value 10; G = 17 (via E); notes F's candidate value via E (10 + 4 = 14) does not improve on F's existing value of 14 (via D), so F is unchanged
(a) A1 F permanently labelled sixth, with value 14 (via D)
(a) A1 G updated to 16 (via F, since 14 + 2 = 16 < 17)
(a) B1 G permanently labelled seventh (last), with value 16; full order of labelling correctly stated as A, B, C, D, E, F, G
(a) Answer: Order of permanent labelling: A(0), B(4), C(6), D(9), E(10), F(14), G(16).
(b) B1 A-B-C-D-F-G (oe, traced back through predecessors from G)
(b) B1 16 (minutes) cao
(b) Answer: A-B-C-D-F-G, 16 minutes.

Question 8

(a) B1 A, B, G, H cao
(a) Answer: A, B, G, H.
(b) B1 correctly lists the three possible pairings: (AB and GH), (AG and BH), (AH and BG)
(b) M1 valid method: compares alternative routes rather than assuming direct arcs are always shortest
(b) A1 pairing (AB, GH): shortest AB = 6 (direct), shortest GH = 3 (direct); total = 9
(b) A1 pairing (AG, BH): shortest AG = 13 (via A-H-G, 10+3), shortest BH = 16 (via B-A-H, 6+10); total = 29
(b) A1 pairing (AH, BG): shortest AH = 10 (direct), shortest BG = 19 (via B-C-E-G, 4+8+7, tying with B-A-H-G, 6+10+3); total = 29
(b) A1 correctly identifies (AB, GH) = 9 as the minimum of the three pairings
(b) Answer: (AB, GH) = 9; (AG, BH) = 29; (AH, BG) = 29. Minimum pairing: AB and GH.

Question 9

(a) B1 total length of network = 6+5+10+4+7+3+8+6+9+4+7+5+6+3 = 83 (m)
(a) B1 shortest route = 83 + 9 = 92 (m) cao (ft from the minimum pairing found in Question 8)
(a) Answer: 92 m.
(b) B1 AB and GH (the two arcs making up the minimum pairing found in Question 8)
(b) Answer: AB and GH.

Question 10

(a) M1 substitutes v = 9 and e = 14 into v - e + f = 2
(a) A1 f = 7 cao
(a) Answer: 7 faces.
(b) B1 a bipartite graph is one whose vertices can be split into two disjoint sets so that every edge joins a vertex in one set to a vertex in the other set, with no edges within either set (oe)
(b) B1 number of edges in K(4,5) = 4*5 = 20 cao
(b) Answer: A bipartite graph splits its vertices into two sets with edges only between the sets, never within a set; K(4,5) has 4*5 = 20 edges.
(c) B1 a Hamiltonian cycle is a cycle that visits every vertex of the graph exactly once, before returning to its starting vertex (oe)
(c) B1 an Eulerian circuit instead requires every edge (not vertex) to be used exactly once, returning to the start; a graph may possess one of these properties without the other (oe)
(c) Answer: A Hamiltonian cycle visits every vertex exactly once; an Eulerian circuit instead uses every edge exactly once. A graph can have either property without the other.
(d) B1 a tree contains no cycles at all, by definition, so in particular it contains no cycle of odd length (oe)
(d) B1 a graph is bipartite if and only if it contains no odd-length cycle; since a tree has no cycles whatsoever, this condition is automatically satisfied, so every tree is bipartite (oe)
(d) Answer: A tree has no cycles at all, so it certainly has no odd cycles; since a graph is bipartite exactly when it has no odd cycle, every tree must be bipartite.

Question 11

(a) B1 O(n²)
(a) Answer: O(n²).
(b) M1 substitutes n = 60 into n(n - 1)/2
(b) A1 1770 cao
(b) Answer: 1770 comparisons.
(c) B1 quicksort's average-case order, O(n log n), grows far more slowly than bubble sort's typical performance, which is close to O(n²) for almost all inputs (oe)
(c) B1 in practice, most real lists do not trigger quicksort's worst case, so it usually runs much closer to its efficient average-case behaviour, making it faster than bubble sort for large lists in the great majority of cases (oe)
(c) Answer: Quicksort's average-case order O(n log n) is far better than bubble sort's near-O(n²) typical performance; since quicksort's worst case is rare in practice, it is usually much faster for large lists.

Question 12

Level 0 (0): No relevant technique correctly matched to any of the three problems, or the response does not address the question.
Level 1 (1-2): At least one problem is matched to a broadly appropriate technique, but with little or no valid justification, and no discussion of why other techniques would be unsuitable.
Level 2 (3-4): At least two of the three problems are correctly matched to their appropriate technique, with some valid justification referring to what each problem requires; explanation of why an incorrect technique would fail is limited or only partially developed.
Level 3 (5-6): All three problems are correctly matched to their appropriate technique (minimum spanning tree algorithm for Problem 1, Dijkstra's algorithm for Problem 2, route inspection algorithm for Problem 3), with clear justification referring to the specific requirement of each problem, and a clear explanation of why using an incorrect technique for a given problem would fail to answer the question actually being asked.
Indicative content:
- Problem 1 only requires every town to be linked into a single connected network using the least total length of cable, with no requirement to travel quickly between any two particular towns afterwards; this is a minimum spanning tree problem, solved using Kruskal's algorithm or Prim's algorithm.
- Problem 2 requires the shortest route between two specific vertices only (the depot and one named town); this is exactly what Dijkstra's algorithm finds.
- Problem 3 requires a route that uses every road in the network at least once and returns to its starting point; this is the route inspection (Chinese postman) problem.
- Using Dijkstra's algorithm for Problem 1 would only ever find a path between two particular vertices, not a structure connecting every town together, so it cannot solve Problem 1.
- Using a minimum spanning tree for Problem 2 would not generally give the shortest route between the depot and a specific town, since a spanning tree minimises the total length of the whole network, not the distance between any one particular pair of vertices; the route between two towns within a minimum spanning tree can be much longer than the true shortest path between them.
- Using a minimum spanning tree, or Dijkstra's algorithm, for Problem 3 would not guarantee that every road is used: a spanning tree deliberately omits some edges (it has only n - 1 edges for n vertices), and Dijkstra's algorithm only ever finds a route between two vertices, not a route covering every edge.
- The key skill is recognising the single feature that identifies each type of problem: connect everything as cheaply as possible (minimum spanning tree); find the shortest distance between two specific vertices (Dijkstra's algorithm); or use every edge at least once (route inspection algorithm).