10 P72094A 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 × 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) 11 Turn over P72094A A B C D E 21 15 19 17 24 14 13 20 23 28 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) (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) 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) (Total for Question 6 is 12 marks) 12 P72094A 7. y y = 2x + 1 x + y = 8 7x + 2y = 46 x + 2y = 12 x R O 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) 13 P72094A After two iterations of the Simplex algorithm a possible tableau T is b.v. x y s1 s2 s3 s4 Value s1 0 0 1 −3 5 0 1 5 1 x 1 0 0 1 5 0 −2 5 2 s3 0 0 0 −11 5 1 12 5 22 y 0 1 0 2 5 0 1 5 5 P 0 0 0 1 5 2 5 + k 0 − + 2 5 1 5 k 5k + 2 (b) State the value of each variable after the second iteration. (1) 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) (Total for Question 7 is 15 marks) TOTAL FOR PAPER IS 75 MARKS 14 P72094A BLANK PAGE 15 P72094A BLANK PAGE 16 P72094A BLANK PAGE Centre Number Candidate Number Turn over Total Marks Candidate surname Other names Please check the examination details below before entering your candidate information Paper reference Answer Book Do not return the question paper with the answer book. Further Mathematics Advanced PAPER 3D: Decision Mathematics 1 Time 1 hour 30 minutes 9FM0/3D Pearson Edexcel Level 3 GCE P72094A ©2022 Pearson Education Ltd. 1/1/1/1/ 2 1. 4.3 6.1 5.1 4.7 2.5 5.9 3.4 1.7 2.1 0.4 1.3 _____________________________________________________________________________________ _____________________________________________________________________________________ _____________________________________________________________________________________ _____________________________________________________________________________________ _____________________________________________________________________________________ _____________________________________________________________________________________ _____________________________________________________________________________________ _____________________________________________________________________________________ _____________________________________________________________________________________ _____________________________________________________________________________________ _____________________________________________________________________________________ _____________________________________________________________________________________ _____________________________________________________________________________________ _____________________________________________________________________________________ _____________________________________________________________________________________ _____________________________________________________________________________________ _____________________________________________________________________________________ _____________________________________________________________________________________ _____________________________________________________________________________________ _____________________________________________________________________________________ _____________________________________________________________________________________ _____________________________________________________________________________________ _____________________________________________________________________________________ _____________________________________________________________________________________ _____________________________________________________________________________________ _____________________________________________________________________________________ _____________________________________________________________________________________ _____________________________________________________________________________________ _____________________________________________________________________________________ _____________________________________________________________________________________ _____________________________________________________________________________________ _____________________________________________________________________________________ _____________________________________________________________________________________ (Total for Question 1 is 5 marks) Turn over 3 2. A D B C E F G H J K 10 10 10 31 25 6 23 25 8 14 14 18 9 3 4 16 23 33 17 Key: Vertex Order of labelling Final value Working value Shortest path from A to K: _ _________________________________________________________________________________________________ Length of shortest path from A to K: �����������������������������������������������������������������������������������������