| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | First-Fit Bin Packing |
| Difficulty | Easy -1.2 This is a standard D1 bin packing question requiring straightforward application of taught algorithms (lower bound calculation, first-fit algorithm, and full bins method). The calculations are routine with no problem-solving insight needed—students simply follow memorized procedures with small numbers that are easy to manipulate. |
| Spec | 7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| Answer | Marks |
|---|---|
| (a) All arcs must be traversed twice. (So no arc needs repeating more than twice.) All valencies therefore even. | B1 (1) |
| (b) e.g. CECAEFEAFABFBACDBDGFGDC length = \(2 \times 6 = 12\) km | M1 A1 A1 (3) |
**(a)** All arcs must be traversed twice. (So no arc needs repeating more than twice.) All valencies therefore even. | B1 (1)
**(b)** e.g. CECAEFEAFABFBACDBDGFGDC length = $2 \times 6 = 12$ km | M1 A1 A1 (3)
---12\\
10
The numbers in the list above represent the lengths, in metres, of ten lengths of fabric. They are to be cut from rolls of fabric of length 60 m .
\begin{enumerate}[label=(\alph*)]
\item Calculate a lower bound for the number of rolls needed.\\
(2)
\item Use the first-fit bin packing algorithm to determine how these ten lengths can be cut from rolls of length 60 m .
\item Use full bins to find an optimal solution that uses the minimum number of rolls.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 Q12}}