AS June 2022 Q1

EdexcelAS paperCurrent spec9 marksAlgorithms Minimum Spanning Trees

The list of eleven numbers shown above is to be sorted into ascending order.

(a) Carry out a quick sort to produce the sorted list. You should show the result of each pass and identify your pivots clearly. (4)

Figure 1: weighted network on vertices A to G with arcs AC 55, AB 52, BC 41, BD 47, CD 34, CE 37, CF 33, DE 28, DG 59, EG 42, FG 44 — Figure 1

(b) Use Kruskal’s algorithm to find the minimum spanning tree for the network in Figure 1. You should list the arcs in the order in which you consider them. For each arc, state whether or not you are adding it to your minimum spanning tree. (3)

(c)

(i) Draw the minimum spanning tree on Diagram 1 in the answer book.

(ii) State the total weight of the tree. (2)

Diagram 1: the vertices A to G of Figure 1 with no arcs — Diagram 1

Mark scheme (a)

Scheme

Marks

middle right											Pivot(s)
55	44	34	59	28	\(\underline{37}\)	41	52	33	42	47	37
34	\(\underline{28}\)	33	37	55	44	59	\(\underline{41}\)	52	42	47	28 41
28	34	\(\underline{33}\)	37	41	55	44	59	\(\underline{52}\)	42	47	33 52
28	33	34	37	41	44	\(\underline{42}\)	47	52	55	\(\underline{59}\)	(34) 42 59
28	33	34	37	41	42	44	\(\underline{47}\)	52	55	59	47 (55)
28	33	34	37	41	42	44	47	52	55	59	(Sort complete)

middle left											Pivot(s)
55	44	34	59	28	\(\underline{37}\)	41	52	33	42	47	37
34	\(\underline{28}\)	33	37	55	44	59	\(\underline{41}\)	52	42	47	28 41
28	\(\underline{34}\)	33	37	41	55	44	\(\underline{59}\)	52	42	47	34 59
28	33	34	37	41	55	44	\(\underline{52}\)	42	47	59	(33) 52
28	33	34	37	41	44	\(\underline{42}\)	47	52	55	59	42 (55)
28	33	34	37	41	42	\(\underline{44}\)	47	52	55	59	44
28	33	34	37	41	42	44	47	52	55	59	(Sort Complete)

M1
A1
A1ft
A1

1.1b
1.1b
1.1b
1.1b

(4)

Notes

M1: Quick Sort, pivot, p, chosen (must be choosing middle right or middle left). After the first pass the list must read (values less than the pivot), pivot, (values greater than the pivot). If choosing one pivot per iteration then M1 only. This mark can be scored if one number only is either missing or incorrect or an additional number is added to the list.

A1: First two passes correct (pivots for third pass need not be chosen)

A1ft: Third and fourth passes correct (follow through from their second pass and choice of pivots) (pivot(s) for the fifth pass need not be chosen). After their second pass their list must contain either 10, 11 or 12 numbers (so allow one additional/missing number)

A1: cso – if choosing middle right pivots then they must include a fifth pass and if choosing middle left then they must include a sixth pass

SC: If list is sorted into descending order, then award a maximum of M1A1A0A0 (so 2 marks) as in the scheme above even if the list is re-ordered after the sort is complete

Mark scheme (b)

Scheme	Marks	AO
DE, CF, CD, reject CE; BC, EG, reject FG; reject BD, AB, (reject AC, reject DG)	M1 A1 A1	1.1b 1.1b 1.1b
	(3)

Notes

M1: Kruskal: first three arcs correctly chosen (DE, CF, CD), and arc CE rejected at the correct time. No follow through from an incorrect list. Condone list of weights for this mark only (28, 33, 34 and reject 37)

A1: First five arcs correctly chosen (DE, CF, CD, BC, EG), and arc FG rejected at the correct time. Must state the arcs and not the corresponding weights for this mark

A1: cso including all rejections correct and at the correct time. We do not need to see the explicit rejection of arcs AC and DG but if these are explicitly rejected then they must be in the correct order. Note that a list of all the arcs in the correct order followed by a list of the arcs in the MST can score full marks

Scheme	Marks	AO
(i)	B1	2.2a
(ii) (Total weight =) 230	B1	2.2a
	(2)
	(9 marks)