| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2005 |
| Session | January |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Quick Sort Execution |
| Difficulty | Easy -1.3 This is a straightforward algorithmic execution question requiring students to mechanically apply two standard D1 algorithms (Quick Sort and First-Fit Decreasing bin packing) with no problem-solving or insight needed. The steps are entirely procedural, following textbook methods exactly, making it easier than average A-level questions which typically require some mathematical reasoning or connection between concepts. |
| Spec | 7.03k Sorting: quick sort7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| Answer | Marks | Guidance |
|---|---|---|
| 650, 643, 710, 455, 431, 245, 234, 162, 452, 134 | M1 A1 A1 A1 (5) | 5 bins needed; optimal |
| Answer | Marks | Guidance |
|---|---|---|
| Bin 1: \(710 + 245\) | Bin 3: \(643 + 162 + 134\) | M1 A1 |
| Bin 2: \(650 + 234\) | Bin 4: \(455 + 452\) | A1 A1 (4) |
| Answer | Marks | Guidance |
|---|---|---|
| \[\frac{e^{2+1.16}}{1280} = \frac{4 \cdot 1.16}{1280}\] | M1 A1 (2) | 5 bins needed; optimal |
## Part (a)
650, 643, 710, 455, 431, 245, 234, 162, 452, 134 | M1 A1 A1 A1 (5) | 5 bins needed; optimal
## Part (b)
Bin 1: $710 + 245$ | Bin 3: $643 + 162 + 134$ | M1 A1
Bin 2: $650 + 234$ | Bin 4: $455 + 452$ | A1 A1 (4)
## Part (c)
$$\frac{e^{2+1.16}}{1280} = \frac{4 \cdot 1.16}{1280}$$ | M1 A1 (2) | 5 bins needed; optimal
---$650 \quad 431 \quad 245 \quad 643 \quad 455 \quad 134 \quad 710 \quad 234 \quad 162 \quad 452$
\begin{enumerate}[label=(\alph*)]
\item The list of numbers above is to be sorted into descending order. Perform a Quick Sort to obtain the sorted list, giving the state of the list after each pass, indicating the pivot elements. [5]
\end{enumerate}
The numbers in the list represent the lengths, in mm, of some pieces of wood. The wood is sold in one metre lengths.
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{1}
\item Use the first-fit decreasing bin packing algorithm to determine how these pieces could be cut from the minimum number of one metre lengths. (You should ignore wastage due to cutting.) [4]
\item Determine whether your solution to part (b) is optimal. Give a reason for your answer. [2]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2005 Q4 [11]}}