| Exam Board | Edexcel |
|---|---|
| Module | FD1 (Further Decision 1) |
| Year | 2019 |
| Session | June |
| Marks | 8 |
| 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 algorithms from Decision Maths. Part (a) is mechanical first-fit bin packing, part (b) is routine quick sort execution showing working, and part (c) is a simple proportion calculation using the given complexity formula. All parts require only direct application of learned procedures with no problem-solving or insight needed, making it easier than average A-level questions. |
| Spec | 7.03g Order notation: O(n^k) for k = 0,1,2,3,47.03k Sorting: quick sort7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance Notes |
| Bin 1: 2.1, 1.7, 1.2 | M1 | First six items placed correctly and at least eight values placed in bins - condone cumulative totals for M1 only (the underlined values) |
| Bin 2: 3.0, 1.9 | ||
| Bin 3: 3.2, 1.4, 0.2 | A1 | CSO – all correct (no additional/repeated values) |
| Bin 4: 3.3, 1.5 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance Notes |
| First pass: 2.1 1.7 3.0 1.9 \(\boxed{1.2}\) 3.3 1.4 1.5 0.2, Pivot: 1.2 | M1 | Quick sort, pivot chosen (must be middle left or right – choosing first/last is M0). After first pass list must read: (values greater than pivot), pivot, (values less than pivot). If only choosing one pivot per iteration then max M1A1 only |
| 2.1 1.7 3.0 1.9 \(\boxed{3.2}\) 3.3 1.4 1.5 1.2 0.2, Pivot(s): 3.2, (0.2) | A1 | First pass correct and next pivots chosen correctly for second pass |
| 3.3 \(\underline{3.2}\) 2.1 1.7 3.0 \(\boxed{1.9}\) 1.4 1.5 1.2 0.2, Pivot(s): (3.3) 1.9 | A1ft | Second and third passes correct (follow through from first pass and choice of pivots) |
| 3.3 \(\underline{3.2}\) 2.1 \(\boxed{3.0}\) 1.9 1.7 \(\boxed{1.4}\) 1.5 1.2 0.2, Pivots: 3.0, 1.4 | ||
| 3.3 \(\underline{3.2}\) \(\underline{3.0}\) 2.1 1.9 1.7 \(\boxed{1.5}\) \(\underline{1.4}\) 1.2 0.2, Pivot(s): (2.1) 1.5 | A1 | CSO – all previous marks must have been awarded, including fifth pass with 1.5 as pivot (middle right) or fourth pass with 1.7 as pivot (middle left) |
| 3.3 \(\underline{3.2}\) \(\underline{3.0}\) 2.1 1.9 1.7 \(\underline{1.5}\) \(\underline{1.4}\) \(\underline{1.2}\) 0.2 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance Notes |
| \(\dfrac{2.32(11250\log 11250)}{450\log 450}\) | M1 | Complete correct method – allow reciprocal – allow slips in values only e.g. 1250 for 11250 |
| \(= 88.6\) seconds | A1 | CAO – exact value of 88.6 must be stated at some point; isw if 90 follows 88.6 seen. Answer of 88.6 with no working scores M1A0. Condone lack of units (but if present must be correct) |
# Question 1:
## Part (a)
| Answer/Working | Marks | Guidance Notes |
|---|---|---|
| Bin 1: 2.1, 1.7, 1.2 | M1 | First six items placed correctly and at least eight values placed in bins - condone cumulative totals for M1 only (the underlined values) |
| Bin 2: 3.0, 1.9 | | |
| Bin 3: 3.2, 1.4, 0.2 | A1 | CSO – all correct (no additional/repeated values) |
| Bin 4: 3.3, 1.5 | | |
**(2 marks)**
---
## Part (b)
| Answer/Working | Marks | Guidance Notes |
|---|---|---|
| First pass: 2.1 1.7 3.0 1.9 $\boxed{1.2}$ 3.3 1.4 1.5 0.2, Pivot: 1.2 | M1 | Quick sort, pivot chosen (must be middle left or right – choosing first/last is M0). After first pass list must read: (values greater than pivot), pivot, (values less than pivot). **If only choosing one pivot per iteration then max M1A1 only** |
| 2.1 1.7 3.0 1.9 $\boxed{3.2}$ 3.3 1.4 1.5 1.2 0.2, Pivot(s): 3.2, (0.2) | A1 | First pass correct **and** next pivots chosen correctly for second pass |
| 3.3 $\underline{3.2}$ 2.1 1.7 3.0 $\boxed{1.9}$ 1.4 1.5 1.2 0.2, Pivot(s): (3.3) 1.9 | A1ft | Second and third passes correct (follow through from first pass and choice of pivots) |
| 3.3 $\underline{3.2}$ 2.1 $\boxed{3.0}$ 1.9 1.7 $\boxed{1.4}$ 1.5 1.2 0.2, Pivots: 3.0, 1.4 | | |
| 3.3 $\underline{3.2}$ $\underline{3.0}$ 2.1 1.9 1.7 $\boxed{1.5}$ $\underline{1.4}$ 1.2 0.2, Pivot(s): (2.1) 1.5 | A1 | CSO – all previous marks **must** have been awarded, including fifth pass with 1.5 as pivot (middle right) or fourth pass with 1.7 as pivot (middle left) |
| 3.3 $\underline{3.2}$ $\underline{3.0}$ 2.1 1.9 1.7 $\underline{1.5}$ $\underline{1.4}$ $\underline{1.2}$ 0.2 | | |
**(4 marks)**
---
## Part (c)
| Answer/Working | Marks | Guidance Notes |
|---|---|---|
| $\dfrac{2.32(11250\log 11250)}{450\log 450}$ | M1 | Complete correct method – allow reciprocal – allow slips in values only e.g. 1250 for 11250 |
| $= 88.6$ seconds | A1 | CAO – exact value of 88.6 must be stated at some point; isw if 90 follows 88.6 seen. Answer of 88.6 with no working scores M1A0. Condone lack of units (but if present must be correct) |
**(2 marks)**
**Total: 8 marks**1.
0.2\\
1.7\\
1.9\\
1.2\\
1.4\\
1.5\\
2.1\\
3.0\\
3.2\\
3.3
\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 5
The list of numbers is now to be sorted into descending order.
\item Perform a quick sort on the original list to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.
For a list of $n$ numbers, the quick sort algorithm has, on average, order $n \log n$.\\
Given that it takes 2.32 seconds to run the algorithm when $n = 450$
\item calculate approximately how long it will take, to the nearest tenth of a second, to run the algorithm when $n = 11250$. You should make your method and working clear.
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD1 2019 Q1 [8]}}