2024 PEARSON EDEXCEL GCE A LEVEL FURTHER MATHEMATICS 9FMO/3D PAPER 3D MERGED QUESTION
PAPER AND MARKING SCHEME
■ ■
Further Mathematics
Advanced
PAPER 3D: Decision Mathematics 1
Decision Mathematics Answer Book (enclosed)
Candidates may use any calculator permitted by Pearson regulations.
Calculators must not have the facility for symbolic algebra manipulation,
differentiation and integration, or have retrievable mathematical formulae
stored in them.
Instructions
•• Use black ink or ball-point pen.
• Write
If pencil is used for diagrams/sketches/graphs it must be dark (HB or B).
your answers for this paper in the Decision Mathematics answer book
• Fill
provided.
in the boxes at the top of the answer book with your name, centre number
and candidate number.
•• DoAnswer
not return the question paper with the answer book.
all questions and ensure that your answers to parts of questions are
• Answer
clearly labelled.
the questions in the answer book provided
– there may be more space than you need.
• You should show sufficient working to make your methods clear. Answers without
• Inexact
working may not gain full credit.
answers should be given to three significant figures unless
otherwise stated.
Information
•• AThere
booklet ‘Mathematical Formulae and Statistical Tables’ is provided.
• The are 7 questions in this question paper. The total mark for this paper is 75.
marks for each question are shown in brackets
– use this as a guide as to how much time to spend on each question.
Advice
• Read each question carefully before you start to answer it.
•• Try to answer every question.
Check your answers if you have time at the end.
Turn over
P75688A
©2024 Pearson Education Ltd.
F:1/1/1/1/1/1/
, BLANK PAGE
2 P75688A
■■■■
,1.
17 8 16 12 24 19 23 11 20 13 4
The eleven numbers listed above 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 eleven
numbers, the bins are packed as shown below.
Bin 1: 17 8 12
Bin 2: 16 24
Bin 3: 19 11 4
Bin 4: 23 13
Bin 5: 20
(a) Explain why this packing means that the value of n must be 40
(1)
The original list of eleven numbers is to be sorted into descending order.
(b) Use a quick sort to obtain the fully sorted list. You must make your pivots clear.
(4)
(c) Apply the first-fit decreasing bin packing algorithm to the fully sorted list to pack
the numbers into bins of size 40
(2)
(Total for Question 1 is 7 marks)
P75688A 3
■■■■ Turn over
, 2. The table below represents a network of shortest distances, in miles, to travel between
nine castles, A, B, C, D, E, F, G, H and J.
A B C D E F G H J
A – 50 59 26 50 40 87 63 59
B 50 – 28 61 79 63 45 64 48
C 59 28 – 33 57 35 70 36 45
D 26 61 33 – 24 64 71 37 33
E 50 79 57 24 – 40 64 30 31
F 40 63 35 64 40 – 47 70 71
G 87 45 70 71 64 47 – 34 67
H 63 64 36 37 30 70 34 – 33
J 59 48 45 33 31 71 67 33 –
(a) Use Prim’s algorithm, starting at D, to find the minimum spanning tree for this
network. You must clearly state the order in which you select the arcs of your tree.
(3)
(b) State the weight of the minimum spanning tree found in part (a).
(1)
(c) Draw the minimum spanning tree using the vertices given in Diagram 1 in the
answer book.
(1)
A historian needs to visit all of the castles, starting and finishing at the same castle, and
wishes to minimise the total distance travelled.
(d) Use your answer to part (b) to calculate an initial upper bound for the length of the
historian’s route.
(1)
(e) (i) Use the nearest neighbour algorithm, starting at D, to find an upper bound for
the length of the historian’s route.
(ii) Write down the route which gives this upper bound.
(3)
Using the nearest neighbour algorithm, starting at F, an upper bound of length 352 miles
was found.
(f) State the best upper bound that can be obtained by using this information and your
answers from parts (d) and (e). Give the reason for your answer.
(1)
4 P75688A
■■■■
PAPER AND MARKING SCHEME
■ ■
Further Mathematics
Advanced
PAPER 3D: Decision Mathematics 1
Decision Mathematics Answer Book (enclosed)
Candidates may use any calculator permitted by Pearson regulations.
Calculators must not have the facility for symbolic algebra manipulation,
differentiation and integration, or have retrievable mathematical formulae
stored in them.
Instructions
•• Use black ink or ball-point pen.
• Write
If pencil is used for diagrams/sketches/graphs it must be dark (HB or B).
your answers for this paper in the Decision Mathematics answer book
• Fill
provided.
in the boxes at the top of the answer book with your name, centre number
and candidate number.
•• DoAnswer
not return the question paper with the answer book.
all questions and ensure that your answers to parts of questions are
• Answer
clearly labelled.
the questions in the answer book provided
– there may be more space than you need.
• You should show sufficient working to make your methods clear. Answers without
• Inexact
working may not gain full credit.
answers should be given to three significant figures unless
otherwise stated.
Information
•• AThere
booklet ‘Mathematical Formulae and Statistical Tables’ is provided.
• The are 7 questions in this question paper. The total mark for this paper is 75.
marks for each question are shown in brackets
– use this as a guide as to how much time to spend on each question.
Advice
• Read each question carefully before you start to answer it.
•• Try to answer every question.
Check your answers if you have time at the end.
Turn over
P75688A
©2024 Pearson Education Ltd.
F:1/1/1/1/1/1/
, BLANK PAGE
2 P75688A
■■■■
,1.
17 8 16 12 24 19 23 11 20 13 4
The eleven numbers listed above 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 eleven
numbers, the bins are packed as shown below.
Bin 1: 17 8 12
Bin 2: 16 24
Bin 3: 19 11 4
Bin 4: 23 13
Bin 5: 20
(a) Explain why this packing means that the value of n must be 40
(1)
The original list of eleven numbers is to be sorted into descending order.
(b) Use a quick sort to obtain the fully sorted list. You must make your pivots clear.
(4)
(c) Apply the first-fit decreasing bin packing algorithm to the fully sorted list to pack
the numbers into bins of size 40
(2)
(Total for Question 1 is 7 marks)
P75688A 3
■■■■ Turn over
, 2. The table below represents a network of shortest distances, in miles, to travel between
nine castles, A, B, C, D, E, F, G, H and J.
A B C D E F G H J
A – 50 59 26 50 40 87 63 59
B 50 – 28 61 79 63 45 64 48
C 59 28 – 33 57 35 70 36 45
D 26 61 33 – 24 64 71 37 33
E 50 79 57 24 – 40 64 30 31
F 40 63 35 64 40 – 47 70 71
G 87 45 70 71 64 47 – 34 67
H 63 64 36 37 30 70 34 – 33
J 59 48 45 33 31 71 67 33 –
(a) Use Prim’s algorithm, starting at D, to find the minimum spanning tree for this
network. You must clearly state the order in which you select the arcs of your tree.
(3)
(b) State the weight of the minimum spanning tree found in part (a).
(1)
(c) Draw the minimum spanning tree using the vertices given in Diagram 1 in the
answer book.
(1)
A historian needs to visit all of the castles, starting and finishing at the same castle, and
wishes to minimise the total distance travelled.
(d) Use your answer to part (b) to calculate an initial upper bound for the length of the
historian’s route.
(1)
(e) (i) Use the nearest neighbour algorithm, starting at D, to find an upper bound for
the length of the historian’s route.
(ii) Write down the route which gives this upper bound.
(3)
Using the nearest neighbour algorithm, starting at F, an upper bound of length 352 miles
was found.
(f) State the best upper bound that can be obtained by using this information and your
answers from parts (d) and (e). Give the reason for your answer.
(1)
4 P75688A
■■■■
