� �
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
• Write your answers for this paper in the Decision Mathematics answer book
Fill in the boxes at the top of the answer book with your name,
centre number and candidate number.
• Answer all questions and ensure that your answers to parts of questions are clearly
Answer 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
working may not gain full credit.
Inexact answers should be given to three significant figures unless otherwise stated.
• There are 7 questions in this question paper. The total mark for this paper is 75.
– 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.
• Check your answers if you have time at the end.
Turn over
,1.
4.7 2.9 5.5 1.4 5.8 2.8 3.8 6.5 5.1 6.3 4.1
(a) Use the first-fit bin packing algorithm to determine how the numbers listed above
can be packed into bins of size 13
(3)
(b) Use the first-fit decreasing bin packing algorithm to determine how the numbers
listed above can be packed into bins of size 13
(2)
(Total for Question 1 is 5 marks)
,2.
271 828 182 845 904 523 536 028 747 135
The list of ten numbers above is to be sorted into descending order.
(a) Perform a quick sort on the list to obtain the sorted list. You should show the result
of each pass and identify the pivots clearly.
(4)
A list of n numbers is to be sorted into descending order using bubble sort.
(b) Determine, in the worst case, the total number of comparisons required to sort the
list. Give your answer as a simplified expression in terms of n.
(2)
The following algorithm determines an approximation to the value of e
Step 1 Start
Step 2 Let a = 1
Step 3 Let b = 1
Step 4 Let c = 1
Step 5 Let d = a
Step 6 Let c c b
Step 7 Let d d 1c
Step 8 If b = 6 go to Step 11
Step 9 Let b = b + 1
Step 10 Go to Step 6
Step 11 Output d
Step 12 Stop
(c) Complete the table in the answer book to show the results obtained at each step of
the algorithm.
(3)
(d) Calculate, to 3 significant figures, the percentage error in using the value found in
(c) to approximate the value of e
(1)
(Total for Question 2 is 10 marks)
, 3.
G 12 F
11
47 24 14
A
35 E
9 35 31
25 11
8
B
40 D
17
C
Figure 1
Direct roads between seven villages, A, B, C, D, E, F and G, are represented in
Figure 1. The weight on each arc is the time, in minutes, taken to travel along the
corresponding road. Three roads, AB, AD and GE, are one-way, as indicated by the
arrow on the corresponding arc.
Floyd‟s algorithm is to be used to find the complete network of shortest times between
the seven villages.
(a) Set up an initial time matrix for this network.
(2)
The time matrix after three iterations of Floyd‟s algorithm is shown below.
A B C D E F G
A – 9 49 17 35 44 11
B – 40 8 35 87
C 40 – 17 75 47
D 8 17 – 11 31 64
E 35 44 84 11 – 14 46
F 35 75 31 14 – 12
G 11 20 47 28 24 12 –
(b) Perform the next two iterations of Floyd‟s algorithm that follow from the
table above.
You should show only the time matrix after each iteration.
(5)
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
• Write your answers for this paper in the Decision Mathematics answer book
Fill in the boxes at the top of the answer book with your name,
centre number and candidate number.
• Answer all questions and ensure that your answers to parts of questions are clearly
Answer 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
working may not gain full credit.
Inexact answers should be given to three significant figures unless otherwise stated.
• There are 7 questions in this question paper. The total mark for this paper is 75.
– 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.
• Check your answers if you have time at the end.
Turn over
,1.
4.7 2.9 5.5 1.4 5.8 2.8 3.8 6.5 5.1 6.3 4.1
(a) Use the first-fit bin packing algorithm to determine how the numbers listed above
can be packed into bins of size 13
(3)
(b) Use the first-fit decreasing bin packing algorithm to determine how the numbers
listed above can be packed into bins of size 13
(2)
(Total for Question 1 is 5 marks)
,2.
271 828 182 845 904 523 536 028 747 135
The list of ten numbers above is to be sorted into descending order.
(a) Perform a quick sort on the list to obtain the sorted list. You should show the result
of each pass and identify the pivots clearly.
(4)
A list of n numbers is to be sorted into descending order using bubble sort.
(b) Determine, in the worst case, the total number of comparisons required to sort the
list. Give your answer as a simplified expression in terms of n.
(2)
The following algorithm determines an approximation to the value of e
Step 1 Start
Step 2 Let a = 1
Step 3 Let b = 1
Step 4 Let c = 1
Step 5 Let d = a
Step 6 Let c c b
Step 7 Let d d 1c
Step 8 If b = 6 go to Step 11
Step 9 Let b = b + 1
Step 10 Go to Step 6
Step 11 Output d
Step 12 Stop
(c) Complete the table in the answer book to show the results obtained at each step of
the algorithm.
(3)
(d) Calculate, to 3 significant figures, the percentage error in using the value found in
(c) to approximate the value of e
(1)
(Total for Question 2 is 10 marks)
, 3.
G 12 F
11
47 24 14
A
35 E
9 35 31
25 11
8
B
40 D
17
C
Figure 1
Direct roads between seven villages, A, B, C, D, E, F and G, are represented in
Figure 1. The weight on each arc is the time, in minutes, taken to travel along the
corresponding road. Three roads, AB, AD and GE, are one-way, as indicated by the
arrow on the corresponding arc.
Floyd‟s algorithm is to be used to find the complete network of shortest times between
the seven villages.
(a) Set up an initial time matrix for this network.
(2)
The time matrix after three iterations of Floyd‟s algorithm is shown below.
A B C D E F G
A – 9 49 17 35 44 11
B – 40 8 35 87
C 40 – 17 75 47
D 8 17 – 11 31 64
E 35 44 84 11 – 14 46
F 35 75 31 14 – 12
G 11 20 47 28 24 12 –
(b) Perform the next two iterations of Floyd‟s algorithm that follow from the
table above.
You should show only the time matrix after each iteration.
(5)
