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

The questions

1(a)1(b)1(c)2(a)2(b)2(c)2(d)3(a)3(b)3(c)3(d)4(a)4(b)4(c)4(d)5(a)5(b)6(a)6(b)6(c)6(d)6(e)7(a)7(b)7(c)7(d)
June 2019 · Paper 3D (Decision 1) · Q1(a) 2 marks algorithms and graph theory
1. 2.1 1.7 3.0 1.9 3.2 1.2 3.3 1.4 1.5 0.2 (a) Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 5 (2)
June 2019 · Paper 3D (Decision 1) · Q1(b) 4 marks algorithms and graph theory
The list of numbers is now to be sorted into descending order. (b) Perform a quick sort on the original list to obtain the sorted list. You should show the result of each pass and identify your pivots clearly. (4)
June 2019 · Paper 3D (Decision 1) · Q1(c) 2 marks algorithms and graph theory
For a list of n numbers, the quick sort algorithm has, on average, order n log n. Given that it takes 2.32 seconds to run the algorithm when n = 450 (c) calculate approximately how long it will take, to the nearest tenth of a second, to run the algorithm when n = 11 250. You should make your method and working clear. (2)
June 2019 · Paper 3D (Decision 1) · Q2(a) 6 marks minimum spanning trees and shortest paths
2. B E C A J G F H Figure 1 [The total weight of the network is 370] Figure 1 represents a network of corridors in a building. The number on each arc represents the length, in metres, of the corresponding corridor. (a) Use Dijkstra’s algorithm to find the shortest path from A to D, stating the path and its length. (6)
June 2019 · Paper 3D (Decision 1) · Q2(b) 4 marks route inspection and travelling salesman
On a particular day, Naasir needs to check the paintwork along each corridor. Naasir must find a route of minimum length. It must traverse each corridor at least once, starting at B and finishing at G. (b) Use an appropriate algorithm to find the arcs that will need to be traversed twice. You must make your method and working clear. (4)
June 2019 · Paper 3D (Decision 1) · Q2(c) 1 mark route inspection and travelling salesman
(c) Find the length of Naasir’s route. (1)
June 2019 · Paper 3D (Decision 1) · Q2(d) 3 marks route inspection and travelling salesman
On a different day, all the corridors that start or finish at B are closed for redecorating. Naasir needs to check all the remaining corridors and may now start at any vertex and finish at any vertex. A route is required that excludes all those corridors that start or finish at B. (d) (i) Determine the possible starting and finishing points so that the length of Naasir’s route is minimised. You must give reasons for your answer. (ii) Find the length of Naasir’s new route. (3)
June 2019 · Paper 3D (Decision 1) · Q3(a) 2 marks minimum spanning trees and shortest paths
3. B C A E Figure 2 The network in Figure 2 shows the direct roads linking five villages, A, B, C, D and E. The number on each arc represents the length, in miles, of the corresponding road. The roads from A to E and from C to B are one-way, as indicated by the arrows. (a) Complete the initial distance and route tables for the network provided in the answer book. (2)
June 2019 · Paper 3D (Decision 1) · Q3(b) 5 marks minimum spanning trees and shortest paths
(b) Perform the first three iterations of Floyd’s algorithm. You should show the distance table and the route table after each of the three iterations. (5)
June 2019 · Paper 3D (Decision 1) · Q3(c) 3 marks minimum spanning trees and shortest paths
After five iterations of Floyd’s algorithm the final distance table and partially completed final route table are shown below. Distance table Route table A B C E A B C E A – A A B – B A B C – C A B C – C C C E – E E (c) (i) Explain how the partially completed final route table can be used to find the shortest route from E to A. (ii) State this route. (3)
June 2019 · Paper 3D (Decision 1) · Q3(d) 4 marks route inspection and travelling salesman
Mabintou decides to use the distance table to try to find the shortest cycle that passes through each vertex. Starting at D, she applies the nearest neighbour algorithm to the final distance table. (d) (i) State the cycle obtained using the nearest neighbour algorithm. (ii) State the length of this cycle. (iii) Interpret the cycle in terms of the actual villages visited. (iv) Prove that Mabintou’s cycle is not optimal. (4)
June 2019 · Paper 3D (Decision 1) · Q4(a) 2 marks critical path analysis
4. D(11) I(6) E(5) A(8) J(4) K(6) B(6) F(8) L(7) Key: G(10) Early M(6) C(7) event time Late event H(x) time Figure 3 The network in Figure 3 shows the activities that need to be undertaken to complete 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 and late event times are to be shown at each vertex and one late event time has been completed for you. The total float of activity H is 7 days. (a) Explain, with detailed reasoning, why x = 11 (2)
June 2019 · Paper 3D (Decision 1) · Q4(b) 3 marks critical path analysis
(b) Determine the missing early event times and late event times, and hence complete Diagram 1 in your answer book. (3)
June 2019 · Paper 3D (Decision 1) · Q4(c) 1 mark 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. (c) Calculate a lower bound for the number of workers needed to complete the project in the shortest possible time. (1)
June 2019 · Paper 3D (Decision 1) · Q4(d) 3 marks critical path analysis
(d) Schedule the activities using Grid 1 in the answer book. (3)
June 2019 · Paper 3D (Decision 1) · Q5(a) 5 marks critical path analysis
5. Activity Immediately preceding activities A – B – C – A E C F B, C, D G A H B, C, D I B, C, D, G J B, C, D, G K E, H (a) Draw the activity network described in the precedence table above, using activity on arc. Your activity network must contain only the minimum number of dummies. (5)
June 2019 · Paper 3D (Decision 1) · Q5(b) 1 mark critical path analysis
Given that all the activities shown in the precedence table have the same duration, (b) state the critical path for the network. (1)
June 2019 · Paper 3D (Decision 1) · Q6(a) 1 mark linear programming
6. A linear programming problem in x, y and z is described as follows. Maximise P = 2x + 2y í z 3x + y + 2z - 30 subject to x í y + z . 8 4y + 2z . 15 x, y, z . 0 (a) Explain why the Simplex algorithm cannot be used to solve this linear programming problem. (1)
June 2019 · Paper 3D (Decision 1) · Q6(b) 7 marks linear programming
(b) Set up the initial tableau for solving this linear programming problem using the big-M method. (7)
June 2019 · Paper 3D (Decision 1) · Q6(c) 1 mark linear programming
After a first iteration of the big-M method, the tableau is b.v. x y z s1 s2 s3 a1 a2 Value s1 1.5 0.25 í0.25 26.25 a1 1.5 í1 í0.25 0.25 11.75 y 0.5 í0.25 0.25 3.75 P í(2 + M) 2 í 1.5M M í0.5 + 0.25M 0.5 + 0.75M 7.5 í 11.75M (c) State the value of each variable after the first iteration. (1)
June 2019 · Paper 3D (Decision 1) · Q6(d) 1 mark linear programming
(d) Explain why the solution given by the first iteration is not feasible. (1)
June 2019 · Paper 3D (Decision 1) · Q6(e) 2 marks linear programming
Taking the most negative entry in the profit row to indicate the pivot column, (e) obtain the most efficient pivot for a second iteration. You must give reasons for your answer. (2)
June 2019 · Paper 3D (Decision 1) · Q7(a) 2 marks linear programming
7. A shop sells two types of watch, analogue watches and digital watches. The shop manager knows that, each month, she should order at least 60 watches in total. In addition, at most 80% of the watches she orders must be digital. Let x be the number of analogue watches ordered and let y be the number of digital watches ordered. (a) Write down inequalities, in terms of x and y, to model these constraints. (2)
June 2019 · Paper 3D (Decision 1) · Q7(b) 4 marks linear programming
Two further constraints are y + 3x . 140 4y + x . 80 (b) Represent all these constraints on Diagram 1 in the answer book. Hence determine, and label, the feasible region, R. (4)
June 2019 · Paper 3D (Decision 1) · Q7(c) 3 marks linear programming
The cost to the shop of ordering an analogue watch is five times the cost of ordering a digital watch. The shop manager wishes to minimise the total cost. (c) Determine the number of each type of watch the shop manager should order. You must make your method clear. (3)
June 2019 · Paper 3D (Decision 1) · Q7(d) 3 marks linear programming
Given that the minimum total cost of ordering the watches is £4455 (d) determine the cost of ordering one analogue watch and the cost of ordering one digital watch. You must make your method clear. (3)

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.