| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2016 |
| Session | June |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Quick Sort Execution |
| Difficulty | Moderate -0.8 This is a straightforward algorithmic execution question requiring mechanical application of quick sort and first-fit decreasing algorithms with clear procedures. While multi-part and requiring careful bookkeeping, it demands no problem-solving insight or novel thinking—just following standard D1 algorithms step-by-step, making it easier than average A-level maths questions. |
| Spec | 7.03k Sorting: quick sort7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Quick sort attempted with middle right/left pivot chosen | M1 | Must choose middle left or right; choosing first/last item as pivot is M0 |
| First two passes correct and next pivots correctly chosen for third pass (pivot values of 55 and 17, or 59 and 17) | A1 | |
| Third and fourth passes correct (follow through from second pass and choice of pivots) | A1ft | \(3^{rd}\) and \(4^{th}\) passes correct |
| Sort complete, with fifth pass using 42 (middle right) or 45 (middle left) as pivot | A1 CSO | All previous marks must have been awarded |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Using sorted list in descending order; first five items placed correctly and at least eight values placed in bins | M1 | Must use sorted list in descending order |
| Bin 1: 63, 18, 17; Bin 2: 59, 15, 11; Bin 3: 55, 45; Bin 4: 47, 42 — first eight items correctly placed | A1 | Underlined and boxed values correct |
| CSO | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| \(\frac{372}{100} = 3.72\), so yes the solution in (b) is optimal | M1 A1 | Attempt lower bound \((372 \pm 63)/100\); conclusion "yes" required as minimum |
# Question 3:
## Part (a):
| Answer/Working | Marks | Guidance |
|---|---|---|
| Quick sort attempted with middle right/left pivot chosen | M1 | Must choose middle left or right; choosing first/last item as pivot is M0 |
| First two passes correct **and** next pivots correctly chosen for third pass (pivot values of 55 and 17, or 59 and 17) | A1 | |
| Third and fourth passes correct (follow through from second pass and choice of pivots) | A1ft | $3^{rd}$ and $4^{th}$ passes correct |
| Sort complete, with fifth pass using 42 (middle right) or 45 (middle left) as pivot | A1 CSO | All previous marks must have been awarded |
## Part (b):
| Answer/Working | Marks | Guidance |
|---|---|---|
| Using sorted list in descending order; first five items placed correctly and at least eight values placed in bins | M1 | Must use sorted list in descending order |
| Bin 1: 63, 18, 17; Bin 2: 59, 15, 11; Bin 3: 55, 45; Bin 4: 47, 42 — first eight items correctly placed | A1 | Underlined **and** boxed values correct |
| CSO | A1 | |
## Part (c):
| Answer/Working | Marks | Guidance |
|---|---|---|
| $\frac{372}{100} = 3.72$, so yes the solution in (b) is optimal | M1 A1 | Attempt lower bound $(372 \pm 63)/100$; conclusion "yes" required as minimum |
---\begin{enumerate}
\item 594518553471183171542\\
(a) The list of numbers above is to be sorted into descending order. Perform a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.
\end{enumerate}
The numbers in the list represent the lengths, in cm, of some pieces of copper wire. The copper wire is sold in one metre lengths.\\
(b) Use the first-fit decreasing bin packing algorithm to determine how these pieces could be cut from one metre lengths. (You should ignore wastage due to cutting.)\\
(c) Determine whether your solution to (b) is optimal. Give a reason for your answer.\\
\hfill \mbox{\textit{Edexcel D1 2016 Q3 [9]}}