June 2023: AS Paper 27: Decision Mathematics 1

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

Question by question

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

The questions

12(a)2(b)2(c)2(d)2(e)3(a)3(b)3(c)3(d)4(a)4(b)5(a)5(b)5(c)
June 2023 · AS Paper 2 (Decision 1) · Q1 4 marks algorithms and graph theory
1. 67 59 46 71 40 48 53 63 45 54 56 The list of eleven numbers shown above is to be sorted into descending order. Carry out a quick sort to produce the sorted list. You should show the result of each pass and identify the pivots clearly.
June 2023 · AS Paper 2 (Decision 1) · Q2(a) 1 mark critical path analysis
2. D(7) A(6) G(5) I(2) E(8) B(10) H(9) L(5) J(6) K(9) C(7) F(11) Figure 1 A project is modelled by the activity network shown in Figure 1. The activities are represented by the arcs. The number in brackets on each arc gives the time required, in hours, to complete the corresponding activity. The numbers in circles are the event numbers. Each activity requires one worker, and the project is to be completed in the shortest possible time. (a) Explain the significance of the dummy activity from event 3 to event 4 (1)
June 2023 · AS Paper 2 (Decision 1) · Q2(b) 3 marks critical path analysis
(b) Complete Diagram 1 in the answer book to show the early event times and the late event times. (3)
June 2023 · AS Paper 2 (Decision 1) · Q2(c) 1 mark critical path analysis
(c) State the critical activities. (1)
June 2023 · AS Paper 2 (Decision 1) · Q2(d) 1 mark critical path analysis
(d) Calculate a lower bound for the number of workers needed to complete the project in the minimum time. You must show your working. (1)
June 2023 · AS Paper 2 (Decision 1) · Q2(e) 4 marks critical path analysis
(e) Draw a Gantt chart for this project on Grid 1 in the answer book. (4)
June 2023 · AS Paper 2 (Decision 1) · Q3(a) 1 mark minimum spanning trees and shortest paths
3. C H G J B A E F Figure 2 Figure 2 represents a network of train tracks. The number on each edge represents the length, in kilometres, of the corresponding track. Dyfan wishes to travel from A to J via C. Dyfan wishes to minimise the distance they travel. Given that Dijkstra’s algorithm is to be applied only once to find Dyfan’s route, (a) explain why the algorithm should begin at C. (1)
June 2023 · AS Paper 2 (Decision 1) · Q3(b) 6 marks minimum spanning trees and shortest paths
(b) Use Dijkstra’s algorithm to find the shortest route from A to J via C. State this route and its length. (6)
June 2023 · AS Paper 2 (Decision 1) · Q3(c) 3 marks minimum spanning trees and shortest paths
(c) Use Prim’s algorithm, starting at C, to find a minimum spanning tree for the network. You must clearly state the order in which you select the edges of your tree. (3)
June 2023 · AS Paper 2 (Decision 1) · Q3(d) 1 mark minimum spanning trees and shortest paths
(d) State the total length, in km, of the minimum spanning tree. (1)
June 2023 · AS Paper 2 (Decision 1) · Q4(a) 2 marks linear programming
4. y x = 8 3y = 4x + 5 R 4x + 15y = 120 objective line x 3x + 8y = 32 Figure 3 Figure 3 shows the constraints of a linear programming problem in x and y. The unshaded area, including its boundaries, forms the feasible region, R. An objective line has been drawn and labelled on the graph. (a) State the inequalities that define the feasible region. (2)
June 2023 · AS Paper 2 (Decision 1) · Q4(b) 5 marks linear programming
The maximum value of the objective function is 160 The minimum value of the objective function is 883 (b) Determine the objective function, showing your working clearly. (5)
June 2023 · AS Paper 2 (Decision 1) · Q5(a) 1 mark algorithms and graph theory
5. B x + 4 2x + 1 5x – 8 2x – 2 C A x + 5 3x + 2 x + 7 E 5x – 6 F Figure 4 [The weight of the network is 20x + 3] Figure 4 shows a graph G that contains 8 arcs and 6 vertices. (a) State the minimum number of arcs that would need to be added to make G into an Eulerian graph. (1)
June 2023 · AS Paper 2 (Decision 1) · Q5(b) 1 mark algorithms and graph theory
(b) Explain whether or not the route A – C – F – E – C – D – B is an example of a path on G. (1)
June 2023 · AS Paper 2 (Decision 1) · Q5(c) 6 marks route inspection and travelling salesman
Figure 4 represents a network of 8 roads in a city. The expression on each arc gives the time, in minutes, to travel along the corresponding road. You are given that x > 1.6 A route is required that • starts and finishes at the same vertex • traverses each road at least once • minimises the total time taken The route inspection algorithm is applied to the network in Figure 4 and the time taken for the route is found to be at most 189 minutes. Given that the inspection route contains two roads that need to be traversed twice, (c) determine the range of possible values of x, making your reasoning clear. (6)

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.