| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2010 |
| Session | June |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Lower Bound for Bins |
| Difficulty | Easy -1.3 This is a straightforward application of standard bin-packing algorithms taught in D1. Part (a) requires simple arithmetic (sum/capacity), parts (b) and (c) are direct algorithm applications with no problem-solving required, and part (d) asks for a standard justification. The question is entirely procedural with no novel insight needed, making it easier than average A-level questions which typically require some problem-solving or connection between concepts. |
| Spec | 7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| e.g. total weight is 239, lower bound is \(\frac{239}{60}=3.98\) so 4 bins. | M1 A1 | M1: Any correct statement, must involve calculation<br>1A1: cao (accept 4 for both marks) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Bin 1: 41<br>Bin 2: 28 + 31<br>Bin 3: 42<br>Bin 4: 36<br>Bin 5: 32<br>Bin 6: 29 | M1 A1 A1 | M1: Bins 1 and 2 correct and at least 6 values put in bins<br>1A1: Bins 1,2,3 and 4 correct.<br>2A1: All correct |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Full Bins: 28 + 32, 31 + 29<br>The other 3 items (42, 41, 36) require 3 separate bins | M1 A1 | M1: Attempt to find two full bins and allocate at least 6 values<br>1A1: cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| There are 5 items over 30. No two of these 5 can be paired in a bin, so at least 5 bins will be required. | B2, 1, 0 | 1B1: Correct argument may be imprecise or muddled (bod gets B1)<br>2B1: A good, clear, correct argument. (They have answered the question 'why?') |
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| e.g. total weight is 239, lower bound is $\frac{239}{60}=3.98$ so 4 bins. | M1 A1 | M1: Any correct statement, must involve calculation<br>1A1: cao (accept 4 for both marks) |
**Total: 2 marks**
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Bin 1: 41<br>Bin 2: 28 + 31<br>Bin 3: 42<br>Bin 4: 36<br>Bin 5: 32<br>Bin 6: 29 | M1 A1 A1 | M1: Bins 1 and 2 correct and at least 6 values put in bins<br>1A1: Bins 1,2,3 and 4 correct.<br>2A1: All correct |
**Total: 3 marks**
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Full Bins: 28 + 32, 31 + 29<br>The other 3 items (42, 41, 36) require 3 separate bins | M1 A1 | M1: Attempt to find two full bins and allocate at least 6 values<br>1A1: cao |
**Total: 2 marks**
## Part (d)
| Answer | Marks | Guidance |
|--------|-------|----------|
| There are 5 items over 30. No two of these 5 can be paired in a bin, so at least 5 bins will be required. | B2, 1, 0 | 1B1: Correct argument may be imprecise or muddled (bod gets B1)<br>2B1: A good, clear, correct argument. (They have answered the question 'why?') |
**Total: 2 marks**
**Grand Total for Q3: 9 marks**
---41 28 42 31 36 32 29
The numbers in the list represent the weights, in kilograms, of seven statues. They are to be transported in crates that will each hold a maximum weight of 60 kilograms.
\begin{enumerate}[label=(\alph*)]
\item Calculate a lower bound for the number of crates that will be needed to transport the statues.
[2]
\item Use the first-fit bin packing algorithm to allocate the statues to the crates.
[3]
\item Use the full bin algorithm to allocate the statues to the crates.
[2]
\item Explain why it is not possible to transport the statues using fewer crates than the number needed for part (c).
[2]
\end{enumerate}
(Total 9 marks)
\hfill \mbox{\textit{Edexcel D1 2010 Q3 [9]}}