A2 June 2022 Q6

EdexcelCurrent spec12 marksAlgorithms Minimum Spanning Trees

6. The following algorithm determines the number of comparisons made when Prim’s algorithm is applied to \(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	Let \(b = b - 1\)
Step 8	Let \(c = c + (a \times b) + (a - 1)\)
Step 9	If \(b \gt 0\) go to Step 6
Step 10	Output \(c\)
Step 11	Stop

(a) For \(K_5\), complete the table in the answer book to show the results obtained at each step of the algorithm. (3)

You may not need to use all the rows in this table. It may not be necessary to complete all the boxes in each row.

\(n\)	\(a\)	\(b\)	\(c\)

Output: ____________

Figure 4: complete graph on A, B, C, D and E with arcs AB 17, AC 28, AD 24, AE 14, BC 19, BD 21, BE 15, CD 23, CE 20, DE 13 — Figure 4

The weights of the ten arcs in Figure 4 are

(b)

(i) 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.

(ii) Find the total number of comparisons performed during the sort. (5)

(c) Find the maximum total number of comparisons required to sort the weights of the 10 arcs of \(K_5\) into ascending order using bubble sort. (1)

It is given that the maximum total number of comparisons required to sort the weights of the arcs of \(K_n\) into ascending order using bubble sort is

\(\lambda n(n - 1)(n + 1)(n - 2)\)

where \(\lambda\) is a constant.

(d) Determine the maximum total number of comparisons required to sort the weights of the arcs of \(K_{50}\) into ascending order using bubble sort. You must make your method and working clear. (3)

Mark scheme (a)

Scheme

Marks

\(n\)	\(a\)	\(b\)	\(c\)
5	1	3	3
	2	2	8
	3	1	13
	4	0	16

M1
A1

1.1b
1.1b

Output: 16

2.2a

(3)

Notes

(a) M1: At least three rows of cells completed with a correct first row – condone repeated values in all columns or a single value in each row

A1: cao – the values in the second and third rows correct

A1: cao – correct output following a correct fourth row (with no extra rows) – the output must either be stated on the given answer line or ‘output 16’ must be clearly written somewhere near the table (do not bod the 16 circled, underlined, written twice, etc.)

Mark scheme (b)

Scheme

Marks

(i)

17	21	24	14	23	13	15	19	28	20
17	21	14	23	13	15	19	24	20	28
17	14	21	13	15	19	23	20	24	28
14	17	13	15	19	21	20	23	24	28
14	13	15	17	19	20	21	23	24	28
13	14	15	17	19	20	21	23	24	28
13	14	15	17	19	20	21	23	24	28

M1
A1
A1ft
A1

1.1b
1.1b
1.1b
1.1b

(ii) Total number of comparisons: 9 + 8 + 7 + 6 + 5 + 4 = 39

2.2a

(5)

Notes

(b)(i) M1: Bubble sort. Consistent direction, end number (28) in place, the list containing ten numbers with the list beginning with the correct first five numbers (17 21 14 23 13). Do check these carefully as some candidates show the result of each comparison and swap in their first pass. Consider the placement of the candidate’s numbers, rather than what the candidate labels each line of their pass. For example, assume that the first time that the 28 appears at the end of the list is the end of their first pass

A1: Second and third passes correct – so end three numbers in place

A1ft: Fourth and fifth passes correct following through from the candidate’s third pass – so end five numbers in place. After their third pass their list must contain the correct 10 numbers

A1: cso (correct solution only – so previous three marks must have been awarded in this part). Must show a 6^th pass showing no swaps/changes (give bod if the passes are not labelled but do not award this mark if it is clear that after the 5^th pass the list is simply being written out again (rather than a genuine 6^th pass taking place)). Condone if the sort continues until a 9^th pass has been completed (but there must be no changes in the 6^th to 9^th passes)

(b)(ii) B1: cao (for total number of comparisons)

In (b) starting at the right-hand end of the list is M0. Quick sort (or any other sorting algorithm e.g. shuttle) is M0. No misreads in this part – mark exactly to the scheme.

If sorting into descending order, then award M1 for 21 24 17 23 14 15 19 28 20 13 and the first A1 for both 24 21 23 17 15 19 28 20 14 13 and 24 23 21 17 19 28 20 15 14 13 ONLY (so two out of the first four marks) even if the list is re-ordered after the sort is complete

Scheme	Marks	AO
45	B1	2.2a
	(1)

Mark scheme (d)

Scheme	Marks	AO
e.g. when \(n = 3\) the total number of comparisons is 3 therefore \(\lambda(3)(3 - 1)(3 + 1)(3 - 2) = 3\) e.g. when \(n = 5\) the total number of comparisons is 45 (from (c)) therefore \(\lambda(5)(5 - 1)(5 + 1)(5 - 2) = 45\)	M1	3.1a
For \(K_{50}\) total number of comparisons is \(\text{‘}\lambda\text{’}(50)(50 - 1)(50 + 1)(50 - 2)\)	dM1	3.4
749 700	A1	2.2a
	(3)
	(12 marks)

Notes

(d) M1: Considering the total number of comparisons for any positive integer value of \(n\) (greater than 2) and substitute into the given expression (if correct \(\lambda = \dfrac{1}{8}\)). The correct value of \(\lambda\) implies this mark. If using \(n = 5\) then follow through their value from (c). If any other value of \(n\) used, then the maximum number of comparisons must be correct e.g.

\(n\)	3	4	5	6	7	8	9	10
Comparisons	3	15	45	105	210	378	630	990

dM1: Using their \(\lambda\) and \(n = 50\) to calculate the maximum total number of comparisons (dependent on the previous M mark). Writing \(\dfrac{1}{8}(50)(50 - 1)(50 + 1)(50 - 2)\) implies the first two M marks

A1: cao (749 700) – no marks for the correct answer with no working

Alternative solution to (d) for those who are clearly using an algebraic method to derive the quartic expression for the maximum total number of comparisons:

If there are \(N\) values then
1^st pass of bubble sort requires \(N - 1\) comparisons
2^nd pass of bubble sort requires \(N - 2\) comparisons
3^rd pass of bubble sort requires \(N - 3\) comparisons and so on

Therefore, the total number of comparisons is \(\displaystyle\sum_{r=1}^{N-1} r = \tfrac{1}{2}(N - 1)N\) M1

Maximum number of comparisons in \(K_n\) is therefore
\(\tfrac{1}{2}\left(\tfrac{1}{2}n(n - 1) - 1\right)\left(\tfrac{1}{2}n(n - 1)\right)\)
\(= \tfrac{1}{8}n(n - 1)\left[n(n - 1) - 2\right]\)
\(= \tfrac{1}{8}n(n - 1)(n^2 - n - 2) = \tfrac{1}{8}n(n - 1)(n - 2)(n + 1)\) so \(\lambda = \tfrac{1}{8}\) dM1

Therefore, maximum number of comparisons for \(K_{50}\) is 749 700 A1

M1: Considering the total number of comparisons that are required to sort a list containing \(N\) values (possibly will see \(1 + 2 + 3 + \ldots + (n - 1)\)) and using the standard series result that \(\sum r = \tfrac{1}{2}n(n + 1)\) to get the correct quadratic expression for the total number of comparisons when sorting \(N\) values (allow any letter)

dM1: Dependent on previous M mark – substituting the correct quadratic expression into the correct quadratic expression with correct algebraic working leading to \(\tfrac{1}{8}n(n - 1)(n - 2)(n + 1)\)

A1: Correct answer of 749 700

[Corrected from the printed mark scheme: the alternative solution ends “so \(k = \tfrac{1}{8}\)”; the constant in the question is \(\lambda\).]