June 2022: A level Paper 3D: Decision Mathematics 1

75 marks · 23 question parts · Question paper, mark scheme and examiner's report on Pearson's site

Question by question

QTopicMarksDifficulty
1(a) Algorithms, sorting, bin packing and graph theory 2 —
1(b) Algorithms, sorting, bin packing and graph theory 3 —
2(a) Minimum spanning trees (Prim, Kruskal) and shortest paths (Dijkstra, Floyd) 6 —
2(b) Route inspection and the travelling salesman problem 2 —
2(c) Route inspection and the travelling salesman problem 5 —
3(a) Minimum spanning trees (Prim, Kruskal) and shortest paths (Dijkstra, Floyd) 2 —
3(b) Minimum spanning trees (Prim, Kruskal) and shortest paths (Dijkstra, Floyd) 4 —
3(c) Route inspection and the travelling salesman problem 4 —
4(a) Linear programming: formulation, graphs and the Simplex algorithm 4 —
4(b) Linear programming: formulation, graphs and the Simplex algorithm 2 —
5(a) Critical path analysis 2 —
5(b) Critical path analysis 1 —
5(c) Critical path analysis 3 —
5(d) Critical path analysis 1 —
5(e) Critical path analysis 2 —
5(f) Critical path analysis 5 —
6(a) Algorithms, sorting, bin packing and graph theory 3 —
6(b) Algorithms, sorting, bin packing and graph theory 5 —
6(c) Algorithms, sorting, bin packing and graph theory 1 —
6(d) Algorithms, sorting, bin packing and graph theory 3 —
7(a) Linear programming: formulation, graphs and the Simplex algorithm 5 —
7(b) Linear programming: formulation, graphs and the Simplex algorithm 1 —
7(c) Linear programming: formulation, graphs and the Simplex algorithm 9 —

The questions

1(a)1(b)2(a)2(b)2(c)3(a)3(b)3(c)4(a)4(b)5(a)5(b)5(c)5(d)5(e)5(f)6(a)6(b)6(c)6(d)7(a)7(b)7(c)
June 2022 · Paper 3D (Decision 1) · Q1(a) 2 marks algorithms and graph theory
1. A gardener needs the following lengths of string. All lengths are in metres. 4.3 6.1 5.1 4.7 2.5 5.9 3.4 1.7 2.1 0.4 1.3 She cuts the lengths from balls of string. Each ball contains 10 m of string. (a) Calculate a lower bound for the number of balls of string the gardener needs. You must make your method clear. (2)
June 2022 · Paper 3D (Decision 1) · Q1(b) 3 marks algorithms and graph theory
(b) Use the first‑fit bin packing algorithm to determine how the lengths could be cut from the balls of string. (3)
June 2022 · Paper 3D (Decision 1) · Q2(a) 6 marks minimum spanning trees and shortest paths
2. B H E A C J K F G Figure 1 [The total weight of the network is 299] Figure 1 represents a network of cycle tracks between 10 landmarks, A, B, C, D, E, F, G, H, J and K. The number on each edge represents the length, in kilometres, of the corresponding track. One day, Blanche wishes to cycle from A to K. She wishes to minimise the distance she travels. (a) (i) Use Dijkstra’s algorithm to find the shortest path from A to K. (ii) State the length of the shortest path from A to K. (6)
June 2022 · Paper 3D (Decision 1) · Q2(b) 2 marks route inspection and travelling salesman
The cycle tracks between the landmarks now need to be inspected. Blanche must travel along each track at least once. She wishes to minimise the length of her inspection route. Blanche will start her inspection route at D and finish at E. (b) (i) State the edges that will need to be traversed twice. (ii) Find the length of Blanche’s route. (2)
June 2022 · Paper 3D (Decision 1) · Q2(c) 5 marks route inspection and travelling salesman
It is now decided to start the inspection route at A and finish at K. Blanche must minimise the length of her route and travel along each track at least once. (c) By considering the pairings of all relevant nodes, find the length of Blanche’s new route. You must make your method and working clear. (5)
June 2022 · Paper 3D (Decision 1) · Q3(a) 2 marks minimum spanning trees and shortest paths
3. The initial distance matrix (Table 1) shows the lengths, in metres, of the corridors connecting six classrooms, A, B, C, D, E and F, in a school. For safety reasons, some of the corridors are one‑way only. A B C E F A – B – ∞ ∞ C – ∞ ∞ – ∞ E ∞ ∞ – F ∞ ∞ – Table 1 (a) By adding the arcs from vertex A, along with their weights, complete the drawing of this network on Diagram 1 in the answer book. (2)
June 2022 · Paper 3D (Decision 1) · Q3(b) 4 marks minimum spanning trees and shortest paths
Floyd’s algorithm is to be used to find the complete network of shortest distances between the six classrooms. The distance matrix after two iterations of Floyd’s algorithm is shown in Table 2. A B C E F A – B – C – – E ∞ ∞ – F – Table 2 (b) Perform the next two iterations of Floyd’s algorithm that follow from Table 2. You should show the distance matrix after each iteration. (4)
June 2022 · Paper 3D (Decision 1) · Q3(c) 4 marks route inspection and travelling salesman
The final distance matrix after completion of Floyd’s algorithm is shown in Table 3. A B C E F A – B – C – – E – F – Table 3 Yinka must visit each classroom. He will start and finish at E and wishes to minimise the total distance travelled. (c) (i) Use the nearest neighbour algorithm, starting at E, to find two Hamiltonian cycles in the completed network of shortest distances. (ii) Find the length of each of the two cycles. (iii) State, with a reason, which of the two cycles provides the better upper bound for the length of Yinka’s route. (4)
June 2022 · Paper 3D (Decision 1) · Q4(a) 4 marks linear programming
4. A linear programming problem in x, y and z is to be solved using the big‑M method. The initial tableau is shown below. b.v. x y z s1 s2 s3 a1 a2 Value s1 a1 –2 –1 a2 –4 –1 P 2 – 4M –3 + 2M –1 + 2M M M –20M (a) Using the information in the above tableau, formulate the linear programming problem. You should • list each of the constraints as an inequality • state the two possible objectives (4)
June 2022 · Paper 3D (Decision 1) · Q4(b) 2 marks linear programming
(b) Obtain the most efficient pivot for a first iteration of the big‑M method. You must give reasons for your answer. (2)
June 2022 · Paper 3D (Decision 1) · Q5(a) 2 marks critical path analysis
5. D(x) A(4) G(3) J(7) B(5) E(4) C(7) H(5) K(6) F(x) Figure 2 The network in Figure 2 shows the activities that need to be completed for a project. Each activity is represented by an arc and the duration of the activity, in days, is shown in brackets. The early event times are shown in Figure 2. (a) Complete Table 1 in the answer book to show the immediately preceding activities for each activity. (2)
June 2022 · Paper 3D (Decision 1) · Q5(b) 1 mark critical path analysis
It is given that 4 < x m (b) State the largest possible integer value of m. (1)
June 2022 · Paper 3D (Decision 1) · Q5(c) 3 marks critical path analysis
(c) (i) Complete Diagram 1 in the answer book to show the late event times. (ii) State the activities that must be critical. (3)
June 2022 · Paper 3D (Decision 1) · Q5(d) 1 mark critical path analysis
(d) Calculate the total float for activity G. (1)
June 2022 · Paper 3D (Decision 1) · Q5(e) 2 marks critical path analysis
The resource histogram in Figure 3 shows the number of workers required when each activity starts at its earliest possible time. The histogram also shows which activities happen at each time. number of workers C F F B H C F J K K A B E G H C J 22 time Figure 3 (e) Complete Table 2 in the answer book to show the number of workers required for each activity of the project. (2)
June 2022 · Paper 3D (Decision 1) · Q5(f) 5 marks critical path analysis
(f) Draw a Gantt chart on Grid 1 in the answer book to represent the activity network. (5)
June 2022 · Paper 3D (Decision 1) · Q6(a) 3 marks algorithms and graph theory
6. The following algorithm determines the number of comparisons made when Prim’s algorithm is applied to Kn Step 1 Start Step 2 Input the value of n Step 3 Let a = 1 Step 4 Let b = n – 2 Step 5 Let c = b Step 6 Let a = a + 1 Step 7 Let b = b – 1 Step 8 Let c = c + (a x b) + (a – 1) Step 9 If b > 0 go to Step 6 Step 10 Output c Step 11 Stop (a) For K5, complete the table in the answer book to show the results obtained at each step of the algorithm. (3)
June 2022 · Paper 3D (Decision 1) · Q6(b) 5 marks algorithms and graph theory
B C A 24 14 E Figure 4 The weights of the ten arcs in Figure 4 are 17 21 24 14 23 13 15 19 28 20 (b) (i) Starting at the left‑hand end of the above list, sort the list into ascending order using bubble sort. You need only write down the state of the list at the end of each pass. (ii) Find the total number of comparisons performed during the sort. (5)
June 2022 · Paper 3D (Decision 1) · Q6(c) 1 mark algorithms and graph theory
(c) Find the maximum total number of comparisons required to sort the weights of the 10 arcs of K5 into ascending order using bubble sort. (1)
June 2022 · Paper 3D (Decision 1) · Q6(d) 3 marks algorithms and graph theory
It is given that the maximum total number of comparisons required to sort the weights of the arcs of Kn into ascending order using bubble sort is λn(n – 1)(n + 1)(n – 2) where λ is a constant. (d) Determine the maximum total number of comparisons required to sort the weights of the arcs of K50 into ascending order using bubble sort. You must make your method and working clear. (3)
June 2022 · Paper 3D (Decision 1) · Q7(a) 5 marks linear programming
7. y y = 2x + 1 R x x + 2y = 12 7x + 2y = 46 x + y = 8 Figure 5 Figure 5 shows the constraints of a linear programming problem in x and y where R is the feasible region. The objective is to maximise P = x + ky, where k is a positive constant. The optimal vertex of R is to be found using the Simplex algorithm. (a) Set up an initial tableau for solving this linear programming problem using the Simplex algorithm. (5)
June 2022 · Paper 3D (Decision 1) · Q7(b) 1 mark linear programming
After two iterations of the Simplex algorithm a possible tableau T is b.v. x y s1 s2 s3 s4 Value -3 s1 -2 x -11 s3 y + k 5 k P - + 5k + 2 (b) State the value of each variable after the second iteration. (1)
June 2022 · Paper 3D (Decision 1) · Q7(c) 9 marks linear programming
It is given that T does not give an optimal solution to the linear programming problem. After a third iteration of the Simplex algorithm the resulting tableau does give an optimal solution to the problem. (c) Perform the third iteration of the Simplex algorithm and hence determine the range of possible values for P. You should state the row operations you use and make your method and working clear. (9)

Find an Edexcel Further Maths tutor

Want this paper marked and gone through with a Further Maths tutor? Message us.

Prefer email? Send an enquiry

If you are under 18, please include a parent's contact details. Enquiries go to enquiries@alevelfurthermathstutor.com and are deleted once handled.