Instructions

 Use black ink or ball-point pen.

 If pencil is used for diagrams/sketches/graphs it must be dark (HB or B).
 Fill in the boxes at the top of this page with your name, centre number and candidate number.
 Answer all the questions and ensure that your answers to parts of questions are clearly labelled.
 Answer the questions in the spaces 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.

Information
 A booklet ‘Mathematical Formulae and Statistical Tables’ is provided.
 There are 9 questions in this question paper. The total mark for this paper is 95.
 The marks for each question are shown in brackets – use this as a guide as to how much time to
spend on each question.
 Calculators must not be used for questions marked with a * sign.

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.
 If you change your mind about an answer, cross it out and put your new answer and any working
underneath.
1.

Figure 1
Hero’s algorithm for finding a square root is described by the flow chart shown in Figure 1.
Given that N = 72 and E = 8,
(a) use the flow chart to complete the table in the answer book, working to at least seven
decimal places when necessary. Give the final output correct to seven decimal places.
(4)
The flow chart is used with N = 72 and E = – 8,
(b) describe how this would affect the output.
(1)

(c) State the value of E which cannot be used when using this flow chart.
(1)
(Total 6 marks)
___________________________________________________________________________

2 Turn over
2.
31 10 38 45 19 47 35 28 12
(a) Use the first-fit bin packing algorithm to determine how the numbers listed above can be
packed into bins of size 60.
(3)

(b) Carry out a quick sort to produce a list of the numbers in descending order. You should
show the result of each pass and identify your pivots clearly.
(4)

(c) Use the first-fit decreasing bin packing algorithm to determine how the numbers listed
can be packed into bins of size 60.
(2)

(d) Determine whether the number of bins used in (c) is optimal. Give a reason for your
answer.
(2)

(Total 11 marks)
_______________________________________________________________________________

3.
0.6 1.5 1.6 0.2 0.4 0.5 0.7 0.1 0.9 0.3
(a) Use the first-fit bin packing algorithm to determine how the numbers listed above can be
packed into bins of size 2.
(3)

(b) The list of numbers is to be sorted into descending order. Use a quick sort to obtain the
sorted list. You must make your pivots clear.
(4)

(c) Apply the first-fit decreasing bin packing algorithm to your ordered list to pack the
numbers into bins of size 2.
(3)

(d) Determine whether your answer to part (c) uses the minimum number of bins. You must
justify your answer.
(1)
(Total 11 marks)
_______________________________________________________________________________

3 Turn over
4.
23 29 11 34 10 14 35 17
The numbers represent the sizes, in megabytes (MB), of eight files.
The files are to be stored on 50 MB discs.
(a) Calculate a lower bound for the number of discs needed to store all eight files.
(2)

(b) Use the first-fit bin packing algorithm to fit the files onto the discs.
(3)

(c) Perform a bubble sort on the numbers in the list to sort them into descending order. You
need only write down the final result of each pass.
(4)

(d) Use the first-fit decreasing bin packing algorithm to fit the files onto the discs.
(3)
(Total 12 marks)
___________________________________________________________________________

4 Turn over
5.
42 21 15 16 35 10 31 11 27 39

(a) Use the first-fit bin packing algorithm to determine how the numbers listed above can be
packed into bins of size 65.
(3)
(b) The list of numbers is to be sorted into descending order. Use a quick sort to obtain the
sorted list. You should show the result of each pass and identify your pivots clearly.
(4)
(c) Use the first-fit decreasing bin packing algorithm on your ordered list to pack the
numbers into bins of size 65.
(3)

The nine distinct numbers below are to be sorted into descending order

23 14 17 x 21 18 8 20 11

A bubble sort, starting at the left-hand end of the list, is to be used to obtain the sorted list.
After the first complete pass, the list is

23 17 x 21 18 14 20 11 8

After the second complete pass, the list is

23 17 21 18 x 20 14 11 8

(d) Using this information, write down the smallest interval that must contain x. Give your
answer as an inequality.
(3)
(Total 13 marks)
___________________________________________________________________________

5 Turn over
6.

An algorithm is described by the flow chart shown in Figure 4.

Given that x = 27 and y = 5,

(a) complete the table in the answer book to show the results obtained at each step when the
algorithm is applied. Give the final output.
(4)

The numbers 122 and are to be used as inputs for the algorithm described by the flow chart.

(b) (i) State, giving a reason, which number should be input as x.

(ii) State the output.

(3)
(Total 7 marks)
___________________________________________________________________________

6 Turn over
7.
59 45 18 55 47 11 63 17 15 42

(a) The list of numbers above is to be sorted into descending order. Perform a quick sort to
obtain the sorted list. You should show the result of each pass and identify your pivots
clearly.
(4)

The numbers in the list represent the lengths, in cm, of some pieces of copper wire. The
copper wire is sold in one metre lengths.

(b) Use the first-fit decreasing bin packing algorithm to determine how these pieces could be
cut from one metre lengths. (You should ignore wastage due to cutting.)
(3)
(c) Determine whether your solution to (b) is optimal. Give a reason for your answer.
(2)
(Total 9 marks)

___________________________________________________________________________

8.
5 1 8 13 16 5 8 2 15 12 10
(a) Use the first-fit bin packing algorithm to determine how the numbers listed above can be
packed into bins of size 20.
(3)

(b) The list of numbers is to be sorted into descending order. Use a bubble sort to obtain the
sorted list, giving the state of the list after each complete pass.
(5)

(c) Apply the first-fit decreasing bin packing algorithm to your ordered list to pack the
numbers into bins of size 20.
(3)

(d) Determine whether your answer to (c) uses the minimum number of bins. You must
justify your answer.
(2)
(Total 13 marks)
___________________________________________________________________________

7 Turn over
9.
24 14 8 x 19 25 6 17 9
The numbers in the list represent the exact weights, in kilograms, of 9 suitcases. One suitcase
is weighed inaccurately and the only information known about the unknown weight, x kg, of
this suitcase is that 19 < x ≤ 23. The suitcases are to be transported in containers that can hold
a maximum of 50 kilograms.
(a) Use the first-fit bin packing algorithm, on the list provided, to allocate the suitcases to
containers.
(3)

(b) Using the list provided, carry out a quick sort to produce a list of the weights in
descending order. Show the result of each pass and identify your pivots clearly.
(4)

(c) Apply the first-fit decreasing bin packing algorithm to the ordered list to determine the 2
possible allocations of suitcases to containers.
(4)
After the first-fit decreasing bin packing algorithm has been applied to the ordered list, one of
the containers is full.
(d) Calculate the possible integer values of x. You must show your working.
(2)

(Total 13 marks)

TOTAL FOR PAPER: 95 MARKS

8 Turn over