| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2008 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Permutations & Arrangements |
| Type | Sorting and searching algorithms |
| Difficulty | Easy -1.2 This is a straightforward application of standard bin packing algorithms from D1 with clear instructions. Students need only recall the definitions of first-fit and first-fit decreasing algorithms and apply them mechanically to a small dataset (9 items). The lower bound calculation is a simple sum divided by capacity. No problem-solving insight or novel thinking required—pure algorithmic execution. |
| Spec | 7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| Answer | Marks | Guidance |
|---|---|---|
| (a) \(\frac{502}{100} = 5.02\) so 6 tapes. | M1 A1 | (2 marks) |
| (b) Bin 1: 29, 52; Bin 2: 73; Bin 3: 87; Bin 4: 74; Bin 5: 47, 38; Bin 6: 61; Bin 7: 41 | M1 A1 A1 | (3 marks) |
| Answer | Marks | Guidance |
|---|---|---|
| (c) Bin 1: 87; Bin 2: 74; Bin 3: 73; Bin 4: 61, 38; Bin 5: 52, 47; Bin 6: 41, 29 | M1 A1 A1 | (3 marks) |
**(a)** $\frac{502}{100} = 5.02$ so 6 tapes. | M1 A1 | (2 marks) |
**(b)** Bin 1: 29, 52; Bin 2: 73; Bin 3: 87; Bin 4: 74; Bin 5: 47, 38; Bin 6: 61; Bin 7: 41 | M1 A1 A1 | (3 marks) |
**Guidance:** M1: Bin 1 correct and at least 8 values put in bins. A1: Condone one error (e.g. extra, omission, 'balanced' swap). A1: All correct
**(c)** Bin 1: 87; Bin 2: 74; Bin 3: 73; Bin 4: 61, 38; Bin 5: 52, 47; Bin 6: 41, 29 | M1 A1 A1 | (3 marks) |
**Guidance:** M1: Bin 1 correct and at least 8 values put in bins. A1: Condone one error (e.g. extra, omission, 'balanced' swap). A1: All correct
**Total for Q1: 8 marks**
---1.
$\begin{array} { l l l l l l l l l } 29 & 52 & 73 & 87 & 74 & 47 & 38 & 61 & 41 \end{array}$
The numbers in the list represent the lengths in minutes of nine radio programmes. They are to be recorded onto tapes which each store up to 100 minutes of programmes.
\begin{enumerate}[label=(\alph*)]
\item Obtain a lower bound for the number of tapes needed to store the nine programmes.
\item Use the first-fit bin packing algorithm to fit the programmes onto the tapes.
\item Use the first-fit decreasing bin packing algorithm to fit the programmes onto the tapes.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2008 Q1 [8]}}