| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2013 |
| Session | Specimen |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | First-Fit Bin Packing |
| Difficulty | Easy -1.8 This is a straightforward application of standard D1 bin-packing algorithms with small numbers and clear steps. Part (a) requires simple arithmetic (sum/capacity), parts (b-c) are mechanical algorithm applications following textbook procedures, and part (d) asks for basic observation that the solution matches the lower bound. No problem-solving insight or novel reasoning required. |
| Spec | 7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Total weight is 239, lower bound is \(\frac{239}{60} = 3.98\) so 4 bins | M1, A1 | 2 marks; 1M1: Any correct statement, must involve calculation; 1A1: cao (accept 4 for both marks) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Bin 1: 41; Bin 2: \(28+31\); Bin 3: 42; Bin 4: 36; Bin 5: 32; Bin 6: 29 | M1 A1, A1 | 3 marks; 1M1: Bins 1 and 2 correct and at least 6 values put in bins; 1A1: Bins 1,2,3 and 4 correct; 2A1: All correct |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Full Bins: \(28+32\), \(31+29\); The other 3 items (42, 41, 36) require 3 separate bins | M1 A1 | 2 marks; 1M1: Attempt to find two full bins and allocate at least 6 values; 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 | 2 marks; 1B1: Correct argument may be imprecise or muddled (bod gets B1); 2B1: A good, clear, correct argument (they have answered the question 'why?') |
# Question 3:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Total weight is 239, lower bound is $\frac{239}{60} = 3.98$ so 4 bins | M1, A1 | **2 marks**; 1M1: Any correct statement, must involve calculation; 1A1: cao (accept 4 for both marks) |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Bin 1: 41; Bin 2: $28+31$; Bin 3: 42; Bin 4: 36; Bin 5: 32; Bin 6: 29 | M1 A1, A1 | **3 marks**; 1M1: Bins 1 and 2 correct and at least 6 values put in bins; 1A1: Bins 1,2,3 and 4 correct; 2A1: All correct |
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Full Bins: $28+32$, $31+29$; The other 3 items (42, 41, 36) require 3 separate bins | M1 A1 | **2 marks**; 1M1: Attempt to find two full bins and allocate at least 6 values; 1A1: cao |
## 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 | **2 marks**; 1B1: Correct argument may be imprecise or muddled (bod gets B1); 2B1: A good, clear, correct argument (they have answered the question 'why?') |
**Misread in (b) First Fit Decreasing:** Bin 1: 42, Bin 2: 41, Bin 3: 36, Bin 4: 32 28, Bin 5: 31 29 — remove up to two A marks if earned, so M1 max in (b) if first 4 bins correct.
**Total: 9 marks**
---3.
$$\begin{array} { l l l l l l l }
41 & 28 & 42 & 31 & 36 & 32 & 29
\end{array}$$
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.
\item Use the first-fit bin packing algorithm to allocate the statues to the crates.
\item Use the full bin algorithm to allocate the statues to the crates.
\item Explain why it is not possible to transport the statues using fewer crates than the number needed for part (c).
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2013 Q3 [9]}}