| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Quick Sort Execution |
| Difficulty | Easy -1.2 This is a straightforward algorithmic application question requiring execution of quicksort and first-fit decreasing bin-packing with no problem-solving insight. Both algorithms are standard D1 procedures that students practice repeatedly, and the question provides explicit instructions for each step. The arithmetic is simple and the bin-packing verification is mechanical calculation. |
| Spec | 7.03k Sorting: quick sort7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| Answer | Marks | Guidance |
|---|---|---|
| \(150 \quad 104 \quad 200 \quad \underline{184} \quad 84 \quad 120, \quad 60\) | ||
| \(L_1\) | ||
| \(200 \quad \underline{184} \quad 150 \quad 104 \quad 84 \quad 120 \quad 60\) | ||
| \(L_2\) | ||
| \(200 \quad 184 \quad 150 \quad \underline{104} \quad 120 \quad 84 \quad 60\) | ||
| \(L_3\) | ||
| \(200 \quad 184 \quad 150 \quad \underline{120} \quad 104 \quad 84 \quad 60\) | ||
| \(L_4\) | ||
| \(200 \quad 184 \quad 150 \quad 120 \quad 104 \quad 84 \quad 60\) | M2 A2 | now complete |
| Answer | Marks | Guidance |
|---|---|---|
| \(\therefore 5\) bins needed | M1 A1 | |
| (c) unused rod \(= (5 \times 240) - (200 + 184 + 150 + 120 + 104 + 84 + 60) = 298 \therefore\) not possible | B1 | (9) |
**(a)** 150 104 200 60 184 84 120 (pivot in box)
$150 \quad 104 \quad 200 \quad \underline{184} \quad 84 \quad 120, \quad 60$ | | |
| $L_1$ | | |
| $200 \quad \underline{184} \quad 150 \quad 104 \quad 84 \quad 120 \quad 60$ | | |
| $L_2$ | | |
| $200 \quad 184 \quad 150 \quad \underline{104} \quad 120 \quad 84 \quad 60$ | | |
| $L_3$ | | |
| $200 \quad 184 \quad 150 \quad \underline{120} \quad 104 \quad 84 \quad 60$ | | |
| $L_4$ | | |
| $200 \quad 184 \quad 150 \quad 120 \quad 104 \quad 84 \quad 60$ | M2 A2 | now complete |
**(b)** sort list in decreasing order and have bins of size 240 take each length in turn and put it in the first bin in which it can fit count number of bins used
[Bin packing diagram with 5 bins showing placement of 200, 184, 150, 120, 104, 84, 60]
$\therefore 5$ bins needed | M1 A1 |
**(c)** unused rod $= (5 \times 240) - (200 + 184 + 150 + 120 + 104 + 84 + 60) = 298 \therefore$ not possible | B1 | (9) |
---A machinist has to cut the following seven lengths (in centimetres) of steel tubing.
$$150 \quad 104 \quad 200 \quad 60 \quad 184 \quad 84 \quad 120$$
\begin{enumerate}[label=(\alph*)]
\item Perform a quick sort to put the seven lengths in descending order. [4 marks]
\end{enumerate}
The machinist is to cut the lengths from rods that are each 240 cm long. You may assume that no waste is incurred during the cutting process.
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{1}
\item Explain how to use the first-fit decreasing bin-packing algorithm to find the minimum number of rods required. Show that, using this algorithm, five rods are needed. [4 marks]
\item Find if it is possible to cut additional pieces with a total length of 300 cm from the five rods. [1 mark]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 Q3 [9]}}