| Exam Board | Edexcel |
|---|---|
| Module | FD1 AS (Further Decision 1 AS) |
| Year | 2020 |
| Session | June |
| Marks | 6 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | First-Fit Bin Packing |
| Difficulty | Moderate -0.8 Part (a) is a straightforward application of the first-fit algorithm with clear numbers and bin size—pure procedural execution requiring no problem-solving. Part (b) asks for algorithmic complexity analysis (worst case is O(n²)), which is standard theory for Decision Maths but requires understanding that each item may need comparing with all previous bins. Overall, this is easier than average A-level maths due to being algorithmic/procedural rather than requiring mathematical insight or proof techniques. |
| Spec | 7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Bin 1: \(\overline{3.7}\) \(\overline{2.5}\) \(\overline{1.9}\) | M1 | First four items placed correctly (values in boxes) with at least eight values placed – allow cumulative totals for M1 only |
| Bin 2: \(\overline{5.4}\) \(\underline{2.7}\) | A1 | First eight items placed correctly (values in boxes and underlined) – no repeated values |
| Bin 3: \(\underline{3.2}\) \(\underline{3.1}\) \(2.0\) | A1 | CSO (so no repeated values) |
| Bin 4: \(\underline{2.7}\) \(4.2\) | ||
| Total | (3) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| In the worst case the second number must be compared with the first number so 1 comparison, then the third number must be compared with the first and second numbers so 2 comparisons… so in total there are \(1 + 2 + 3 + \ldots + (n-1)\) comparisons in total | M1 | Considers the correct worst case and attempts to sum the total number of comparisons – this mark can be implied by the correct summation |
| \(1 + 2 + \ldots + (n-1) = \frac{1}{2}(n-1)n\) | A1 | Correct sum evaluation seen or implied from a correct simplified formula together with the correct method for determining the total number of comparisons in the worst case. Note: simply stating \(\frac{1}{2}n(n-1)\) gives M1A0. Minimum for M1A1: \(\sum_{r=1}^{n-1} r = \frac{1}{2}n(n-1)\) |
| \(\frac{1}{2}(n-1)n\) so quadratic order | B1 | Or equivalent e.g. order \(n^2\), \(O(n^2)\), etc. Independent of previous M and A marks |
| Total | (3) |
## Question 1:
### Part (a):
| Answer/Working | Marks | Guidance |
|---|---|---|
| Bin 1: $\overline{3.7}$ $\overline{2.5}$ $\overline{1.9}$ | M1 | First four items placed correctly (values in boxes) with at least eight values placed – allow cumulative totals for M1 only |
| Bin 2: $\overline{5.4}$ $\underline{2.7}$ | A1 | First eight items placed correctly (values in boxes and underlined) – no repeated values |
| Bin 3: $\underline{3.2}$ $\underline{3.1}$ $2.0$ | A1 | CSO (so no repeated values) |
| Bin 4: $\underline{2.7}$ $4.2$ | | |
| **Total** | **(3)** | |
### Part (b):
| Answer/Working | Marks | Guidance |
|---|---|---|
| In the worst case the second number must be compared with the first number so 1 comparison, then the third number must be compared with the first and second numbers so 2 comparisons… so in total there are $1 + 2 + 3 + \ldots + (n-1)$ comparisons in total | M1 | Considers the correct worst case and attempts to sum the total number of comparisons – this mark can be implied by the correct summation |
| $1 + 2 + \ldots + (n-1) = \frac{1}{2}(n-1)n$ | A1 | Correct sum evaluation seen or implied from a correct simplified formula together with the correct method for determining the total number of comparisons in the worst case. Note: simply stating $\frac{1}{2}n(n-1)$ gives M1A0. Minimum for M1A1: $\sum_{r=1}^{n-1} r = \frac{1}{2}n(n-1)$ |
| $\frac{1}{2}(n-1)n$ so quadratic order | B1 | Or equivalent e.g. order $n^2$, $O(n^2)$, etc. Independent of previous M and A marks |
| **Total** | **(3)** | |
**Overall total: (6 marks)**1.
$3.7 \quad 2.5$\\
$5.4 \quad 1.9$\\
2.7\\
3.2\\
3.1\\
2.7\\
4.2\\
2.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 8.5
The first-fit bin packing algorithm is to be used to pack $n$ numbers into bins. The number of comparisons is used to measure the order of the first-fit bin packing algorithm.
\item By considering the worst case, determine the order of the first-fit bin packing algorithm in terms of $n$. You must make your method and working clear.
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD1 AS 2020 Q1 [6]}}