| Exam Board | Edexcel |
|---|---|
| Module | FD1 (Further Decision 1) |
| Year | 2022 |
| Session | June |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Algorithm Tracing |
| Difficulty | Moderate -0.5 This is a routine Further Maths Decision question testing standard algorithm tracing and bubble sort mechanics. Part (a) requires systematic table completion following given steps, parts (b)-(c) involve straightforward bubble sort execution and counting comparisons using the formula n(n-1)/2, and part (d) applies a given formula. While multi-part and requiring careful bookkeeping, it demands only procedural application of well-practiced algorithms with no novel problem-solving or insight. |
| Spec | 7.03j Sorting: bubble sort and shuttle sort7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Table with \(n=5\): \(a\): 1,2,3,4; \(b\): 3,2,1,0; \(c\): 3,8,13,16 | M1 | At least three rows completed with correct first row |
| Second and third rows correct | A1 | cao |
| Output: 16 | A1 | cao; must be stated on answer line or clearly written near table |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| First pass correct: 17 21 14 23 13 15 19 24 20 28 | M1 | Bubble sort; 28 in place; list of ten numbers beginning 17 21 14 23 13 |
| Second and third passes correct (three numbers in place at end) | A1 | |
| Fourth and fifth passes correct (five numbers in place at end) | A1ft | ft from candidate's third pass |
| Sixth pass showing no swaps | A1 | cso |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Total number of comparisons: \(9+8+7+6+5+4 = 39\) | B1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| 45 | B1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Using e.g. \(n=3\): \(\lambda(3)(3-1)(3+1)(3-2)=3\), or \(n=5\): \(\lambda(5)(5-1)(5+1)(5-2)=45\) to find \(\lambda = \frac{1}{8}\) | M1 | Considering comparisons for any positive integer \(n>2\); correct \(\lambda\) implies M1 |
| For \(K_{50}\): \(\frac{1}{8}(50)(50-1)(50+1)(50-2)\) | dM1 | Using their \(\lambda\) and \(n=50\) |
| 749 700 | A1 | cao; no marks for correct answer with no working |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Total comparisons for \(N\) values: \(\sum_{r=1}^{N-1} r = \frac{1}{2}(N-1)N\) | M1 | Considering total comparisons for list of \(N\) values, using standard series result \(\sum r = \frac{1}{2}n(n+1)\) to get correct quadratic expression |
| \(\frac{1}{2}\left(\frac{1}{2}n(n-1)-1\right)\left(\frac{1}{2}n(n-1)\right)\) | ||
| \(= \frac{1}{8}n(n-1)\left[n(n-1)-2\right]\) | dM1 | Dependent on M1 — substituting correct quadratic expression into correct quadratic expression with correct algebraic working |
| \(= \frac{1}{8}n(n-1)(n^2-n-2) = \frac{1}{8}n(n-1)(n-2)(n+1)\), so \(k=\frac{1}{8}\) | leading to \(\frac{1}{8}n(n-1)(n-2)(n+1)\) | |
| Maximum comparisons for \(K_{50}\) is \(749\,700\) | A1 | Correct answer |
# Question 6:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Table with $n=5$: $a$: 1,2,3,4; $b$: 3,2,1,0; $c$: 3,8,13,16 | M1 | At least three rows completed with correct first row |
| Second and third rows correct | A1 | cao |
| Output: 16 | A1 | cao; must be stated on answer line or clearly written near table |
## Part (b)(i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| First pass correct: 17 21 14 23 13 15 19 24 20 28 | M1 | Bubble sort; 28 in place; list of ten numbers beginning 17 21 14 23 13 |
| Second and third passes correct (three numbers in place at end) | A1 | |
| Fourth and fifth passes correct (five numbers in place at end) | A1ft | ft from candidate's third pass |
| Sixth pass showing no swaps | A1 | cso |
## Part (b)(ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Total number of comparisons: $9+8+7+6+5+4 = 39$ | B1 | cao |
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| 45 | B1 | cao |
## Part (d)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Using e.g. $n=3$: $\lambda(3)(3-1)(3+1)(3-2)=3$, or $n=5$: $\lambda(5)(5-1)(5+1)(5-2)=45$ to find $\lambda = \frac{1}{8}$ | M1 | Considering comparisons for any positive integer $n>2$; correct $\lambda$ implies M1 |
| For $K_{50}$: $\frac{1}{8}(50)(50-1)(50+1)(50-2)$ | dM1 | Using their $\lambda$ and $n=50$ |
| 749 700 | A1 | cao; no marks for correct answer with no working |
# Bubble Sort / K_n Comparisons Question:
## Maximum Comparisons in K_n
| Answer/Working | Mark | Guidance |
|---|---|---|
| Total comparisons for $N$ values: $\sum_{r=1}^{N-1} r = \frac{1}{2}(N-1)N$ | M1 | Considering total comparisons for list of $N$ values, using standard series result $\sum r = \frac{1}{2}n(n+1)$ to get correct quadratic expression |
| $\frac{1}{2}\left(\frac{1}{2}n(n-1)-1\right)\left(\frac{1}{2}n(n-1)\right)$ | | |
| $= \frac{1}{8}n(n-1)\left[n(n-1)-2\right]$ | dM1 | Dependent on M1 — substituting correct quadratic expression into correct quadratic expression with correct algebraic working |
| $= \frac{1}{8}n(n-1)(n^2-n-2) = \frac{1}{8}n(n-1)(n-2)(n+1)$, so $k=\frac{1}{8}$ | | leading to $\frac{1}{8}n(n-1)(n-2)(n+1)$ |
| Maximum comparisons for $K_{50}$ is $749\,700$ | A1 | Correct answer |
---6. The following algorithm determines the number of comparisons made when Prim's algorithm is applied to $\mathrm { K } _ { n }$
Step 1 Start\\
Step 2 Input the value of $n$\\
Step 3 Let $a = 1$\\
Step 4 Let $b = n - 2$\\
Step 5 Let $c = b$\\
Step 6 Let $a = a + 1$\\
Step $7 \quad$ Let $b = b - 1$\\
Step 8 Let $c = c + ( a \times b ) + ( a - 1 )$\\
Step 9 If $b > 0$ go to Step 6\\
Step 10 Output $C$\\
Step 11 Stop
\begin{enumerate}[label=(\alph*)]
\item For $\mathrm { K } _ { 5 }$, complete the table in the answer book to show the results obtained at each step of the algorithm.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{27586973-89f4-45e1-9cc4-04c4044cd3db-11_595_703_175_680}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\end{center}
\end{figure}
The weights of the ten arcs in Figure 4 are
$$\begin{array} { l l l l l l l l l l }
17 & 21 & 24 & 14 & 23 & 13 & 15 & 19 & 28 & 20
\end{array}$$
\item \begin{enumerate}[label=(\roman*)]
\item Starting at the left-hand end of the above list, sort the list into ascending order using bubble sort. You need only write down the state of the list at the end of each pass.
\item Find the total number of comparisons performed during the sort.
\end{enumerate}\item Find the maximum total number of comparisons required to sort the weights of the 10 arcs of $\mathrm { K } _ { 5 }$ into ascending order using bubble sort.
It is given that the maximum total number of comparisons required to sort the weights of the arcs of $\mathrm { K } _ { n }$ into ascending order using bubble sort is
$$\lambda n ( n - 1 ) ( n + 1 ) ( n - 2 )$$
where $\lambda$ is a constant.
\item Determine the maximum total number of comparisons required to sort the weights of the arcs of $\mathrm { K } _ { 50 }$ into ascending order using bubble sort. You must make your method and working clear.
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD1 2022 Q6 [12]}}