Decision: Algorithms and Graph Theory Depth - Worksheets, Questions and Revision
24 original exam-style questions - 8 pages of questions with a full mark scheme - free printable PDF.
Decision: Algorithms and Graph Theory Depth revision guideWrite-in editionMore A Level Further Maths practiceMock exams
This topic is chapter 5 of A Level Further Maths Decision Topic Workbook and chapter 3 of A Level Further Maths 10-Minute Tests 2.
4.5 Decision: Algorithms and Graph Theory Depth
42, 17, 56, 8, 31, 24, 63
13, 8, 19, 11, 6, 14, 9, 17
AB = 7, AC = 9, BC = 5, BD = 8, CD = 6, DE = 4, EF = 3, EG = 9, FG = 6, CE = 10, BE = 11, DF = 12
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 -
Question 1
- (a) first pivot = 42 identified, with correct sublists {17, 8, 31, 24} (< 42) and {56, 63} (≥ 42)M1
- (a) correct second-stage split on {17, 8, 31, 24}: pivot 17, giving {8} and {31, 24}A1
- (a) correct second-stage split on {56, 63}: pivot 56, giving { } and {63}A1
- (a) correct third-stage split on {31, 24}: pivot 31, giving {24} and { }A1
- (a) correct final sorted list 8, 17, 24, 31, 42, 56, 63 cao, with all four pivots (42, 17, 56, 31) correctly identifiedB1
- (a) Answer: Final sorted list: 8, 17, 24, 31, 42, 56, 63.
- (b) 4 pivots caoB1
- (b) Answer: 4 pivots.
Question 2
- (a) total weight = 13+8+19+11+6+14+9+17 = 97 kgM1
- (a) lower bound = ceiling(97/30) = 4 caoA1
- (a) Answer: Lower bound = 4 bins.
- (b) 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 itM1
- (b) correct bin contents: Bin 1 {13, 8, 6}, Bin 2 {19, 11}, Bin 3 {14, 9}, Bin 4 {17}A1
- (b) 4 bins used caoB1
- (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) correct decreasing order: 19, 17, 14, 13, 11, 9, 8, 6M1
- (c) correct bin contents: Bin 1 {19, 11}, Bin 2 {17, 13}, Bin 3 {14, 9, 6}, Bin 4 {8}A1
- (c) 4 bins used cao, matching the lower bound found in part (a), so this packing is optimalB1
- (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 3
- (a) attempts edges in increasing order of distance: QR(90), PQ(120), RS(150), ST(180), PR(200), ...M1
- (a) correctly accepts QR(90), PQ(120), RS(150), ST(180), connecting all five checkpoints with 4 edges and no cycleA1
- (a) total minimum length = 90+120+150+180 = 540 (m) caoA1
- (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)B1
- (a) Answer: Minimum cable length = 540 m, using edges QR, PQ, RS, ST; PR (200) is rejected as it would form a cycle.
- (b) P permanently labelled 0; initial working values Q = 120 (via P), R = 200 (via P), S = 340 (via P)M1
- (b) Q permanently labelled second, value 120A1
- (b) R permanently labelled third, value 200 (via P); notes Q's route to R, 120+90=210, is not an improvementA1
- (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 knownA1
- (b) T permanently labelled fifth (last), value 380 (via Q, since 120+260=380); route P-Q-T statedA1
- (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) total mass = 14+22+9+18+27+11+16 = 117 kg, lower bound = ceiling(117/45) = 3B1
- (c) correct decreasing order: 27, 22, 18, 16, 14, 11, 9M1
- (c) correct van contents: Van 1 {27, 18}, Van 2 {22, 16}, Van 3 {14, 11, 9}A1
- (c) 3 vans used, matching the lower bound, so this packing is optimal caoB1
- (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 4
- (a) sorts the arcs in increasing order of weight and selects the smallestM1
- (a) adds each next smallest arc that does not form a cycleM1
- (a) arcs selected: CG (5), DE (6), BD (15), AD (18), DF (19), EG (28)A1
- (a) Answer: CG (5), DE (6), BD (15), AD (18), DF (19), EG (28)
- (b) 91B1
- (b) Answer: 91
- (c) starts at A and adds the shortest arc joining a tree vertex to a non-tree vertex each timeM1
- (c) first three arcs correctA1
- (c) arcs added: AD (18), DE (6), BD (15), DF (19), EG (28), CG (5)A1
- (c) Answer: AD (18), DE (6), BD (15), DF (19), EG (28), CG (5)
Question 5
- (a) sorts the arcs in increasing order of weight and selects the smallestM1
- (a) adds each next smallest arc that does not form a cycleM1
- (a) arcs selected: BC (7), AC (8), BF (11), AG (18), CE (24), BD (27)A1
- (a) Answer: BC (7), AC (8), BF (11), AG (18), CE (24), BD (27)
- (b) 95B1
- (b) Answer: 95
- (c) starts at A and adds the shortest arc joining a tree vertex to a non-tree vertex each timeM1
- (c) first three arcs correctA1
- (c) arcs added: AC (8), BC (7), BF (11), AG (18), CE (24), BD (27)A1
- (c) Answer: AC (8), BC (7), BF (11), AG (18), CE (24), BD (27)
Question 6
- (a) compares adjacent pairs from the left, swapping when the left item is largerM1
- (a) list after pass 1: 2, 30, 50, 8, 20, 52, 41, 31, 59A1
- (a) 5 swapsB1
- (a) Answer: 2, 30, 50, 8, 20, 52, 41, 31, 59; 5 swaps
- (b) repeats the process, ignoring the final item (already in place)M1
- (b) 2, 30, 8, 20, 50, 41, 31, 52, 59A1
- (b) Answer: 2, 30, 8, 20, 50, 41, 31, 52, 59
- (c) 4 passesB1
- (c) 14 swaps in totalB1
- (c) Answer: 4 passes, 14 swaps
Question 7
- (a) total size = 224M1
- (a) 224/50 = 4.48, so at least 5 binsA1
- (a) Answer: 5
- (b) places each item in the first bin with enough room, in the order givenM1
- (b) first bins correctA1
- (b) bins: (18, 5, 8, 13); (40); (28, 20); (31); (26); (35)A1
- (b) Answer: (18, 5, 8, 13); (40); (28, 20); (31); (26); (35)
- (c) sorts the items into descending orderM1
- (c) applies first-fit to the sorted listM1
- (c) 5 bins: (40, 8); (35, 13); (31, 18); (28, 20); (26, 5)A1
- (c) Answer: 5 bins: (40, 8); (35, 13); (31, 18); (28, 20); (26, 5)
Question 8
- (a) compares adjacent pairs from the left, swapping when the left item is largerM1
- (a) list after pass 1: 14, 25, 2, 11, 1, 33, 23, 39, 53A1
- (a) 8 swapsB1
- (a) Answer: 14, 25, 2, 11, 1, 33, 23, 39, 53; 8 swaps
- (b) repeats the process, ignoring the final item (already in place)M1
- (b) 14, 2, 11, 1, 25, 23, 33, 39, 53A1
- (b) Answer: 14, 2, 11, 1, 25, 23, 33, 39, 53
- (c) 5 passesB1
- (c) 18 swaps in totalB1
- (c) Answer: 5 passes, 18 swaps
Question 9
- (a) counts the edges at each vertexM1
- (a) degrees: A 4, B 4, C 5, D 2, E 4, F 3A1
- (a) sum of degrees = 22 = 2 x 11 edgesA1
- (a) Answer: A 4, B 4, C 5, D 2, E 4, F 3; sum 22
- (b) counts the vertices of odd degree: C, FM1
- (b) semi-Eulerian (has an Eulerian trail but no cycle)A1
- (b) Answer: semi-Eulerian (has an Eulerian trail but no cycle)
- (c) 9(9 - 1)/2M1
- (c) 36 edgesA1
- (c) each vertex has degree 8, which is even, so K9 is EulerianB1
- (c) Answer: 36 edges; Eulerian
Question 10
- (a) total size = 73M1
- (a) 73/20 = 3.65, so at least 4 binsA1
- (a) Answer: 4
- (b) places each item in the first bin with enough room, in the order givenM1
- (b) first bins correctA1
- (b) bins: (7, 12); (7, 5, 8); (8, 3, 5); (11, 7)A1
- (b) Answer: (7, 12); (7, 5, 8); (8, 3, 5); (11, 7)
- (c) sorts the items into descending orderM1
- (c) applies first-fit to the sorted listM1
- (c) 4 bins: (12, 8); (11, 8); (7, 7, 5); (7, 5, 3)A1
- (c) Answer: 4 bins: (12, 8); (11, 8); (7, 7, 5); (7, 5, 3)
Question 11
- (a) sorts the arcs in increasing order of weight and selects the smallestM1
- (a) adds each next smallest arc that does not form a cycleM1
- (a) arcs selected: AF (4), CE (5), BF (6), DE (14), EF (26)A1
- (a) Answer: AF (4), CE (5), BF (6), DE (14), EF (26)
- (b) 55B1
- (b) Answer: 55
- (c) starts at A and adds the shortest arc joining a tree vertex to a non-tree vertex each timeM1
- (c) first three arcs correctA1
- (c) arcs added: AF (4), BF (6), EF (26), CE (5), DE (14)A1
- (c) Answer: AF (4), BF (6), EF (26), CE (5), DE (14)
Question 12
- (a) counts the edges at each vertexM1
- (a) degrees: A 4, B 4, C 4, D 4, E 4A1
- (a) sum of degrees = 20 = 2 x 10 edgesA1
- (a) Answer: A 4, B 4, C 4, D 4, E 4; sum 20
- (b) counts the vertices of odd degree: noneM1
- (b) Eulerian (has an Eulerian cycle)A1
- (b) Answer: Eulerian (has an Eulerian cycle)
- (c) 8(8 - 1)/2M1
- (c) 28 edgesA1
- (c) each vertex has degree 7, which is odd, so K8 is not EulerianB1
- (c) Answer: 28 edges; not Eulerian
Question 13
- (a) counts the edges at each vertexM1
- (a) degrees: A 3, B 4, C 3, D 4, E 4, F 2A1
- (a) sum of degrees = 20 = 2 x 10 edgesA1
- (a) Answer: A 3, B 4, C 3, D 4, E 4, F 2; sum 20
- (b) counts the vertices of odd degree: A, CM1
- (b) semi-Eulerian (has an Eulerian trail but no cycle)A1
- (b) Answer: semi-Eulerian (has an Eulerian trail but no cycle)
- (c) 5(5 - 1)/2M1
- (c) 10 edgesA1
- (c) each vertex has degree 4, which is even, so K5 is EulerianB1
- (c) Answer: 10 edges; Eulerian
Question 14
- (a) counts the edges at each vertexM1
- (a) degrees: A 3, B 3, C 2, D 2, E 2A1
- (a) sum of degrees = 12 = 2 x 6 edgesA1
- (a) Answer: A 3, B 3, C 2, D 2, E 2; sum 12
- (b) counts the vertices of odd degree: A, BM1
- (b) semi-Eulerian (has an Eulerian trail but no cycle)A1
- (b) Answer: semi-Eulerian (has an Eulerian trail but no cycle)
- (c) 5(5 - 1)/2M1
- (c) 10 edgesA1
- (c) each vertex has degree 4, which is even, so K5 is EulerianB1
- (c) Answer: 10 edges; Eulerian
Question 15
- (a) sorts the arcs in increasing order of weight and selects the smallestM1
- (a) adds each next smallest arc that does not form a cycleM1
- (a) arcs selected: CD (2), CF (5), DE (9), BF (12), AB (29)A1
- (a) Answer: CD (2), CF (5), DE (9), BF (12), AB (29)
- (b) 57B1
- (b) Answer: 57
- (c) starts at A and adds the shortest arc joining a tree vertex to a non-tree vertex each timeM1
- (c) first three arcs correctA1
- (c) arcs added: AB (29), BF (12), CF (5), CD (2), DE (9)A1
- (c) Answer: AB (29), BF (12), CF (5), CD (2), DE (9)
Question 16
- (a) total size = 120M1
- (a) 120/30 = 4.00, so at least 4 binsA1
- (a) Answer: 4
- (b) places each item in the first bin with enough room, in the order givenM1
- (b) first bins correctA1
- (b) bins: (3, 11, 4); (20); (26); (17); (18); (21)A1
- (b) Answer: (3, 11, 4); (20); (26); (17); (18); (21)
- (c) sorts the items into descending orderM1
- (c) applies first-fit to the sorted listM1
- (c) 5 bins: (26, 4); (21, 3); (20); (18, 11); (17)A1
- (c) Answer: 5 bins: (26, 4); (21, 3); (20); (18, 11); (17)
Question 17
- (a) compares adjacent pairs from the left, swapping when the left item is largerM1
- (a) list after pass 1: 24, 28, 46, 17, 25, 30, 36, 58A1
- (a) 6 swapsB1
- (a) Answer: 24, 28, 46, 17, 25, 30, 36, 58; 6 swaps
- (b) repeats the process, ignoring the final item (already in place)M1
- (b) 24, 28, 17, 25, 30, 36, 46, 58A1
- (b) Answer: 24, 28, 17, 25, 30, 36, 46, 58
- (c) 4 passesB1
- (c) 13 swaps in totalB1
- (c) Answer: 4 passes, 13 swaps
Question 18
- (a) sorts the arcs in increasing order of weight and selects the smallestM1
- (a) adds each next smallest arc that does not form a cycleM1
- (a) arcs selected: AG (5), FG (6), CF (13), AE (15), DF (21), BE (29)A1
- (a) Answer: AG (5), FG (6), CF (13), AE (15), DF (21), BE (29)
- (b) 89B1
- (b) Answer: 89
- (c) starts at A and adds the shortest arc joining a tree vertex to a non-tree vertex each timeM1
- (c) first three arcs correctA1
- (c) arcs added: AG (5), FG (6), CF (13), AE (15), DF (21), BE (29)A1
- (c) Answer: AG (5), FG (6), CF (13), AE (15), DF (21), BE (29)
Question 19
- (a) compares adjacent pairs from the left, swapping when the left item is largerM1
- (a) list after pass 1: 26, 31, 55, 49, 39, 53, 22, 59A1
- (a) 5 swapsB1
- (a) Answer: 26, 31, 55, 49, 39, 53, 22, 59; 5 swaps
- (b) repeats the process, ignoring the final item (already in place)M1
- (b) 26, 31, 49, 39, 53, 22, 55, 59A1
- (b) Answer: 26, 31, 49, 39, 53, 22, 55, 59
- (c) 7 passesB1
- (c) 15 swaps in totalB1
- (c) Answer: 7 passes, 15 swaps
Question 20
- (a) compares adjacent pairs from the left, swapping when the left item is largerM1
- (a) list after pass 1: 5, 15, 54, 44, 31, 9, 50, 56A1
- (a) 7 swapsB1
- (a) Answer: 5, 15, 54, 44, 31, 9, 50, 56; 7 swaps
- (b) repeats the process, ignoring the final item (already in place)M1
- (b) 5, 15, 44, 31, 9, 50, 54, 56A1
- (b) Answer: 5, 15, 44, 31, 9, 50, 54, 56
- (c) 5 passesB1
- (c) 15 swaps in totalB1
- (c) Answer: 5 passes, 15 swaps
Question 21
- (a) attempts edges in increasing order of cost: EF(3), DE(4), BC(5), CD(6), FG(6), AB(7), ...M1
- (a) accepts EF(3), DE(4), BC(5), each correctly joining a new component with no cycleA1
- (a) accepts CD(6) and FG(6) (either order, since tied), each correctly joining a new componentA1
- (a) accepts AB(7), correctly completing the spanning treeA1
- (a) correctly states the tree is complete once 6 edges have been chosen, since a spanning tree of 7 reservoirs requires exactly 6 edgesB1
- (a) Answer: Accepted, in order: EF(3), DE(4), BC(5), CD(6), FG(6), AB(7). Tree complete with 6 edges.
- (b) 31 (i.e. £31,000) caoB1
- (b) Answer: 31 (£31,000).
- (c) 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)B1
- (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 22
- (a) starting town P noted; identifies PR = 4 as the least connection available from PM1
- (a) R added, connected via PR = 4A1
- (a) S added, connected via RS = 3 (the least value now available from {P, R} to the remaining towns)A1
- (a) Q added, connected via RQ = 5A1
- (a) T added, connected via ST = 6A1
- (a) U added, connected via TU = 4, completing the treeA1
- (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) 22 km caoB1
- (b) Answer: 22 km.
Question 23
- (a) A, B, G, H caoB1
- (a) Answer: A, B, G, H.
- (b) correctly lists the three possible pairings: (AB and GH), (AG and BH), (AH and BG)B1
- (b) valid method: compares alternative routes rather than assuming direct arcs are always shortestM1
- (b) pairing (AB, GH): shortest AB = 6 (direct), shortest GH = 3 (direct); total = 9A1
- (b) pairing (AG, BH): shortest AG = 13 (via A-H-G, 10+3), shortest BH = 16 (via B-A-H, 6+10); total = 29A1
- (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 = 29A1
- (b) correctly identifies (AB, GH) = 9 as the minimum of the three pairingsA1
- (b) Answer: (AB, GH) = 9; (AG, BH) = 29; (AH, BG) = 29. Minimum pairing: AB and GH.
Question 24
- (a) total length of network = 6+5+10+4+7+3+8+6+9+4+7+5+6+3 = 83 (m)B1
- (a) shortest route = 83 + 9 = 92 (m) cao (ft from the minimum pairing found in Question 23)B1
- (a) Answer: 92 m.
- (b) AB and GH (the two arcs making up the minimum pairing found in Question 23)B1
- (b) Answer: AB and GH.
Mark your answers
Check answers without an account. Some answers can be checked automatically; use the mark scheme to mark the rest.