| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2021 |
| Session | June |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Bubble Sort Execution |
| Difficulty | Easy -1.8 This is a routine algorithmic execution question requiring only mechanical application of standard D1 algorithms (bubble sort and bin packing) with no problem-solving or insight. Each part follows textbook procedures exactly, making it significantly easier than average A-level maths questions which typically require some mathematical reasoning. |
| Spec | 7.03j Sorting: bubble sort and shuttle sort7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
No marking scheme content provided.
---1.
$\begin{array} { l l l l l l l l l l l l l } 16 & 23 & 18 & 9 & 4 & 20 & 35 & 5 & 17 & 13 & 6 & 11 \end{array}$\\
The numbers in the list represent the weights, in kilograms, of twelve parcels. The parcels are to be transported in containers that will each hold a maximum weight of 45 kg .
\begin{enumerate}[label=(\alph*)]
\item Calculate a lower bound for the number of containers needed. You must make your method clear.
\item Use the first-fit bin packing algorithm to allocate the parcels to the containers.
\item Carry out a bubble sort, starting at the left-hand end of the list, to produce a list of the weights in descending order. You should only give the state of the list after each pass.
\item Use the first-fit decreasing bin packing algorithm to allocate the parcels to the containers.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2021 Q1 [12]}}