| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2016 |
| Session | January |
| Marks | 15 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Apply Prim's algorithm from vertex |
| Difficulty | Easy -1.2 This is a routine Decision Maths question testing standard algorithm application (bin packing, bubble sort, quick sort) with no problem-solving or insight required. The algorithms are mechanical procedures learned by rote, and parts (a)-(d) involve straightforward execution of these procedures on given data. Part (e) requires only basic lower bound calculation. Significantly easier than average A-level maths questions which typically require mathematical reasoning rather than algorithmic execution. |
| Spec | 7.03j Sorting: bubble sort and shuttle sort7.03k Sorting: quick sort7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| Answer | Marks | Guidance |
|---|---|---|
| (a) | Bin 1: 12.1, 9.3, 10.9. Bin 2: 15.7, 6.4, 7.9. Bin 3: 17.4, 8.1. Bin 4: 20.1. Bin 5: 14.0 | M1 A1 A1 |
| (b)(i) | 12.1, 15.7, 10.9, 17.4, 9.3, 20.1, 7.9, 8.1, 14.0, 6.4. Then: 15.7, 12.1, 17.4, 10.9, 20.1, 9.3, 8.1, 14.0, 7.9, 6.4 | M1 A1 |
| (ii) | Comparisons = 9 + 8 = 17. Swaps = 7 + 5 = 12 | B1 B1 |
| (c) | Quick sort – pivots p, selected and first pass given >p, p, <p. If only choosing one pivot per iteration then M1. First pass correct, next pivot chosen correctly for second pass. Second and third passes correct (follow through from first pass and choice of pivots) – and next pivot(s) chosen consistently for fourth pass. Cso including choice of pivots for the fifth pass and 'sort complete' | M1 A1 A1ft A1 |
| (d) | Bin 1: 20.1, 12.1. Bin 2: 17.4, 14.0. Bin 3: 15.7, 10.9, 6.4. Bin 4: 9.3, 8.1, 7.9 | M1 A1 A1 |
| (e) | e.g. \(\frac{121.9}{33} \approx 3.694\) so yes 4 bins is optimal | B1 |
| Answer | Marks |
|---|---|
| a1M1 | First four items placed correctly |
| a1A1 | First eight items placed correctly |
| a2A1 | Cso |
| b1M1 | Bubble sort – 6.4 at the end of the list after the first pass |
| b1A1 | Cao |
| b1B1 | Cao on total number of comparisons (allow 9 and 8 seen and referred to correctly) |
| b2B1 | Cao on total number of swaps (allow 7 and 5 seen and referred to correctly) |
| c1M1 | Quick sort – pivots, p. selected and first pass given >p, p, <p. If only choosing one pivot per iteration then M1. |
| c1A1 | First pass correct, next pivot chosen correctly for second pass. |
| c2A1ft | Second and third passes correct (follow through from first pass and choice of pivots) – and next pivot(s) chosen consistently for fourth pass. |
| c3A1 | Cso including choice of pivots for the fifth pass and 'sort complete' |
| d1M1 | First four items placed correctly |
| d1A1 | First eight items placed correctly |
| d2A1 | Cso |
| e1B1 | Cao |
(a) | Bin 1: 12.1, 9.3, 10.9. Bin 2: 15.7, 6.4, 7.9. Bin 3: 17.4, 8.1. Bin 4: 20.1. Bin 5: 14.0 | M1 A1 A1 | (3) |
(b)(i) | 12.1, 15.7, 10.9, 17.4, 9.3, 20.1, 7.9, 8.1, 14.0, 6.4. Then: 15.7, 12.1, 17.4, 10.9, 20.1, 9.3, 8.1, 14.0, 7.9, 6.4 | M1 A1 | (2) |
(ii) | Comparisons = 9 + 8 = 17. Swaps = 7 + 5 = 12 | B1 B1 | (4) |
(c) | Quick sort – pivots p, selected and first pass given >p, p, <p. If only choosing one pivot per iteration then M1. First pass correct, next pivot chosen correctly for second pass. Second and third passes correct (follow through from first pass and choice of pivots) – and next pivot(s) chosen consistently for fourth pass. Cso including choice of pivots for the fifth pass and 'sort complete' | M1 A1 A1ft A1 | (4) |
(d) | Bin 1: 20.1, 12.1. Bin 2: 17.4, 14.0. Bin 3: 15.7, 10.9, 6.4. Bin 4: 9.3, 8.1, 7.9 | M1 A1 A1 | (3) |
(e) | e.g. $\frac{121.9}{33} \approx 3.694$ so yes 4 bins is optimal | B1 | (1) |
**Notes:**
| a1M1 | First four items placed correctly |
| a1A1 | First eight items placed correctly |
| a2A1 | Cso |
| b1M1 | Bubble sort – 6.4 at the end of the list after the first pass |
| b1A1 | Cao |
| b1B1 | Cao on total number of comparisons (allow 9 and 8 seen and referred to correctly) |
| b2B1 | Cao on total number of swaps (allow 7 and 5 seen and referred to correctly) |
| c1M1 | Quick sort – pivots, p. selected and first pass given >p, p, <p. If only choosing one pivot per iteration then M1. |
| c1A1 | First pass correct, next pivot chosen correctly for second pass. |
| c2A1ft | Second and third passes correct (follow through from first pass and choice of pivots) – and next pivot(s) chosen consistently for fourth pass. |
| c3A1 | Cso including choice of pivots for the fifth pass and 'sort complete' |
| d1M1 | First four items placed correctly |
| d1A1 | First eight items placed correctly |
| d2A1 | Cso |
| e1B1 | Cao |
**Total: 15 marks**
---3.\\
6.4\\
7.9\\
8.1\\
12.19 .3\\
14.0\\
15.7\\
17.4\\
20.1
\begin{enumerate}[label=(\alph*)]
\item Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 33
The list is to be sorted into descending order.
\item \begin{enumerate}[label=(\roman*)]
\item Starting at the left-hand end of the list, perform two passes through the list using a bubble sort. Write down the state of the list that results at the end of each pass.
\item Write down the total number of comparisons and the total number of swaps performed during your two passes.
\end{enumerate}\item Use a quick sort on the original list to obtain a fully sorted list in descending order. You must make your pivots clear.
\item Use the first-fit decreasing bin packing algorithm to determine how the numbers listed can be packed into bins of size 33
\item Determine whether your answer to (d) uses the minimum number of bins. You must justify your answer.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2016 Q3 [15]}}