| Exam Board | OCR |
|---|---|
| Module | Further Discrete AS (Further Discrete AS) |
| Year | 2021 |
| Session | November |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Next-Fit Bin Packing |
| Difficulty | Moderate -0.3 This is a straightforward application of standard bin-packing algorithms with clear procedures. Part (a) requires mechanical execution of three well-defined algorithms, part (b) tests basic understanding of online/offline terminology, and part (c) requires some trial-and-error optimization but no sophisticated insight. The question is slightly easier than average because it's mostly procedural with minimal problem-solving demand. |
| Spec | 7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin7.03m Packing extensions: 2D/3D packing and knapsack problems |
| Answer | Marks | Guidance |
|---|---|---|
| 2 | (a) | (i) |
| Answer | Marks |
|---|---|
| Bin 5 7 5 | M1 |
| Answer | Marks |
|---|---|
| [2] | 1.1 |
| 1.1 | Bins 1 and 2 correct |
| Answer | Marks | Guidance |
|---|---|---|
| 2 | (a) | (ii) |
| Answer | Marks |
|---|---|
| Bin 5 | M1 |
| Answer | Marks |
|---|---|
| [2] | 1.1 |
| 1.1 | Bins 1 and 2 correct |
| Answer | Marks | Guidance |
|---|---|---|
| 2 | (a) | (iii) |
| Answer | Marks |
|---|---|
| Bin 5 | M1 |
| Answer | Marks |
|---|---|
| [2] | 1.1 |
| 1.1 | Ordered list may be seen |
| Answer | Marks | Guidance |
|---|---|---|
| 2 | (b) | With ‘online’ lists the items are presented one at a |
| Answer | Marks |
|---|---|
| ‘offline’ list. | B1 |
| Answer | Marks |
|---|---|
| [2] | 1.2 |
| 2.3 | Evidence of understanding what ‘online’ means |
| Answer | Marks | Guidance |
|---|---|---|
| Bin 1 | 12 | |
| Bin 2 | 23 | |
| Bin 3 | 15 | |
| Bin 4 | 18 | 8 |
| Bin 5 | 7 | 5 |
| Bin 1 | 12 | 15 |
| Bin 2 | 23 | 7 |
| Bin 3 | 18 | 8 |
| Bin 4 | 5 |
| Answer | Marks | Guidance |
|---|---|---|
| Bin 1 | 23 | 7 |
| Bin 2 | 18 | 12 |
| Bin 3 | 15 | 8 |
| Answer | Marks | Guidance |
|---|---|---|
| 2 | (c) | 88 ÷ 4 = 22, so M is at least 22 |
| Answer | Marks |
|---|---|
| Hence, least M is 23 | M1 |
| Answer | Marks |
|---|---|
| [3] | 1.1 |
| Answer | Marks |
|---|---|
| 2.2a | Identifying that M must be at least 22 |
Question 2:
2 | (a) | (i) | Next-fit method
Bin 1 12
Bin 2 23
Bin 3 15
Bin 4 18 8
Bin 5 7 5 | M1
A1
[2] | 1.1
1.1 | Bins 1 and 2 correct
All correct
2 | (a) | (ii) | First-fit method
Bin 1 12 15
Bin 2 23 7
Bin 3 18 8
Bin 4 5
Bin 5 | M1
A1
[2] | 1.1
1.1 | Bins 1 and 2 correct
All correct
2 | (a) | (iii) | 23 18 15 12 8 7 5
First-fit decreasing method
Bin 1 23 7
Bin 2 18 12
Bin 3 15 8 5
Bin 4
Bin 5 | M1
A1
[2] | 1.1
1.1 | Ordered list may be seen
Bins 1 and 2 correct
All correct
2 | (b) | With ‘online’ lists the items are presented one at a
time and the whole list is not known until the end.
With next-fit and first-fit the items are placed in
the order they appear in the list, so these methods
can be used ‘offline’ or ‘online’.
However, for first-fit decreasing the whole list
needs to be known before it can be sorted, so
first-fit decreasing can only be used for an
‘offline’ list. | B1
B1
[2] | 1.2
2.3 | Evidence of understanding what ‘online’ means
Evidence of realising that ffd cannot be used with an online list
(or implied from an appropriate statement about next-fit and first-fit)
Bin 1 | 12
Bin 2 | 23
Bin 3 | 15
Bin 4 | 18 | 8
Bin 5 | 7 | 5
Bin 1 | 12 | 15
Bin 2 | 23 | 7
Bin 3 | 18 | 8
Bin 4 | 5
Bin 5
Bin 1 | 23 | 7
Bin 2 | 18 | 12
Bin 3 | 15 | 8 | 5
Bin 4
Bin 5
2 | (c) | 88 ÷ 4 = 22, so M is at least 22
But it is not possible to fill 4 bins of capacity 22
Since 22 – 18 = 4 which is less than 5
So the 23 would have to be split as 4 and 19
And then there is no 3 to go with the 19
M = 23 is possible
e.g. 23 – x and x, 18 + 5, 15 + 8, 12 + 7
Hence, least M is 23 | M1
A1
B1
[3] | 1.1
2.4
2.2a | Identifying that M must be at least 22
Showing that M = 22 is not possible
Fully correct explanation
Showing that M = 23 is possible2 Seven items need to be packed into bins. Each bin has capacity 30 kg . The sizes of the items, in kg, in the order that they are received, are as follows.\\
12\\
23\\
15\\
18\\
8\\
7\\
5
\begin{enumerate}[label=(\alph*)]
\item Find the packing that results using each of these algorithms.
\begin{enumerate}[label=(\roman*)]
\item The next-fit method
\item The first-fit method
\item The first-fit decreasing method
\end{enumerate}\item A student claims that all three methods from part (a) can be used for both 'online' and 'offline' lists.
Explain why the student is wrong.
The bins of capacity 30 kg are replaced with bins of capacity $M \mathrm {~kg}$, where $M$ is an integer.\\
The item of size 23 kg can be split into two items, of sizes $x \mathrm {~kg}$ and $( 23 - x ) \mathrm { kg }$, where $x$ may be any integer value you choose from 1 to 11. No other item can be split.
\item Determine the smallest value of $M$ for which four bins are needed to pack these eight items.
Explain your reasoning carefully.
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete AS 2021 Q2 [11]}}