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

The questions

1(a)1(b)2(a)2(b)2(c)2(d)3(a)3(b)3(c)4(a)4(b)4(c)5(a)5(b)5(c)5(d)5(e)6(a)6(b)6(c)6(d)7(a)7(b)
June 2025 · Paper 3D (Decision 1) · Q1(a) 3 marks algorithms and graph theory
1. 4.7 2.9 5.5 1.4 5.8 2.8 3.8 6.5 5.1 6.3 4.1 (a) Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 13 (3)
June 2025 · Paper 3D (Decision 1) · Q1(b) 2 marks algorithms and graph theory
(b) Use the first-fit decreasing bin packing algorithm to determine how the numbers listed above can be packed into bins of size 13 (2)
June 2025 · Paper 3D (Decision 1) · Q2(a) 4 marks algorithms and graph theory
2. 271 828 182 845 904 523 536 028 747 135 The list of ten numbers above is to be sorted into descending order. (a) Perform a quick sort on the list to obtain the sorted list. You should show the result of each pass and identify the pivots clearly. (4)
June 2025 · Paper 3D (Decision 1) · Q2(b) 2 marks algorithms and graph theory
A list of n numbers is to be sorted into descending order using bubble sort. (b) Determine, in the worst case, the total number of comparisons required to sort the list. Give your answer as a simplified expression in terms of n. (2)
June 2025 · Paper 3D (Decision 1) · Q2(c) 3 marks algorithms and graph theory
The following algorithm determines an approximation to the value of e Step 1 Start Step 2 Let a = 1 Step 3 Let b = 1 Step 4 Let c = 1 Step 5 Let d = a Step 6 Let c c ; b 1 1 Step 7 Let d d c Step 8 If b = 6 go to Step 11 Step 9 Let b = b + 1 Step 10 Go to Step 6 Step 11 Output d Step 12 Stop (c) Complete the table in the answer book to show the results obtained at each step of the algorithm. (3)
June 2025 · Paper 3D (Decision 1) · Q2(d) 1 mark algorithms and graph theory
(d) Calculate, to 3 significant figures, the percentage error in using the value found in (c) to approximate the value of e (1)
June 2025 · Paper 3D (Decision 1) · Q3(a) 2 marks minimum spanning trees and shortest paths
3. G F A E B C Figure 1 Direct roads between seven villages, A, B, C, D, E, F and G, are represented in Figure 1. The weight on each arc is the time, in minutes, taken to travel along the corresponding road. Three roads, AB, AD and GE, are one-way, as indicated by the arrow on the corresponding arc. Floyd’s algorithm is to be used to find the complete network of shortest times between the seven villages. (a) Set up an initial time matrix for this network. (2)
June 2025 · Paper 3D (Decision 1) · Q3(b) 5 marks minimum spanning trees and shortest paths
The time matrix after three iterations of Floyd’s algorithm is shown below. A B C E F G A – B – ∞ ∞ C – ∞ ∞ – ∞ E – F – ∞ G – (b) Perform the next two iterations of Floyd’s algorithm that follow from the table above. You should show only the time matrix after each iteration. (5)
June 2025 · Paper 3D (Decision 1) · Q3(c) 3 marks route inspection and travelling salesman
The final time matrix after completion of Floyd’s algorithm is shown below. A B C E F G A – B – C – – E – F – G – Albert must visit each village. He will start and finish at B and wishes to minimise the total time taken to visit each village. (c) (i) Use the nearest neighbour algorithm, starting at B, to find a Hamiltonian cycle in the complete network of shortest times shown above. (ii) Find the total travel time for this cycle. (iii) Given that he travels the Hamiltonian cycle found in (c)(i), interpret this cycle in terms of the actual villages visited by Albert. (3)
June 2025 · Paper 3D (Decision 1) · Q4(a) 6 marks minimum spanning trees and shortest paths
4. B E J F C A K G H Figure 2 [The total weight of the network is 268] Figure 2 represents a network of corridors between 10 offices, A, B, C, D, E, F, G, H, J and K, in a building. The number on each edge represents the length, in metres, of the corresponding corridor. On Monday morning, Turvi needs to walk from J to K via A. She wishes to minimise the distance she travels along the corridors. (a) (i) Use Dijkstra’s algorithm, starting at A, to find the shortest route from J to K via A. (ii) State the length of this route. (6)
June 2025 · Paper 3D (Decision 1) · Q4(b) 5 marks route inspection and travelling salesman
On Monday afternoon, Turvi needs a route that traverses each corridor at least once. She plans to start at J and finish at A and wants to minimise the distance travelled. (b) (i) By considering the pairings of all relevant nodes, find the corridors that would need to be traversed twice. You must make your method and working clear. (ii) State the total length of this route. (5)
June 2025 · Paper 3D (Decision 1) · Q4(c) 2 marks route inspection and travelling salesman
Turvi discovers that she cannot walk along corridors AB, CD and JK because they are being decorated. Turvi walks from J to A travelling along all the other corridors at least once. She does this in the minimum distance possible. (c) Determine the difference between the length of the route Turvi travels and the length of the route found in (b). You must make the values used in your calculation clear. (2)
June 2025 · Paper 3D (Decision 1) · Q5(a) 1 mark linear programming
5. Consider the following linear programming problem in x, y and z. Maximise P x y z subject to 2 x + y + z x - y - z z x y x y z (a) Explain why the Simplex algorithm cannot be used to solve this linear programming problem in its current form. (1)
June 2025 · Paper 3D (Decision 1) · Q5(b) 3 marks linear programming
(b) Use the substitutions x X , y Y , z O 3 Z and P Q 1 10 to reformulate the linear programming problem into a form in which the Simplex algorithm can be used to solve the problem. You should write the constraints as simplified inequalities with integer coefficients. (3)
June 2025 · Paper 3D (Decision 1) · Q5(c) 1 mark linear programming
After a second iteration of the Simplex algorithm, a possible tableau T is s1 s2 s3 b.v. X Y Z Value -3 -1 X s2 -1 Y -5 Q (c) Write down the profit equation given by T. (1)
June 2025 · Paper 3D (Decision 1) · Q5(d) 1 mark linear programming
(d) Using your answer to (c), explain why T is not optimal. (1)
June 2025 · Paper 3D (Decision 1) · Q5(e) 6 marks linear programming
(e) (i) Perform the third iteration of the Simplex algorithm. You should state the row operations you use. (ii) Hence determine the maximum value of P, and the corresponding values of x, y and z. (6)
June 2025 · Paper 3D (Decision 1) · Q6(a) 2 marks critical path analysis
6. D(7) H(6) A(2) G(5) J(2) I(10) B(4) K(6) E(4) C(3) L(10) F(5) M(7) Figure 3 A project is modelled by the activity network shown in Figure 3. The activities are represented by the arcs. The number in brackets on each arc gives the time, in hours, to complete the corresponding activity. The project is to be completed in the shortest possible time. (a) Complete Table 1 in the answer book to show the immediately preceding activities for each activity. (2)
June 2025 · Paper 3D (Decision 1) · Q6(b) 4 marks critical path analysis
(b) Complete Diagram 1 in the answer book to show the early event times and the late event times. (4)
June 2025 · Paper 3D (Decision 1) · Q6(c) 4 marks critical path analysis
(c) Draw a Gantt chart for this project on Grid 1 in the answer book. (4)
June 2025 · Paper 3D (Decision 1) · Q6(d) 3 marks critical path analysis
Number of workers Time (hours) Figure 4 The resource histogram in Figure 4 shows the number of workers required when each activity starts at its earliest possible time. When an activity is started it must be completed without interruption. Each activity requires at least one worker. (d) By considering which activities are happening each hour, and by working backwards from the minimum project completion time, complete Table 2 in the answer book to show the number of workers needed for each activity. (3)
June 2025 · Paper 3D (Decision 1) · Q7(a) 7 marks linear programming
7. y 3x + 4y = 20 R x x = 1 3x + y = 8 2x + 3y = 6 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 value of P is to be found using the big-M method. (a) Set up an initial tableau for solving this linear programming problem using the big-M method. You should use exactly 2 slack variables, 2 surplus variables and 2 artificial variables. (7)
June 2025 · Paper 3D (Decision 1) · Q7(b) 5 marks linear programming
After a third iteration of the big-M method, a possible tableau is s1 s2 s3 s4 a1 a2 x y b.v. Value s1 - - x - y - - s2 -1 - P k k M M k k 7 - 7 - - + 7 + (b) Given that the third iteration gives the optimal value for P, determine this value. (5)

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.