| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2011 |
| Session | January |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Permutations & Arrangements |
| Type | Sorting and searching algorithms |
| Difficulty | Moderate -0.8 This is a straightforward application of standard algorithms (first-fit bin packing, bubble sort, first-fit decreasing) taught in D1. All parts require direct execution of learned procedures with no problem-solving or insight needed. The lower bound calculation is a simple division. While multi-part, each step is routine and mechanical, making it easier than average A-level questions which typically require some conceptual understanding or problem-solving. |
| Spec | 7.03j Sorting: bubble sort and shuttle sort7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
2.
$$\begin{array} { l l l l l l l l }
23 & 29 & 11 & 34 & 10 & 14 & 35 & 17
\end{array}$$
The numbers represent the sizes, in megabytes (MB), of eight files.\\
The files are to be stored on 50 MB discs.
\begin{enumerate}[label=(\alph*)]
\item Calculate a lower bound for the number of discs needed to store all eight files.
\item Use the first-fit bin packing algorithm to fit the files onto the discs.
\item Perform a bubble sort on the numbers in the list to sort them into descending order. You need only write down the final result of each pass.
\item Use the first-fit decreasing bin packing algorithm to fit the files onto the discs.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2011 Q2 [12]}}