Skip to the worksheet
Revision Library
Choose a subject

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.

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.

Revision Library
revisionlibrary.co.uk
A-Level · Further Decision Mathematics (Algorithms and Graph Theory Depth)

4.5 Decision: Algorithms and Graph Theory Depth

EDEXCEL 9FM0 · Calculator allowed · about 230 minutes
Total Marks
Name: _______________________________    Date: ____ / ____ / ______
Answer ALL questions. Show all your working.
1
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 1 is 6 marks)
2
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 2 is 8 marks)
3
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 3 is 13 marks)
4
A network has vertices A, B, C, D, E, F, G and the following weighted arcs: AD = 18, AE = 25, BC = 33, BD = 15, BF = 32, CG = 5, DE = 6, DF = 19, EF = 24, EG = 28.
(a)Use Kruskal's algorithm to find a minimum spanning tree. List the arcs in the order in which you add them to the tree.(3)
(b)State the total weight of your minimum spanning tree.(1)
(c)Use Prim's algorithm starting at vertex A to find the minimum spanning tree, listing the arcs in the order added.(3)
(Total for Question 4 is 7 marks)
5
A network has vertices A, B, C, D, E, F, G and the following weighted arcs: AC = 8, AG = 18, BC = 7, BD = 27, BE = 26, BF = 11, BG = 39, CE = 24, DG = 37.
(a)Use Kruskal's algorithm to find a minimum spanning tree. List the arcs in the order in which you add them to the tree.(3)
(b)State the total weight of your minimum spanning tree.(1)
(c)Use Prim's algorithm starting at vertex A to find the minimum spanning tree, listing the arcs in the order added.(3)
(Total for Question 5 is 7 marks)
6
The list 2, 30, 52, 50, 8, 20, 59, 41, 31 is to be sorted into ascending order using a bubble sort. In each pass, adjacent items are compared from the left and swapped if they are in the wrong order.
(a)Show the list after the first pass and state the number of swaps made in the first pass.(3)
(b)Show the list after the second pass.(2)
(c)State the number of passes needed to sort the list completely, not counting a final pass in which no swaps are made, and the total number of swaps.(2)
(Total for Question 6 is 7 marks)
7
The items with the following sizes are to be packed into bins of capacity 50: 18, 5, 40, 28, 31, 8, 26, 20, 35, 13.
(a)Find a lower bound for the number of bins needed.(2)
(b)Use the first-fit algorithm, taking the items in the order given, to pack the items into bins. State the contents of each bin.(3)
(c)Use the first-fit decreasing algorithm to pack the items. State the number of bins used and the contents of each bin.(3)
(Total for Question 7 is 8 marks)
8
The list 53, 14, 25, 2, 11, 1, 33, 23, 39 is to be sorted into ascending order using a bubble sort. In each pass, adjacent items are compared from the left and swapped if they are in the wrong order.
(a)Show the list after the first pass and state the number of swaps made in the first pass.(3)
(b)Show the list after the second pass.(2)
(c)State the number of passes needed to sort the list completely, not counting a final pass in which no swaps are made, and the total number of swaps.(2)
(Total for Question 8 is 7 marks)
9
The graph G has vertices A, B, C, D, E, F and edges AB, AC, AD, AE, BC, BE, BF, CD, CE, CF, EF.
(a)Find the degree of each vertex, and verify the handshaking lemma for G.(3)
(b)Classify G as Eulerian, semi-Eulerian or neither, giving a reason.(2)
(c)The complete graph K9 has 9 vertices, each joined to every other. Find its number of edges, and state whether it is Eulerian.(3)
(Total for Question 9 is 8 marks)
10
The items with the following sizes are to be packed into bins of capacity 20: 7, 12, 7, 5, 8, 8, 3, 5, 11, 7.
(a)Find a lower bound for the number of bins needed.(2)
(b)Use the first-fit algorithm, taking the items in the order given, to pack the items into bins. State the contents of each bin.(3)
(c)Use the first-fit decreasing algorithm to pack the items. State the number of bins used and the contents of each bin.(3)
(Total for Question 10 is 8 marks)
11
A network has vertices A, B, C, D, E, F and the following weighted arcs: AB = 36, AF = 4, BE = 32, BF = 6, CD = 22, CE = 5, DE = 14, DF = 39, EF = 26.
(a)Use Kruskal's algorithm to find a minimum spanning tree. List the arcs in the order in which you add them to the tree.(3)
(b)State the total weight of your minimum spanning tree.(1)
(c)Use Prim's algorithm starting at vertex A to find the minimum spanning tree, listing the arcs in the order added.(3)
(Total for Question 11 is 7 marks)
12
The graph G has vertices A, B, C, D, E and edges AB, AC, AD, AE, BC, BD, BE, CD, CE, DE.
(a)Find the degree of each vertex, and verify the handshaking lemma for G.(3)
(b)Classify G as Eulerian, semi-Eulerian or neither, giving a reason.(2)
(c)The complete graph K8 has 8 vertices, each joined to every other. Find its number of edges, and state whether it is Eulerian.(3)
(Total for Question 12 is 8 marks)
13
The graph G has vertices A, B, C, D, E, F and edges AB, AD, AE, BC, BD, BF, CD, CE, DE, EF.
(a)Find the degree of each vertex, and verify the handshaking lemma for G.(3)
(b)Classify G as Eulerian, semi-Eulerian or neither, giving a reason.(2)
(c)The complete graph K5 has 5 vertices, each joined to every other. Find its number of edges, and state whether it is Eulerian.(3)
(Total for Question 13 is 8 marks)
14
The graph G has vertices A, B, C, D, E and edges AB, AD, AE, BC, BD, CE.
(a)Find the degree of each vertex, and verify the handshaking lemma for G.(3)
(b)Classify G as Eulerian, semi-Eulerian or neither, giving a reason.(2)
(c)The complete graph K5 has 5 vertices, each joined to every other. Find its number of edges, and state whether it is Eulerian.(3)
(Total for Question 14 is 8 marks)
15
A network has vertices A, B, C, D, E, F and the following weighted arcs: AB = 29, AC = 36, BC = 24, BF = 12, CD = 2, CE = 14, CF = 5, DE = 9, DF = 16.
(a)Use Kruskal's algorithm to find a minimum spanning tree. List the arcs in the order in which you add them to the tree.(3)
(b)State the total weight of your minimum spanning tree.(1)
(c)Use Prim's algorithm starting at vertex A to find the minimum spanning tree, listing the arcs in the order added.(3)
(Total for Question 15 is 7 marks)
16
The items with the following sizes are to be packed into bins of capacity 30: 3, 11, 20, 26, 17, 18, 21, 4.
(a)Find a lower bound for the number of bins needed.(2)
(b)Use the first-fit algorithm, taking the items in the order given, to pack the items into bins. State the contents of each bin.(3)
(c)Use the first-fit decreasing algorithm to pack the items. State the number of bins used and the contents of each bin.(3)
(Total for Question 16 is 8 marks)
17
The list 24, 58, 28, 46, 17, 25, 30, 36 is to be sorted into ascending order using a bubble sort. In each pass, adjacent items are compared from the left and swapped if they are in the wrong order.
(a)Show the list after the first pass and state the number of swaps made in the first pass.(3)
(b)Show the list after the second pass.(2)
(c)State the number of passes needed to sort the list completely, not counting a final pass in which no swaps are made, and the total number of swaps.(2)
(Total for Question 17 is 7 marks)
18
A network has vertices A, B, C, D, E, F, G and the following weighted arcs: AB = 33, AC = 38, AE = 15, AG = 5, BE = 29, CF = 13, CG = 30, DE = 28, DF = 21, EG = 18, FG = 6.
(a)Use Kruskal's algorithm to find a minimum spanning tree. List the arcs in the order in which you add them to the tree.(3)
(b)State the total weight of your minimum spanning tree.(1)
(c)Use Prim's algorithm starting at vertex A to find the minimum spanning tree, listing the arcs in the order added.(3)
(Total for Question 18 is 7 marks)
19
The list 31, 26, 55, 59, 49, 39, 53, 22 is to be sorted into ascending order using a bubble sort. In each pass, adjacent items are compared from the left and swapped if they are in the wrong order.
(a)Show the list after the first pass and state the number of swaps made in the first pass.(3)
(b)Show the list after the second pass.(2)
(c)State the number of passes needed to sort the list completely, not counting a final pass in which no swaps are made, and the total number of swaps.(2)
(Total for Question 19 is 7 marks)
20
The list 56, 5, 15, 54, 44, 31, 9, 50 is to be sorted into ascending order using a bubble sort. In each pass, adjacent items are compared from the left and swapped if they are in the wrong order.
(a)Show the list after the first pass and state the number of swaps made in the first pass.(3)
(b)Show the list after the second pass.(2)
(c)State the number of passes needed to sort the list completely, not counting a final pass in which no swaps are made, and the total number of swaps.(2)
(Total for Question 20 is 7 marks)
21
A water company is planning new pipeline connections between seven reservoirs, A to G. The table below gives the cost, in £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 21 is 7 marks)
22
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 22 is 7 marks)
23
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 23 is 7 marks)
24
This question continues from Question 23, 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 24 is 3 marks)
Mark scheme · 4.5 Decision: Algorithms and Graph Theory Depth

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.

Question 1

6 marks
Did your answer earn the marks?

Question 2

8 marks
Did your answer earn the marks?

Question 3

13 marks
Did your answer earn the marks?

Question 4

7 marks
Did your answer earn the marks?

Question 5

7 marks
Did your answer earn the marks?

Question 6

7 marks
Did your answer earn the marks?

Question 7

8 marks
Did your answer earn the marks?

Question 8

7 marks
Did your answer earn the marks?

Question 9

8 marks
Did your answer earn the marks?

Question 10

8 marks
Did your answer earn the marks?

Question 11

7 marks
Did your answer earn the marks?

Question 12

8 marks
Did your answer earn the marks?

Question 13

8 marks
Did your answer earn the marks?

Question 14

8 marks
Did your answer earn the marks?

Question 15

7 marks
Did your answer earn the marks?

Question 16

8 marks
Did your answer earn the marks?

Question 17

7 marks
Did your answer earn the marks?

Question 18

7 marks
Did your answer earn the marks?

Question 19

7 marks
Did your answer earn the marks?

Question 20

7 marks
Did your answer earn the marks?

Question 21

7 marks
Did your answer earn the marks?

Question 22

7 marks
Did your answer earn the marks?

Question 23

7 marks
Did your answer earn the marks?

Question 24

3 marks
Did your answer earn the marks?
Mark my answers

Worksheets are written for Revision Library and come with a full mark scheme; a few English packs quote an out-of-copyright text, and name it on the page. Exam board names and specification codes say which qualification a pack suits: we are not affiliated with, endorsed by or approved by any exam board, and no past-paper question is reproduced here. Rights queries: hello@revisionlibrary.co.uk