| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2017 |
| Session | January |
| Marks | 11 |
| 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 (first-fit, bubble sort, first-fit decreasing) with minimal problem-solving. All parts follow textbook procedures: calculating lower bound (sum/capacity), applying algorithms mechanically, and a simple explanation. The numbers are manageable and the question is highly structured with no novel insight required. |
| Spec | 7.03j Sorting: bubble sort and shuttle sort7.03k Sorting: quick sort7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
4. $\begin{array} { l l l l l l l l l } 23 & 18 & 27 & 9 & 25 & 10 & 12 & 30 & 24 \end{array}$
The numbers in the list represent the weights, in kilograms, of nine suitcases. The suitcases are to be transported in containers that will each hold a maximum weight of 45 kilograms.
\begin{enumerate}[label=(\alph*)]
\item Calculate a lower bound for the number of containers that will be needed to transport the suitcases.
\item Use the first-fit bin packing algorithm to allocate the suitcases to the containers.
\item Using the list provided, carry out a bubble sort to produce a list of the weights in descending order. You need only give the state of the list after each complete pass.
\item Use the first-fit decreasing bin packing algorithm to allocate the suitcases to the containers.
\item Explain why it is not possible to transport the suitcases using fewer containers than the number used in (d).
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2017 Q4 [11]}}