Nov 2021: A level Paper 3D: Decision Mathematics 1

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

The questions

1(a)1(b)2(a)2(b)2(c)3(a)3(b)3(c)3(d)4(a)4(b)4(c)4(d)5(a)5(b)5(c)6(a)6(b)6(c)7(a)7(b)7(c)8(a)8(b)8(c)8(d)
Nov 2021 · Paper 3D (Decision 1) · Q1(a) 1 mark algorithms and graph theory
1. A U B V C W X E Y Figure 1 A Hamiltonian cycle for the graph in Figure 1 begins C, V, E, X, A, W, …. (a) Complete the Hamiltonian cycle. (1)
Nov 2021 · Paper 3D (Decision 1) · Q1(b) 3 marks algorithms and graph theory
(b) Hence use the planarity algorithm to determine whether the graph shown in Figure 1 is planar. You must make your working clear and justify your answer. (3)
Nov 2021 · Paper 3D (Decision 1) · Q2(a) 4 marks critical path analysis
2. D(2) G(6) J(7) H(7) A(4) E(4) B(6) I(2) K(6) F(5) C(10) L(7) M(5) Figure 2 A project is modelled by the activity network shown in Figure 2. The activities are represented by the arcs. The number in brackets on each arc gives the time, in hours, to complete the corresponding activity. (a) Complete Diagram 1 in the answer book to show the early event times and the late event times. (4)
Nov 2021 · Paper 3D (Decision 1) · Q2(b) 2 marks critical path analysis
Each activity requires one worker and the project must be completed in the shortest possible time using as few workers as possible. (b) Calculate a lower bound for the number of workers needed to complete the project in the shortest possible time. You must show your working. (2)
Nov 2021 · Paper 3D (Decision 1) · Q2(c) 3 marks critical path analysis
(c) Schedule the activities using Grid 1 in the answer book. (3)
Nov 2021 · Paper 3D (Decision 1) · Q3(a) 3 marks minimum spanning trees and shortest paths
3. A B C E F G H A – B – C – – E – F – G – H – Table 1 Table 1 shows the shortest distances, in miles, between eight towns, A, B, C, D, E, F, G and H. (a) Use Prim’s algorithm, starting at A, to find the minimum spanning tree for this table of distances. You must clearly state the order in which you select the edges of your tree. (3)
Nov 2021 · Paper 3D (Decision 1) · Q3(b) 1 mark minimum spanning trees and shortest paths
(b) State the weight of the minimum spanning tree. (1)
Nov 2021 · Paper 3D (Decision 1) · Q3(c) 2 marks route inspection and travelling salesman
A B C E F G H J Table 2 Table 2 shows the distances, in miles, between town J and towns A, B, C, D, E, F, G and H. Pranav needs to visit all of the towns, starting and finishing at J, and wishes to minimise the total distance he travels. (c) Starting at J, use the nearest neighbour algorithm to obtain an upper bound for the length of Pranav’s route. You must state your route and its length. (2)
Nov 2021 · Paper 3D (Decision 1) · Q3(d) 2 marks route inspection and travelling salesman
(d) Starting by deleting J, and all of its edges, find a lower bound for the length of Pranav’s route. (2)
Nov 2021 · Paper 3D (Decision 1) · Q4(a) 1 mark minimum spanning trees and shortest paths
4. A B C F E Figure 3 [The total weight of the network is 1648] Direct roads between six cities, A, B, C, D, E and F, are represented in Figure 3. The weight on each arc is the time, in minutes, required to travel along the corresponding road. Floyd’s algorithm is to be used to find the complete network of shortest times between the six cities. An initial route matrix is given in the answer book. (a) Set up the initial time matrix. (1)
Nov 2021 · Paper 3D (Decision 1) · Q4(b) 2 marks minimum spanning trees and shortest paths
(b) Perform the first iteration of Floyd’s algorithm. You should show the time and route matrices after this iteration. (2)
Nov 2021 · Paper 3D (Decision 1) · Q4(c) 4 marks route inspection and travelling salesman
The final time matrix after completion of Floyd’s algorithm is shown below. A B C E F A – B – C – – E – F – A route is needed that minimises the total time taken to traverse each road at least once. The route must start at B and finish at E. (c) Use an appropriate algorithm to find the roads that will need to be traversed twice. You should make your method and working clear. (4)
Nov 2021 · Paper 3D (Decision 1) · Q4(d) 1 mark route inspection and travelling salesman
(d) Write down the length of the route. (1)
Nov 2021 · Paper 3D (Decision 1) · Q5(a) 4 marks algorithms and graph theory
5. 30 12 5 2 23 18 36 10 15 24 (a) The list of ten numbers above is to be sorted into descending order. Use a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly. (4)
Nov 2021 · Paper 3D (Decision 1) · Q5(b) 3 marks algorithms and graph theory
The ten numbers are to be packed into bins of size n, where n is a positive integer. When the first-fit bin packing algorithm is applied to the original list of ten numbers, the following allocation is obtained. Bin 1: 30 12 2 Bin 2: 5 23 10 Bin 3: 18 15 Bin 4: 36 Bin 5: 24 (b) Explain why the value of the integer n must be either 44 or 45 (3)
Nov 2021 · Paper 3D (Decision 1) · Q5(c) 3 marks algorithms and graph theory
(c) Use the first-fit decreasing bin packing algorithm to determine how the numbers can be packed into bins of size 45 (3)
Nov 2021 · Paper 3D (Decision 1) · Q6(a) 6 marks minimum spanning trees and shortest paths
6. B E F A G C H Figure 4 In Figure 4 the weights on the arcs represent distances. (a) (i) Use Dijkstra’s algorithm to find the shortest path from A to H. (ii) State the length of the shortest path from A to H. (6)
Nov 2021 · Paper 3D (Decision 1) · Q6(b) 3 marks algorithms and graph theory
One application of Dijkstra’s algorithm has order n2 , where n is the number of nodes in the network. A computer produces a table of shortest distances between any two different nodes by repeatedly applying Dijkstra’s algorithm from each node of the network. It takes the computer 0.082 seconds to produce a table of shortest distances for a network of 10 nodes. (b) Calculate approximately how long it will take, in seconds, for the computer to produce a table of shortest distances for a network with 200 nodes. You must give a reason for your answer. (3)
Nov 2021 · Paper 3D (Decision 1) · Q6(c) 1 mark algorithms and graph theory
(c) Explain why your answer to part (b) can only be an approximation. (1)
Nov 2021 · Paper 3D (Decision 1) · Q7(a) 2 marks critical path analysis
7. A F B E G C H Figure 5 Figure 5 shows a partially completed activity network for a project that consists of 14 activities. (a) Complete the precedence table in the answer book for the 8 activities in Figure 5. (2)
Nov 2021 · Paper 3D (Decision 1) · Q7(b) 4 marks critical path analysis
The precedence table for the remaining 6 activities is given below. Activity Immediately preceding activities I D, E, G, H J D, E, G, H K E, G, H L I, J, K M J, K N J, K (b) Complete the activity network in the answer book for the project. Your completed activity network must contain only the minimum number of dummies. (4)
Nov 2021 · Paper 3D (Decision 1) · Q7(c) 2 marks critical path analysis
Given that all 14 activities have the same duration, (c) explain why activity D cannot be critical. (2)
Nov 2021 · Paper 3D (Decision 1) · Q8(a) 5 marks linear programming
8. Susie is preparing for a triathlon event that is taking place next month. A triathlon involves three activities: swimming, cycling and running. Susie decides that in her training next week she should • maximise the total time spent cycling and running • train for at most 39 hours • spend at least 40% of her time swimming • spend a total of at least 28 hours of her time swimming and running Susie needs to determine how long she should spend next week training for each activity. Let • x represent the number of hours swimming • y represent the number of hours cycling • z represent the number of hours running (a) Formulate the information above as a linear programming problem. State the objective and list the constraints as simplified inequalities with integer coefficients. (5)
Nov 2021 · Paper 3D (Decision 1) · Q8(b) 6 marks linear programming
Susie decides to solve this linear programming problem by using the two-stage Simplex method. (b) Set up an initial tableau for solving this problem using the two-stage Simplex method. As part of your solution you must show how • the constraints have been made into equations using slack variables, exactly one surplus variable and exactly one artificial variable • the rows for the two objective functions are formed (6)
Nov 2021 · Paper 3D (Decision 1) · Q8(c) 2 marks linear programming
The following tableau T is obtained after one iteration of the second stage of the two‑stage Simplex method. b.v. x y z s1 s2 s3 Value y s2 -2 -5 x -1 P -1 (c) Obtain a suitable pivot for a second iteration. You must give reasons for your answer. (2)
Nov 2021 · Paper 3D (Decision 1) · Q8(d) 5 marks linear programming
(d) Starting from tableau T, solve the linear programming problem by performing one further iteration of the second stage of the two-stage Simplex method. You should make your method clear by stating the row operations you use. (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.