| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2018 |
| Session | Specimen |
| Marks | 15 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | First-Fit Bin Packing |
| Difficulty | Easy -1.2 This is a straightforward application of standard D1 algorithms (first-fit, bubble sort, quick sort) with no problem-solving required. Students simply execute memorized procedures step-by-step on given data. The bin packing and sorting are routine textbook exercises requiring only careful bookkeeping, making this easier than average A-level maths questions. |
| 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 |
|---|---|---|
| Bin 5: 14.0 | M1 A1, A1 | First four numbers placed correctly (therefore Bin 1 correct and 15.7 in Bin 2) and at least seven numbers put in bins – condone cumulative totals here only. First eight numbers placed correctly (therefore Bins 1 and 2 correct and 17.4 in Bin 3 and 20.1 in Bin 4). cso All correct |
| Answer | Marks | Guidance |
|---|---|---|
| 15.7 12.1 17.4 10.9 20.1 9.3 8.1 14.0 7.9 6.4 | M1 A1 | Bubble sort – first pass correct |
| Answer | Marks | Guidance |
|---|---|---|
| Swaps = 7 + 5 = 12 | B1 B1 | cao on total number of comparisons; cao on total number of swaps |
| Answer | Marks |
|---|---|
| 12.1 9.3 15.7 10.9 17.4 \(\boxed{6.4}\) 20.1 7.9 8.1 14.0 Pivot 6.4 | M1, A1 |
| 12.1 9.3 15.7 10.9 17.4 20.1 7.9 8.1 14.0 6.4 Pivot 17.4 | A1 (\(1^{\text{st}}/2^{\text{nd}}\) passes/pivot for \(3^{\text{rd}}\)) |
| 20.1 17.4 12.1 9.3 15.7 \(\boxed{10.9}\) 7.9 8.1 14.0 6.4 Pivot (20.1) 10.9 | A1ft (\(3^{\text{rd}}/4^{\text{th}}\) passes/pivot for \(5^{\text{th}}\)) |
| 20.1 17.4 12.1 \(\boxed{15.7}\) 14.0 10.9 9.3 \(\boxed{7.9}\) 8.1 6.4 Pivots 15.7 7.9 | A1 |
| 20.1 17.4 15.7 12.1 \(\boxed{14.0}\) 10.9 9.3 \(\boxed{8.1}\) 7.9 6.4 Pivots 14.0 8.1 | |
| 20.1 17.4 15.7 14.0 12.1 10.9 9.3 8.1 7.9 6.4 Sort complete | A1 (cso + 'sort complete') |
| Answer | Marks | Guidance |
|---|---|---|
| Bin 4: 9.3 \(\boxed{8.1}\) 7.9 | M1 A1, A1 | Must be using 'sorted' list in decreasing order (independent of (c)). First four numbers placed correctly and at least seven numbers put in bins – condone cumulative totals here only. First eight numbers placed correctly. cso – all correct |
| Answer | Marks | Guidance |
|---|---|---|
| \(\frac{121.9}{33} \approx 3.694\) so yes 4 bins is optimal | B1ft | or awrt 3.7 (or 3.6 with correct calculation seen) and 4 together with a correct conclusion based on their answer to (d) (a correct calculation etc. with an answer of 4 with no conclusion (as a minimum accept 'yes') scores B0) |
## 3(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 | First four numbers placed correctly (therefore Bin 1 correct and 15.7 in Bin 2) and at least seven numbers put in bins – condone cumulative totals here only. First eight numbers placed correctly (therefore Bins 1 and 2 correct and 17.4 in Bin 3 and 20.1 in Bin 4). cso All correct
## 3(b)
(i) 12.1 15.7 10.9 17.4 9.3 20.1 7.9 8.1 14.0 6.4
15.7 12.1 17.4 10.9 20.1 9.3 8.1 14.0 7.9 6.4 | M1 A1 | Bubble sort – first pass correct
(ii) Comparisons = 9 + 8 = 17
Swaps = 7 + 5 = 12 | B1 B1 | cao on total number of comparisons; cao on total number of swaps
## 3(c)
Quick sort, pivot p, chosen (must be choosing middle left or right – choosing first/last item as pivot is M0) and first pass gives >p, p, <p. So after the first pass the list should read (values greater than the pivot), pivot, (values less than the pivot). If only choosing one pivot per iteration M1 only
12.1 9.3 15.7 10.9 17.4 $\boxed{6.4}$ 20.1 7.9 8.1 14.0 Pivot 6.4 | M1, A1 |
12.1 9.3 15.7 10.9 17.4 20.1 7.9 8.1 14.0 6.4 Pivot 17.4 | A1 ($1^{\text{st}}/2^{\text{nd}}$ passes/pivot for $3^{\text{rd}}$) |
20.1 17.4 12.1 9.3 15.7 $\boxed{10.9}$ 7.9 8.1 14.0 6.4 Pivot (20.1) 10.9 | A1ft ($3^{\text{rd}}/4^{\text{th}}$ passes/pivot for $5^{\text{th}}$) |
20.1 17.4 12.1 $\boxed{15.7}$ 14.0 10.9 9.3 $\boxed{7.9}$ 8.1 6.4 Pivots 15.7 7.9 | A1 |
20.1 17.4 15.7 12.1 $\boxed{14.0}$ 10.9 9.3 $\boxed{8.1}$ 7.9 6.4 Pivots 14.0 8.1 | |
20.1 17.4 15.7 14.0 12.1 10.9 9.3 8.1 7.9 6.4 Sort complete | A1 (cso + 'sort complete') |
## 3(d)
Bin 1: 20.1 $\boxed{12.1}$
Bin 2: 17.4 14.0
Bin 3: 15.7 10.9 6.4
Bin 4: 9.3 $\boxed{8.1}$ 7.9 | M1 A1, A1 | Must be using 'sorted' list in decreasing order (independent of (c)). First four numbers placed correctly and at least seven numbers put in bins – condone cumulative totals here only. First eight numbers placed correctly. cso – all correct
## 3(e)
$\frac{121.9}{33} \approx 3.694$ so yes 4 bins is optimal | B1ft | or awrt 3.7 (or 3.6 with correct calculation seen) and 4 together with a correct conclusion based on their answer to (d) (a correct calculation etc. with an answer of 4 with no conclusion (as a minimum accept 'yes') scores B0)
---12.1 \quad 9.3 \quad 15.7 \quad 10.9 \quad 17.4 \quad 6.4 \quad 20.1 \quad 7.9 \quad 8.1 \quad 14.0
\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 \hfill [3]
\end{enumerate}
The list is to be sorted into descending order.
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{1}
\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}
\hfill [4]
\item Use a quick sort on the original list to obtain a fully sorted list in descending order. You must make your pivots clear. \hfill [4]
\item Use the first-fit decreasing bin packing algorithm to determine how the numbers listed can be packed into bins of size 33 \hfill [3]
\item Determine whether your answer to (d) uses the minimum number of bins. You must justify your answer. \hfill [1]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2018 Q3 [15]}}