OCR Further Discrete AS Specimen — Question 6 8 marks

Exam BoardOCR
ModuleFurther Discrete AS (Further Discrete AS)
SessionSpecimen
Marks8
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicCombinations & Selection
TypeBin packing problems
DifficultyStandard +0.8 This question requires understanding of bin packing algorithms (first-fit vs first-fit decreasing), working backwards to deduce bin capacity from given outcomes, and analyzing time complexity of combined algorithms. It goes beyond standard recall to require problem-solving with constraints and algorithmic analysis, typical of Further Discrete modules but still within reach of well-prepared students.
Spec7.03k Sorting: quick sort7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin
6 The following masses, in kg, are to be packed into bins. $$\begin{array} { l l l l l l l l l l } 8 & 5 & 9 & 7 & 7 & 9 & 1 & 3 & 3 & 8 \end{array}$$
  1. Chloe says that first-fit decreasing gives a packing that requires 4 bins, but first-fit only requires 3 bins. Find the maximum capacity of the bins. First-fit requires one pass through the list and the time taken may be regarded as being proportional to the length of the list. Suppose that shuttle sort was used to sort the list into decreasing order.
  2. What can be deduced, in this case, about the order of the time complexity, \(\mathrm { T } ( n )\), for first-fit decreasing?
Question 6:
AnswerMarks Guidance
6(i) Total mass is 60, so each bin must hold at least
20kg
If it is 20kg then using first-fit:
8 5 7
9 7 1 3
9 3 8
Using first-fit decreasing:
9 9 1
8 8 3
7 7 5
3
But if the capacity was 21kg then the 3 could go
into the first bin and the 1 into the second bin, so
only three bins are needed
So the bins cannot be more than 20kg, so they
AnswerMarks
must be exactly 20kgB1
M1
A1
M1
A1
E1
AnswerMarks
[6]1.1
3.1b
1.1
3.1b
1.1
i
c
AnswerMarks
3.2aConsider total mass to find a lower
bound for capacity
Attempt first-fit with a capacity of at
least 20kg
All correnct, in this order
e
Attempt first-fit decreasing with a
capacity of at least 20kg
m
All correct, in this order (or a
description in words)
20 is also the upper bound, so the
AnswerMarks
capacity is 20First bin correct, in this order
Correct placement of the values
9 9 8 8 7 7
AnswerMarks Guidance
6(ii) Shuttle sort has quadratic order, as a fupnction of
the length of the list, so the time to run first-fit
decreasing would be the sum oSf a quadratic
function and a linear function, which is a
quadratic function
This means that first fit-decreasing has quadratic
AnswerMarks
order in this casee
M1
A1
AnswerMarks
[2]1.1
2.2aKnowing and using the fact that shuttle
sort has quadratic orderT(cid:11)n(cid:12)(cid:32)O (cid:11) n2(cid:12) (cid:14)O(cid:11)n(cid:12)
(cid:11) n2(cid:12)
(cid:32)O
6(i)
n
e
m
i
c
e
p
S
6(ii)(a)
6(ii)(a)
n
e
m
AnswerMarks
6(iii)i
c
e
p
S
Question 6:
6 | (i) | Total mass is 60, so each bin must hold at least
20kg
If it is 20kg then using first-fit:
8 5 7
9 7 1 3
9 3 8
Using first-fit decreasing:
9 9 1
8 8 3
7 7 5
3
But if the capacity was 21kg then the 3 could go
into the first bin and the 1 into the second bin, so
only three bins are needed
So the bins cannot be more than 20kg, so they
must be exactly 20kg | B1
M1
A1
M1
A1
E1
[6] | 1.1
3.1b
1.1
3.1b
1.1
i
c
3.2a | Consider total mass to find a lower
bound for capacity
Attempt first-fit with a capacity of at
least 20kg
All correnct, in this order
e
Attempt first-fit decreasing with a
capacity of at least 20kg
m
All correct, in this order (or a
description in words)
20 is also the upper bound, so the
capacity is 20 | First bin correct, in this order
Correct placement of the values
9 9 8 8 7 7
6 | (ii) | Shuttle sort has quadratic order, as a fupnction of
the length of the list, so the time to run first-fit
decreasing would be the sum oSf a quadratic
function and a linear function, which is a
quadratic function
This means that first fit-decreasing has quadratic
order in this case | e
M1
A1
[2] | 1.1
2.2a | Knowing and using the fact that shuttle
sort has quadratic order | T(cid:11)n(cid:12)(cid:32)O (cid:11) n2(cid:12) (cid:14)O(cid:11)n(cid:12)
(cid:11) n2(cid:12)
(cid:32)O
--- 6(i) ---
6(i)
n
e
m
i
c
e
p
S
6(ii)(a)
6(ii)(a)
n
e
m
--- 6(iii) ---
6(iii) | i
c
e
p
S
6 The following masses, in kg, are to be packed into bins.

$$\begin{array} { l l l l l l l l l l } 
8 & 5 & 9 & 7 & 7 & 9 & 1 & 3 & 3 & 8
\end{array}$$

(i) Chloe says that first-fit decreasing gives a packing that requires 4 bins, but first-fit only requires 3 bins. Find the maximum capacity of the bins.

First-fit requires one pass through the list and the time taken may be regarded as being proportional to the length of the list. Suppose that shuttle sort was used to sort the list into decreasing order.\\
(ii) What can be deduced, in this case, about the order of the time complexity, $\mathrm { T } ( n )$, for first-fit decreasing?

\hfill \mbox{\textit{OCR Further Discrete AS  Q6 [8]}}
This paper (8 questions)
View full paper
Q1 2 Q2 7 Q3 6 Q4 6 Q5 8 Q6 8 Q7 11 Q8 12