Pearson Edexcel Level 3 GCE
Friday 21 June 2024
Afternoon (Time: 1 hour 30 minutes)
Paper
reference 9FM0/3D
Further Mathematics
� �
Advanced
PAPER 3D: Decision Mathematics 1
You must have:
Mathematical Formulae and Statistical Tables (Green), calculator,
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
, BLANK PAGE
2
,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)
, 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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller road2distinction. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $7.99. You're not tied to anything after your purchase.
