Revision Library
Choose a subject
Menu
Further Maths
Need a new topic?
Missing a topic, found a bug, or want something added?

A Level Further Maths Decision Topic Workbooks

A Level Further Maths Decision Topic Workbook

Decision Maths: Algorithms, Sorting and Bin Packing, Decision Maths: Graphs, Trees and Minimum Spanning Trees, Decision Maths: Shortest Paths and Route Inspection and 3 more

Level
A Level · Edexcel 9FM0 · AQA 7367 · OCR H245
Series
A Level Further Maths Decision Topic Workbooks
Suitable for
Years 12-13, AQA / Edexcel / OCR
FreePDF download · 2027 edition · 71 A4 pages
  • One file, prints straight to A4
  • No account, no password

Workbooks like this one, with 6 topics, 60 questions and mark schemes at the back, are usually printed and sold by publishers. This one is one of 558 free PDFs on the shelf.

Pages
71 A4 pages
Chapters
6 worksheet chapters
Questions
60 · 480 marks
Answers
From page 52
Working time
About 10h 20m

What is inside

6 chapters · answers from p52

Each chapter starts with a page showing its marks and a suggested time, followed by the questions. The mark schemes for all 6 chapters are at the back, so the book works for homework, a timed test or revision.

  1. 01Decision Maths: Algorithms, Sorting and Bin Packing9 questions · 73 marks · about 95 min Topic guide: Decision Maths: Algorithms, Sorting and Bin Packingp3
  2. 02Decision Maths: Graphs, Trees and Minimum Spanning Trees10 questions · 73 marks · about 95 min Topic guide: Decision Maths: Graphs, Trees and Minimum Spanning Treesp10
  3. 03Decision Maths: Shortest Paths and Route Inspection10 questions · 88 marks · about 115 min Topic guide: Decision Maths: Shortest Paths and Route Inspectionp16
  4. 04Decision Maths: Critical Path Analysis and Linear Programming10 questions · 77 marks · about 100 min Topic guide: Decision Maths: Critical Path Analysis and Linear Programmingp25
  5. 05Decision: Algorithms and Graph Theory Depth9 questions · 68 marks · about 85 min Topic guide: Decision: Algorithms and Graph Theory Depthp34
  6. 06Decision: Linear Programming and Critical Path Depth12 questions · 101 marks · about 130 min Topic guide: Decision: Linear Programming and Critical Path Depthp39
  7. AnswersMark schemes for every chapterp52

Each chapter is drawn from one of our worksheet packs. Follow a chapter title for the full pack on its own page, or browse every A Level Further Maths pack. Every book on the shelf is a complete printable workbook of up to 120 A4 pages.

Explore this volume

A Level Further Maths Decision Topic Workbook includes Decision Maths: Algorithms, Sorting and Bin Packing (from page 3); Decision Maths: Graphs, Trees and Minimum Spanning Trees (from page 10); Decision Maths: Shortest Paths and Route Inspection (from page 16); Decision Maths: Critical Path Analysis and Linear Programming (from page 25); Decision: Algorithms and Graph Theory Depth (from page 34); Decision: Linear Programming and Critical Path Depth (from page 39).

Worked question 4 - Decision: Algorithms and Graph Theory Depth

Open the included worksheet

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.

Answer and mark scheme

Question 4

CreditAnswer or working
0Level 0 No relevant technique correctly matched to any of the three problems, or the response does not address the question.
1-2Level 1 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.
3-4Level 2 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.
5-6Level 3 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).

Answer: Open response; assessed against the levels of response criteria above using the indicative content as a guide.

Question 5 - Decision: Algorithms and Graph Theory Depth

Open the included worksheet

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)

Answer and mark scheme

Question 5

CreditAnswer or working
M1(a) attempts edges in increasing order of distance: QR(90), PQ(120), RS(150), ST(180), PR(200), ...
A1(a) correctly accepts QR(90), PQ(120), RS(150), ST(180), connecting all five checkpoints with 4 edges and no cycle
A1(a) total minimum length = 90+120+150+180 = 540 (m) cao
B1(a) correctly rejects an edge that would form a cycle, e.g. PR(200), since P and R are already connected via P-Q-R using the edges already accepted (oe)
M1(b) P permanently labelled 0; initial working values Q = 120 (via P), R = 200 (via P), S = 340 (via P)
A1(b) Q permanently labelled second, value 120
A1(b) R permanently labelled third, value 200 (via P); notes Q's route to R, 120+90=210, is not an improvement
A1(b) S permanently labelled fourth, value 340 (via P); notes R's routes to S (200+150=350) and T (200+210=410) are not improvements over the best values already known
A1(b) T permanently labelled fifth (last), value 380 (via Q, since 120+260=380); route P-Q-T stated
B1(c) total mass = 14+22+9+18+27+11+16 = 117 kg, lower bound = ceiling(117/45) = 3
M1(c) correct decreasing order: 27, 22, 18, 16, 14, 11, 9
A1(c) correct van contents: Van 1 {27, 18}, Van 2 {22, 16}, Van 3 {14, 11, 9}
B1(c) 3 vans used, matching the lower bound, so this packing is optimal cao
  • (a) Answer: Minimum cable length = 540 m, using edges QR, PQ, RS, ST; PR (200) is rejected as it would form a cycle.
  • (b) Answer: Order of permanent labelling: P(0), Q(120), R(200), S(340), T(380). Shortest route P-Q-T, length 380 m.
  • (c) Answer: Lower bound = 3 vans. Van 1: 27, 18 (45 kg). Van 2: 22, 16 (38 kg). Van 3: 14, 11, 9 (34 kg). 3 vans used, matching the lower bound.

Question 8 - Decision: Algorithms and Graph Theory Depth

Open the included worksheet

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)

Answer and mark scheme

Question 8

CreditAnswer or working
B1(a) A, B, G, H cao
B1(b) correctly lists the three possible pairings: (AB and GH), (AG and BH), (AH and BG)
M1(b) valid method: compares alternative routes rather than assuming direct arcs are always shortest
A1(b) pairing (AB, GH): shortest AB = 6 (direct), shortest GH = 3 (direct); total = 9
A1(b) pairing (AG, BH): shortest AG = 13 (via A-H-G, 10+3), shortest BH = 16 (via B-A-H, 6+10); total = 29
A1(b) 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
A1(b) correctly identifies (AB, GH) = 9 as the minimum of the three pairings
  • (a) Answer: A, B, G, H.
  • (b) Answer: (AB, GH) = 9; (AG, BH) = 29; (AH, BG) = 29. Minimum pairing: AB and GH.

Question 8 - Decision Maths: Graphs, Trees and Minimum Spanning Trees

Open the included worksheet

A network of relay stations A, B, C, D, E, F, G is to be connected by fibre-optic cable. The possible direct links and their lengths, in km, are: AB=5, AC=8, AD=10, BC=3, BE=7, CD=4, CE=6, CF=9, DF=5, EF=2, EG=8, FG=3. Kruskal's algorithm is to be used to find a minimum spanning tree for this network.
(a)State the two key steps of Kruskal's algorithm for finding a minimum spanning tree.(2)
(b)Apply Kruskal's algorithm to the network, listing the edges in the order they are considered and stating whether each is accepted or rejected.(5)
(c)State the total weight of the minimum spanning tree found in part (b).(1)
(d)Verify that the tree found in part (b) uses the correct number of edges for a spanning tree of this network.(1)
(e)A new relay station, H, is to be added, connected only to G by a new link GH = 5 km, at a cost of £3000 per km. State the new total weight of the minimum spanning tree once H is included, and find the total cost of the resulting network.(2)

Answer and mark scheme

Question 8

CreditAnswer or working
B1(a) consider the edges in ascending order of weight (oe)
B1(a) an edge is added unless it would form a cycle with edges already selected; the process stops once all vertices are connected, i.e. n - 1 edges have been chosen (oe)
M1(b) edges sorted into ascending order: EF(2), BC(3), FG(3), CD(4), AB(5), DF(5), CE(6), BE(7), AC(8), EG(8), CF(9), AD(10)
M1(b) EF, BC, FG, CD each correctly accepted, forming no cycle with the edges already chosen
M1(b) AB correctly accepted, then DF correctly accepted as it joins the two separate components {A,B,C,D} and {E,F,G} (oe)
A1(b) remaining edges CE, BE, AC, EG, CF, AD all correctly rejected, each forming a cycle with edges already accepted
A1(b) final minimum spanning tree correctly stated as {AB, BC, CD, DF, EF, FG}, using 6 edges to connect all 7 vertices
B1(c) 22 (km) ft their tree from part (b)
B1(d) 6 edges are used, and 7 - 1 = 6, so the number of edges is consistent with a spanning tree of a 7-vertex network cao
M1(e) new total weight = 22 + 5 = 27 (ft their part (c))
A1(e) cost = 27 x 3000 = £81,000 cao
  • (a) Answer: Sort edges by ascending weight; add each edge unless it forms a cycle, stopping once n - 1 edges have been chosen.
  • (b) Answer: Minimum spanning tree: {AB, BC, CD, DF, EF, FG}.
  • (c) Answer: 22 km
  • (d) Answer: 6 edges = 7 - 1, so the tree is a valid spanning tree.
  • (e) Answer: New weight = 27 km; total cost = £81 000.

Question 9 - Decision Maths: Graphs, Trees and Minimum Spanning Trees

Open the included worksheet

The table below shows the direct distances, in km, between six market towns A, B, C, D, E, F that a regional council wishes to connect with a new fibre-optic network, following existing roads only where a distance is given (a dash indicates no direct road).
ABCDEF
A-12-9-14
B12-7-11-
C-7-6108
D9-6-5-
E-11105-4
F14-8-4-
(a)State the number of edges required in a minimum spanning tree connecting all 6 towns.(1)
(b)Use Prim's algorithm, starting at A, to find a minimum spanning tree for this network. Show, at each stage, the town added to the tree and the length of road used to connect it.(9)
(c)State the total length of cable required for the minimum spanning tree found in part (b).(1)
(d)Verify your answer to part (c) by applying Kruskal's algorithm to the same network and comparing the total weight obtained.(2)

Answer and mark scheme

Question 9

CreditAnswer or working
B1(a) 5 cao
M1(b) AD=9 selected, D added (rejecting AB=12, AF=14)
M1(b) DE=5 selected, E added (comparing AB=12, AF=14, DC=6, DE=5)
M1(b) EF=4 selected, F added
M1(b) DC=6 selected, C added (rejecting EC=10, EB=11, FC=8)
A1(b) BC=7 selected, B added (rejecting AB=12, EB=11)
A1(b) correct order of towns added stated: D, E, F, C, B
A1(b) correct final edge set stated: {AD, DE, EF, DC, BC}
B1(b) correct method shown of eliminating (crossing out) the column of any town already in the tree when searching for the next minimum entry (oe)
B1(b) tree confirmed to use 5 edges connecting all 6 towns with no cycles
B1(c) 31 (km) ft their tree from part (b)
M1(d) Kruskal's algorithm correctly applied: EF(4), DE(5), CD(6), BC(7) accepted in order; CF(8) rejected as it would form a cycle; AD(9) accepted
A1(d) total = 31 (km), matching part (c) and confirming the minimum spanning tree weight cao
  • (a) Answer: 5
  • (b) Answer: Order of addition: D, E, F, C, B. Tree = {AD, DE, EF, DC, BC}.
  • (c) Answer: 31 km
  • (d) Answer: Kruskal's algorithm also gives 31 km, confirming part (c).

More A Level books

Want a different mix of topics?

Sitting an exam soon? Build a A Level Further Maths mock paper or print a ready-made one.