Notes

a1M1: Quick sort, pivot, p, chosen (must be choosing middle left or right – choosing any other item as the pivot is M0). After the first pass the list must read (values greater than the pivot), pivot, (values less that the pivot). Condone one error or omission in the list.
If only choosing one pivot per iteration then max of M1 only
Bubble sort is not a MR and scores M0.
If the list is sorted into ascending order, they can score M1 A1 A0 A0 for a fully correct sort even if reversed (if any error seen this can score M1 only).
If 028 is written as 28 at any stage this will lose the final CSO mark
The choice of pivots may only be seen once they have been used

a1A1: First pass correct and next pivots chosen correctly for the second pass (but the second pass does not need to be correct)

a2A1ft: Second and third passes correct (follow through from their first pass and choice of pivots). They do not need to be choosing a pivot for the fourth pass for this mark
If they alternate MR and ML pivots for the first and second passes, the pivots for the third pass must be consistent with their second pass

a3A1: CSO – so must have chosen and used 747 (MR) or 828 (ML) as a pivot for the fifth pass

Sort Ascending Max M1 A1 A0 A0   e.g Middle right

Middle left

Notes

b1M1: Considering the total number of comparisons in the worst case (possibly will see e.g. \((n-1) + (n-2) + \ldots [+\, 2 + 1]\) which scores this mark (brackets not needed and sufficient terms to make sum clear. Accept a clear list without + signs for this mark)

b1A1: Using the standard series result that \(\sum r = \frac{1}{2}n(n+1)\) with \(n = (n-1)\) to get the correct quadratic expression for the total number of comparisons when sorting \(n\) values using bubble sort (allow any letter) Accept \((n-1) + (n-2) + \ldots + 2 + 1 = \frac{1}{2}n(n-1)\) for both marks (sight of \(\frac{1}{2}n(n-1)\) with no working scores both marks) (ISW if correct expression incorrectly expanded)

Notes

Note: Rows are shown above, and they may be spread across multiple rows in the table. Each row ends when the appropriate value in column d is seen

c1M1: At least four rows of cells completed with a correct first and second row – condone repeated values in all columns or a single value in each row (Note SC accept Column B with 1, 2, 3, 4, 5, 6 with no empty cell between 1 and 2)

c1A1: CAO – the values in the third, fourth and fifth rows correct (accept either full recurring decimals or decimals consistently rounded to 3 significant figures)

c2A1: CAO - correct output following a correct seventh row (their output must be clearly indicated e.g. on the Output line or identified in or near the table) If a value is written on the output line, this takes precedence over the table.

Notes

d1B1ft: Follow through their answer to (c) provided that % error is < 0.1% (must be given to at least 3 significant figures) (condone missing %) (accept - 0.00832%) (if a numerical approximation to e is used, it must be given to at least 3 d.p. – so 2.718 or better) (accept \(8.32 \times 10^{-3}\)). If incorrect working is seen, even if followed by a correct answer, this is B0.

Note \(\dfrac{\left|\frac{1957}{720} - \mathrm{e}\right|}{\frac{1957}{720}} \times 100 = 0.00832\%\) scores B0

Notes

a1M1: First four items placed correctly (the boxed values) and at least eight values placed in bins – condone cumulative totals for M1 only

a1A1: First eight items placed correctly (the boxed and bold values)

a2A1: CSO (no additional/repeated values)

Notes

b1M1: First eight items placed correctly (the underlined values) and at least ten values placed in bins (no additional/repeated values) - condone cumulative totals for M1 only

b1A1: CSO

Notes

B1: CAO – clear indication that the 16 was not placed in Bin 1 accept sight of \(n \lt (17 + 8 + 16)\) or that the 4 was not placed in Bin 1 \(n \lt (17 + 8 + 12 + 4)\) and that Bin 2 contains a total of 40.

Notes

M1: Quick sort, pivot, p, chosen (must be choosing middle left or right – choosing first/last item as the pivot is M0). After the first pass the list must read (values greater than the pivot), pivot, (values less that the pivot). If only choosing one pivot per iteration then max of M1 only – Bubble sort is not a MR and scores M0 If they make a slip with one value (one slip, one missing or one extra) at the start they can score M1 A0 A1ft A0

A1: First two passes correct and pivots chosen for third pass

A1ft: Third and fourth passes correct (follow through from their second pass and choice of pivots – if an error oversimplifies so that after 3 passes all sublists are of length 1 A0)

A1: CSO (correct solution only – all previous marks in this part must have been awarded)

SC: If the list is sorted in ascending 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

Sort ascending for reference   Middle Right

Middle left

Notes

(c) NO MISREADS MARK EXACTLY TO THE SCHEME

M1: First 6 values placed correctly (the bold values) with at least 8 values placed in bins

A1: CSO so no additional/repeated values

Notes

B1: Correct reasoning for why 3 bins is not possible or at least 4 bins are required

Examples of B1:

• If \(x \gt 23\) then \(132 + x\) is at least 156 and \(\dfrac{156}{40} = 3.9\) so 3 is not possible
• The lower bound for the number of bins is \(\dfrac{156}{40} = 3.9\) so 3 is not possible
• If \(x = 24\) then \(\dfrac{156}{40} = 3.9\) so 3 is not possible (or comparing 156 with 120)
• If \(x \gt 23\) then \(132 + x\) is > 155 so you would need to have more than \(\dfrac{155}{40} = 3.875\) bins so is not possible (condone ‘at least’ rather than ‘more than’ on the bod so condone comparing 155 with 120)
• 4 values are at least half the capacity of a bin (or at least 20) and they are 20, 22, 23 and \(x\), so 3 so not possible (must explicitly state the four values but condone those candidates who imply that the 20, 22, 23 and the \(x\) are all greater than half the capacity of a bin)
• Comparing 132 with 120 and saying that 3 is not possible (no mention of \(x\) is required)
• \(x\) would have to be \(-12\) for it to be possible (but not just that \(x\) would have to be negative)

Notes

B1: One correct inequality (\(x \gt 23,\ x \geqslant 24,\ x \leqslant 28\) or \(x \lt 29\))

B1: CAO (\(23 \lt x \leqslant 28\) or \(24 \leqslant x \leqslant 28\) or 29 with a strict inequality)

Notes

(c) NO MISREADS MARK EXACTLY TO THE SCHEME – if \(x\) is given a value then M1 only

M1: First five values placed correctly (underlined values) and the \(x\) not in Bin 1 or 2 – at least eight values placed (condone cumulative values for M1 only)

A1: First eight values places correctly (underlined and boxed values with no repeated values)

A1: CSO no additional/repeated values

Notes

M1: Quick sort, pivot, p, chosen (must be choosing middle left or right – choosing first/last item as the pivot is M0). After the first pass the list must read (values greater than the pivot), pivot, (values less that the pivot). If only choosing one pivot per iteration then max of M1A1 only – Bubble sort is not a MR and scores M0

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 consistent pivots). They do not need to be choosing a pivot for the fifth pass for this mark. After their second pass their list must contain either 10, 11 or 12 numbers (so allow one additional or one missing number or a slip in one number e.g. the 5 becoming a 6)

A1: CSO (correct solution only – all previous marks in this part must have been awarded) – both middle left and middle right require six passes

SC: If the list is sorted in ascending 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

Ascending (below is middle-right for middle-left the pivot is the 23):

Middle left:

Notes

B1: any clear indication that as the 15 does not fit in Bin 1 then \(x + 15 \gt 40\) (condone for this mark just stating \(x \gt 25\)) or any clear indication that as the 13 does not fit in Bin 1 then \(x + 13 \gt 40\) (condone for this mark just stating that \(x \gt 27\))

dB1: correct answer of \(x = 28\) – this mark is dependent on the previous B mark and the correct upper bound of 28 in (b) (so if \(x = 28\) stated with no justification then no marks). As a minimum accept \(x + 13 \gt 40\) therefore \(x \gt 27\) so \(x = 28\) (just ‘\(x \gt 27\) so \(x = 28\)’ scores B1 B0 unless explicit mention of where \(x \gt 27\) has come from)

SC in (e): if B0B0 then award B1B0 for the first 7 values placed correctly in bins just once (ignore the other values)

Notes

In (a) it is important that all values at each node are checked very carefully – the order of the working values must be correct for the corresponding A mark to be awarded e.g. at D the working values must be 41 38 in that order (so 38 41 is incorrect)
It is also important that the order of labelling is checked carefully – some candidates start with a label of 0 at A (rather than 1) – which is fine. Also the order of labelling must be a strictly increasing sequence – so 1, 2, 3, 3, 4, … will be penalised once (see notes below) but 1, 2, 3, 5, 6, … is fine. Errors in the final values and working values are penalised before errors in the order of labelling

M1: A larger value replaced by a smaller value in the working values at two of C or D or E or F or G or H or J

A1: All values in A, B, C and D correct. Condone lack of 0 in A’s working value

A1: All values G, E and H correct and the working values in the correct order. Penalise order of labelling only once per question (G, E and H must be labelled in that order and G must be labelled after A, B, C and D). Note that an additional working value of 80 at E after the 61 is not an error so 65 61 80 is fine, however, any other number or e.g. 80 65 61 in this order is incorrect and scores A0 in this part

A1ft: All values in F and J correct on the follow through and the working values in the correct order. Penalise order of labelling only once per question.

To follow through F check that the working values at F follow from the candidate’s final values for the nodes that are directly attached to F (which are C, D, G and H). For example, if correct then the order of labelling of nodes C, D, G and H are 3, 4, 5 and 7 respectively so the working values at F should come from C, D, G and H in that order. The first working value at F should be their 31 (the Final value at C) + 43 (the weight of the arc CF), the second working value at F should be their 38 (the Final value at D) + 34 (the weight of the arc DF), the third working value at F should be their 59 (the Final value at G) + 11 (the weight of the arc GF), the fourth working value need not be there (as 68 + 22 > 70) but do not penalise if seen. Repeat the process for J (which will have working values from E and H with the order of these nodes determined by the candidate’s order of labelling at E and H)

A1: CAO - correct path from A to J (ABCEHJ) and not the path from J to A

A1ft: ft their final value at J only (if 100 stated and 100 is not the final value at J then A0)

Notes

M1: Complete, correct method – allow reciprocal e.g. \(0.0312 \times \left(\dfrac{9}{9000}\right)^2\) – allow slips in values only e.g. 0.312 for 0.0312. If using anything other than squared e.g. \(n^3\) then M0. The correct answer in seconds, minutes or hours (8 hours 40 minutes) implies this mark (and if in minutes implies the A mark too)

A1: CAO – the exact value of 520 must be stated at some point (as question specifically asked for the answer in minutes) – condone lack of units (but if present must be correct)

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

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

Notes

(c) B1: cao (45)

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.

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\).]

Notes

(a) M1: Attempt to find the lower bound \((37.5 \pm 6.1)/10\) (a value of 3.75 seen with no working can imply this mark)

A1: cso – a lower bound of 4 with either a correct calculation seen or 3.75 or ‘total is 37.5 and if each ball contains 10 this gives a lower bound of 4’. An answer of 4 with no working (or from part (b)) scores M0A0. Any incorrect working loses this mark e.g. a correct calculation followed by an incorrect value followed by 4 is A0

Notes

(b) M1: First four items placed correctly and at least eight items placed in bins – condone cumulative totals for M1 only (the boxed values)

A1: First eight items placed correctly (the boxed and bold values), and all eleven correct values only placed in bins (so no additional/repeated values)

A1: cso (no additional/repeated values)

Condone working in cm provided consistent

No MR in this question – mark according to the scheme

Notes

In (a) it is important that all values at each node are checked very carefully – the order of the working values must be correct for the corresponding A mark to be awarded e.g. at H the working values must be 129 118 112 in that order (so 129 112 118 is incorrect)

It is also important that the order of labelling is checked carefully – some candidates start with a label of 0 at A (rather than 1) – which is fine. Also the order of labelling must be a strictly increasing sequence – so 1, 2, 3, 3, 4, … will be penalised once (see notes below) but 1, 2, 3, 5, 6, … is fine. Errors in the final values and working values are penalised before errors in the order of labelling

(a) M1: A larger value replaced by a smaller value in at least two of the working boxes at either D or F or G or H

A1: All values in A, B, C and E correct. Condone lack of 0 in A’s working value

A1: All values D and F correct and the working values in the correct order. Penalise order of labelling only once per question (D and F must be labelled in that order and D must be labelled after A, B, C and E)

A1ft: All values in G and H correct on the follow through and the working values in the correct order. Penalise order of labelling only once per question. To follow through G check that the working value at G follows from the candidate’s final values from their feeds into G (which will most likely come from nodes C, D and/or F (in the order in which the candidate has labelled them)) and that the final value, and order of labelling, follows through correctly. Repeat this process for H (which will possibly have working values from C, F and/or G with the order of these values determined by the candidate’s order of labelling at C, F and G)

A1: cao - correct path from A to H (ABEFGH)

A1ft: Follow through their final value at H only (if 112 stated and 112 is not the final value at H then A0)

Notes

(b) B1: Any indication that repeated application of Dijkstra has cubic order

M1: Complete method – allow 10/200 – allow slips in values e.g. 0.82 for 0.082 and accept 200/10 (or 10/200) either squared or cubed only

A1: cao

Notes

(c) B1: Any indication that the run-time is not exactly proportional to \(n^3\) e.g., may suggest that there are other terms (\(n^3 + \ldots\)), or that \(n^3\) is the dominant term, or that order does not imply proportionality. Do not accept only that ‘\(n^3\) is not exact’. Condone use of \(n^2\) (oe) for \(n^3\)

Notes

(a) M1: Quick sort, pivot, p, chosen (must be choosing middle left or right – choosing first/last item as the pivot is M0). After the first pass the list must read (values greater than the pivot), pivot, (values less that the pivot). If only choosing one pivot per iteration then max of M1 only – Bubble sort is not a MR and scores M0

A1: First pass correct and next pivots chosen correctly for the second pass (but the second pass does not need to be correct)

A1ft: Second and third passes correct (follow through from their first pass and choice of pivots). They do not need to be choosing a pivot for the fourth pass for this mark

A1: cso (correct solution only – all previous marks in this part must have been awarded) including ‘sort complete’ statement

If list sorted into ascending order then mark as a MR

Middle left pivot(s)

Therefore, the sort is complete

Notes

(b) B1: Correct reasoning why \(n \leqslant 46\) or \(n \lt 47\) or \(n \leqslant 45\) or \(n \lt 46\) - condone an argument which is mathematical in nature only e.g., \(n \lt 30 + 12 + 5\) or \(n \lt 5 + 23 + 18\)

B1: Correct reasoning why \(n \geqslant 44\) - condone ‘largest bin filled is 44 so \(n \geqslant 44\)’ or other similar mathematical argument. This mark can be awarded for an argument which is mathematical in nature only e.g., \(n \geqslant 30 + 12 + 2\)

B1: Completely correct reasoning for why n is either 44 or 45 only – this mark is dependent on the two previous B marks and must give sufficient detail (so an argument that contains no clear explanation of why certain inequalities hold cannot score this mark)

Notes

No MR or follow through in this part

(c) M1: First five values placed correctly - with at least eight values placed (the squared values)

A1: First eight values places correctly with no additional/repeated values (the squared and underlined values)

A1: cso - no additional/repeated values

Notes

(a) B1: Correct reasoning of why \(x \gt 13\) accept \(x \gt 50 - (19 + 18)\)

B1: Correct explanation of why \(x \leqslant 21\) accept \(x \leqslant 50 - (19 + 10)\)

B1: Correct deduction that \(13 \lt x \lt 21\) must mention that the numbers are distinct (oe)

Notes

(b) B1: Use first complete pass to deduce that \(x \lt 17\)

B1: Correct lower bound of \(x \gt 13\)

Notes

(c) M1: Using first-fit decreasing in an attempt to derive new upper bound for \(x\) (so either for stating both \(x\) could equal 14 or 15, \(x \leqslant 15\) or \(x \lt 15\))

A1: Correct deduction that \(x = 14\) (must clearly state or imply that Bin 2 is full)

Notes

PLEASE NOTE NO MISREADS IN PARTS (a) and (b) – MARK ACCORDING TO THE SCHEME AND THE SPECIAL CASE FOR ASCENDING ORDER IN (b)

(a) M1: First six items placed correctly and at least eight values placed in bins - condone cumulative totals for M1 only (the underlined values)

A1: CSO – all correct (so no additional/repeated values)

Notes

(b) M1: Quick sort, pivot, p, chosen (must be choosing middle left or right – choosing first/last item as the pivot is M0). After the first pass the list must read (values greater than the pivot), pivot, (values less that the pivot). If only choosing one pivot per iteration then max of M1A1 only – Bubble sort is not a MR and scores M0

A1: First pass correct and next pivots chosen correctly for the second pass (but the second pass does not need to be correct) – so they must be choosing (if middle right) a pivot value of 3.2 for the second pass or (if middle left) a pivot value of 1.9

A1ft: Second and third passes correct (follow through from their first pass and choice of pivots). They do not need to be choosing a pivot for the fourth pass for this mark

A1: CSO (correct solution only – all previous marks in this part must have been awarded) including if middle right a fifth pass with the 1.5 used as a pivot or if middle left a fourth pass with the 1.7 used as a pivot

Sorting list into ascending order in (b)

• If the candidate sorts the list into ascending order and reverses the list in this part then this can score full marks in (b)
• If the list is not reversed in (b) then remove the last two A marks earned in (b). If the candidate says that the list needs reversing in (b) but does not actually show the reversed list in (b) then remove the last A mark earned
• Note that if sorting into ascending order then a ‘sort complete’ statement is required – this could be shown by the final list being re-written or ‘sorted’ statement or each item being used as a pivot (which would therefore mean that the final list would have been written twice) BEFORE list is reversed

Middle left

Middle right ascending (which requires a ‘sort complete’ statement – see above)

Middle left ascending (which required a ‘sort complete’ statement – see above)

Notes

(c) M1: Complete correct method – allow reciprocal – allow slips in values only e.g. 1250 for 11 250

A1: CAO – the exact value of 88.6 must be stated at some point (as question specifically asked for the answer to the nearest tenth of a second) – isw if 90 follows 88.6 seen. 90 with no working scores no marks. An answer of 88.6 with no working scores M1A0 – condone lack of units (but if present must be correct)

Notes

PLEASE NOTE NO MISREADS IN THIS QUESTION – MARK ACCORDING TO THE SCHEME AND THE SPECIAL CASES IN PARTS (c) AND (d)

a1M1: Attempt to find the lower bound \((204 \pm 40) / 50\) (a value of 4.08 seen with no working can imply this mark)

a1A1: CSO - correct calculation seen or 4.08 followed by 5 (containers) – accept 4.1 followed by 5 if correct calculation seen. An answer of 5 with no working scores M0A0

Notes

b1M1: First five items placed correctly and at least eight values placed in containers. Condone cumulative totals for M1 only (the values in bold)

b1A1: CSO (correct solution only – so no additional/repeated values)

Notes

c1M1: Quick sort – pivot, \(p\), chosen (must be choosing middle left or middle right – choosing first/last item as pivot is M0). After the first pass the list must read (values greater than the pivot), pivot, (values less that the pivot). If only choosing one pivot per iteration then M1 only – bubble sort is not a MR and scores M1 only for 25  32  16  17  23  18  12  9  8  40  4

c1A1: First two passes correct and next pivots chosen correctly for third pass (but third pass does not need to be correct) – so they must be choosing (if middle right) pivot value of 12 or (if middle left) pivot value of 17

c2A1ft: Third and fourth passes correct (follow through from their second pass and choice of pivots). They do not need to be choosing a pivot for the fifth pass for this mark

c3A1: CSO (correct solution only – all previous marks in this part must have been awarded) - if middle right then a fifth pass in which the 8 is used as a pivot must be included or if middle left then a fifth pass in which the 4 is used as a pivot and a sixth pass in which the 9 is used as a pivot must be included

SC for (c): If using an incorrect list from the start of (c) with only one error (an error is either one missing number, one extra number, one incorrect number or one number incorrectly placed) then the most they can score is M1A0A1ftA0

Sorting list into ascending order in (c)

• If the candidate sorts the list into ascending order and reverses the list in this part then this can score full marks in (c)
• If the list is not reversed in (c) then remove the last two A marks earned in (c). If the list is reversed at the start of (d) but not in (c) then still remove the last two A marks earned in (c). If the list is in ascending order in (c) award no marks for first-fit increasing in (d). If the candidate says that the list needs reversing in (c) but does not actually show the reversed list in (c) then remove the last A mark earned

Notes

d1M1: Must be using the correct sorted list in descending order. First five items placed correctly and at least eight values placed in bins – condone cumulative totals for M1 only (the bold values)

d1A1: First seven items placed correctly (the underlined and bold values)

d2A1: CSO (so no additional/repeated values)

SC for (d) – if ‘sorted’ list is incorrect from part (c) and M0 would be awarded in (d) then award M1 only in (d) for their first eight items correctly placed – by ‘incorrect’ they can have only one ‘error’- an ‘error’ is one missing number, one extra number, one incorrect number or one number incorrectly placed. Allow full marks in (d) if a correct list is used in (d) even if the list is incorrect at the end of (c). Please note that if ‘sorted’ list is incorrect in (c) and it is clear that this has been used from their working in (d) then please award at most M1 in (d)

Notes

e1B1: \(132 + 2x\) (oe)

e1M1: \(((132 \pm 15) + 2x) / 50\) ‘equated’ to their 3 or their 4 (that is 1 or 2 less than the lower bound stated in (a))

e1A1: Either 9 or 34 correctly found

e2A1: \(9 \lt x \leqslant 34\) as a final answer (do not isw incorrect ‘simplification’)

Notes

a1M1: Comparing first value with second value, swap if second is larger (oe) – must be clear that the first value in the list is being compared with the second value in the list and swapping if the second is larger than the first (oe)

a1A1: Compare second with third, (and then third with fourth), and so on until the end (or 9^th item) of the list – must be clear that after the first comparison the second value in the list is compared with the third value and so on until the end of the list

Notes

b1B1: CAO (for left to right) – must mention either the smallest (oe) or the 15 should be at the end of the list/correct position (bod if 15 is mentioned (but not incorrectly))

b2B1: CAO (for right to left) – must mention either the largest (oe) or the 35 should be at the end of the list/correct position (bod if 35 is mentioned (but not incorrectly))

Notes

c1B1: CAO (27) – B0 if choice of answers

Notes

d1M1: Quick sort – 33 and 21 selected as pivots and after their first pass the sublists must read (values greater than the pivot), pivot, (values less than the pivot)

d1A1: The first ‘two’ passes correct – they do not need to be selecting a pivot for the ‘third’ pass

d2A1: CSO (correct solution only) – must include a ‘third’ pass in which the 19 (or 20 if middle left) is used as a pivot – a ‘sort complete’ statement is not required (as their third pass contains no swaps)

In (d) sorting list into ascending order is M0 but allow recovery in (e) if first-fit decreasing

Middle left for (d)

Notes

e1M1: 35 in Bin 1, Bin 2 correct and 30 in Bin 3 (so first 4 values correctly placed) – no follow through on an incorrect list from (d) – condone cumulative totals for M1 only (the boxed values)

e1A1: First 7 values correctly placed (the boxed and underlined values)

e2A1: CSO (so no additional/repeated values)

Notes

f1B1: CSO – therefore correct calculation (e.g. 242/4 = 60.5) + conclusion (oe i.e. an argument based on wastage e.g. there is only room for a tenth value of at most 16)

Notes

a1M1: First five items placed correctly and at least eight values placed in bins - condone cumulative totals for M1 only (the boxed values)

a1A1: First eight items placed correctly (the boxed and underlined values)

a2A1: CSO (so no additional/repeated values)

• If the candidate has misread a number at the start of (a), so genuinely miscopy a number then mark the whole of (a), (b) and (c) as a misread – removing the last two A marks earned. This gives a maximum of 8 marks in total for these three parts
• If they have used the correct numbers at any point in (a) and then use an incorrect number in (b) (say 24 instead of 42) from the beginning of the sort or misread one of their own numbers during (b) then count it as one ‘error’ in (b) (so they will lose at least the final A mark in (b) but should be able to gain at least the M mark and the follow through A mark) – then mark (c) according to the SC above. More than one ‘error’ in (b) loses all subsequent A marks in (b)

Notes

b1M1: Quick sort, pivot, p, chosen (must be choosing middle left or right – choosing first/last item as the pivot is M0). After the first pass the list must read (values greater than the pivot), pivot, (values less that the pivot). If only choosing one pivot per iteration then M1 only – Bubble sort is not a MR and scores M1 only for 42  21  16  35  15  31  11  27  39  10 (for left to right) or 42  39  21  15  16  35  10  31  11  27 (for right to left)

b1A1: First two passes correct and next pivots chosen correctly for the third pass (but the third pass does not need to be correct) – so they must be choosing (if middle right) pivot values of 39 and 31 for the third pass or (if middle left) a pivot value of 16

b2A1ft: Third and fourth passes correct (follow through from their second pass and choice of pivots). They do not need to be choosing a pivot for the fifth pass for this mark

b3A1: CSO (correct solution only – all previous marks in this part must have been awarded) including a fifth pass in which the 27 and 11 (if middle right) or 21 (if middle left) is used as a pivot and a ‘sort complete’ - this could be shown by the final list being re-written or ‘sorted’ statement or each item being used as a pivot (which would therefore mean that the final list would have been written twice)

• If the candidate sorts the list into ascending order and reverses the list in this part then this can score full marks in (b)
• If the list is not reversed in (b) then mark as a misread (so remove the last two A marks earned in (b)). If the list is reversed at the start of (c) but not in (b) then still treat this as a misread. If the list is in ascending order in (b) award no marks for first-fit increasing in (c). If the candidate says that the list needs reversing in (b) but does not actually show the reversed list in (b) then remove the final A mark

Middle left for (b)

Ascending middle right

Ascending middle left

Notes

c1M1: Must be using ‘sorted’ list in descending order. First five items placed correctly and at least eight values placed in bins – condone cumulative totals for M1 only (the boxed values)

c1A1: First eight items placed correctly (the underlined and boxed values)

c2A1: CSO (so no additional/repeated values)

Notes

d1B1: Any inequality in \(x\) linked with either 14 or 17 (allow in words or using set notation) or an indication of an interval with 14 and 17 but with no inequality sign (or even \(x\)) present

d2B1: Any inequality in \(x\) linked with 14 and 17 (allow in words) or using set notation (14, 17)

d3B1: CAO (allow as two separate inequalities: \(x \gt 14,\ x \lt 17\) (allow without a comma separating the two inequalities), accept \(x \gt 14\) and \(x \lt 17\) but not \(x \gt 14\) or \(x \lt 17\)) - if defined using words only then do not award this mark

Notes

a1M1: At least three rows of cells in columns \(x\), \(y\) and \(t\) completed with a correct first row (so 26 for \(x\) and 5 for \(t\))

a1A1: CAO – second and third rows correct (for just the columns in \(x\), \(y\) and \(t\))

a2A1: CAO – fourth, fifth and sixth rows correct (for just the columns in \(x\), \(y\) and \(t\))

a3A1: CSO – including the output of 135 either on the given line in the answer book or clearly stated in the table but it must be absolutely clear that the output is the final \(t\) value (no bod). Furthermore, all ‘yes’ and ‘no’ comments must be present in the 4^th and 5^th columns with no additional/incorrect ‘yes’ or ‘no’

Notes

bi1B1: \(x\) must be 122 and any attempt at a reason

bi2DB1: Dependent on previous B mark (so B0B1 is not possible) – 122 and a correct valid reason – e.g. \(x\) must be an integer/whole number or ½ is not odd or even or if you input ½ then you can never get to \(x = 0\) when halving, etc. Just saying that the algorithm ‘won’t work’ or that the algorithm ‘will get stuck in a loop’ or ‘not terminate’ is not sufficient for this second mark neither is the argument of subtracting 1 from a ½. It must be clear why the algorithm won’t output a value for \(t\) with \(x = \frac{1}{2}\) - so essentially there needs to be some indication of why \(x\) will never become 0. Furthermore, just saying that \(x\) will never reach 0 is insufficient – we need an indication of why \(x = 0\) is not possible with a starting value of \(x = \frac{1}{2}\)

bii3B1: CAO

Notes

a1M1: Quick sort, pivot, p, chosen (must be choosing middle left or right – choosing first/last item as pivot is M0) . After the first pass the list must read (values greater than the pivot), pivot, (values less than the pivot). If only choosing one pivot per iteration then M1 only – Bubble sort is not a MR and scores M1 only for 59  45  55  47  18  63  17  15  42  11 (for left to right) or 63  59  45  18  55  47  11  42  17  15 (for right to left)

a1A1: First two passes correct and next pivots chosen correctly for third pass (but third pass does not need to be correct) – so they must be choosing (if middle right) pivot values of 55 and 17 for the third pass or (if middle left) pivot values of 59 and 17

a2A1ft: Third and fourth passes correct (follow through from their second pass and choice of pivots). They do not need to be choosing a pivot for the fifth pass for this mark

a3A1: CSO (correct solution only – all previous marks in this part must have been awarded) including a fifth pass in which the 42 (if middle right) or 45 (if middle left) is used as a pivot (not just stated as a pivot)

Misreads

• If the candidate has misread a number at the start of (a), so genuinely miscopy a number then mark the whole question as a misread – removing the last two A marks earned. This gives a maximum of total of 7 marks
• If the candidate starts the sort with the correct numbers in (a) but they misread their own numbers (so they have a copying error) during the sort then count this as an error in (a) but mark (b) and (c) as a misread. If they restart in (b) and (c) with the correct list of numbers then this is fine for full marks

Sorting list into ascending order in (a)

• If the candidate sorts the list into ascending order and reverses the list in this part then this can score full marks in (a)
• If the list is not reversed in (a) then mark as a misread (so remove the last two A marks earned in (a)). If the list is reversed at the start of (b) but not in (a) then still treat this as a misread. If the list is in ascending order in (b) award no marks for first-fit increasing. If the candidate says that the list needs reversing in (a) but does not actually show the reversed list in (a) then remove the final A mark

For part (a) using middle left as pivot

Ascending (middle right)

Ascending (middle left)

Notes

b1M1: Must be using ‘sorted’ list in descending order. First five items placed correctly and at least eight values placed in bins – condone cumulative totals for M1 only (the underlined values)

b1A1: First eight items placed correctly (the underlined and boxed values)

b2A1: CSO

Notes

c1M1: Attempt to find lower bound \((372 \pm 63)/100\) (a value of 3.72 seen with no working can imply this mark) or any argument based on the four largest values

c1A1: CSO – correct calculation seen or 3.72 and a conclusion – accept ‘yes’ as a minimum conclusion – however, ‘4 is the optimal number of bins’ (or equivalent) with no reference to the solution in (b) is A0. For those using the four largest values argument they must clearly explain why two of these values cannot be placed in a bin e.g. the sum of any two of 63, 59, 55, 47 is greater than 100 so no two can be placed in a bin

Notes

a1M1: Quick sort, pivot, p, chosen (must be choosing middle left or right – choosing first/last item as pivot is M0) and first pass gives <p, p, >p. So after the first pass the list should read (values less than the pivot), pivot, (values greater than the pivot). If only choosing one pivot per iteration M1 only

a1A1: First pass correct and next pivot(s) chosen correctly for second pass (but second pass does not need to be correct)

a2A1ft: Second and third passes correct (follow through from their first pass and choice of pivots) – and next pivot(s) chosen correctly for the fourth pass

a3A1: CSO (correct solution only – all previous marks in this part must have been awarded) including ‘sort complete’ – this could be shown by the final list being re-written or ‘sorted’ statement or each item being used as a pivot

Sorting list into descending order in either (a) and/or (b)

• If the candidate sorts the list into descending order and reverses the list then they can score full marks
• If the list is not reversed then mark as a misread (so remove the last two A marks earned). If the candidate says that the list needs reversing but doesn’t actually show the reversed list then remove the final A mark earned

Using middle left quick sort in (a)

(note: for full marks must identify 24 as a pivot but no sort complete statement required as pivoting on the 24 produces no further swaps)

Notes

b1M1: Bubble sort. Consistent direction, end number (greatest/least) in place. Do check these carefully as some candidates show the result of each comparison and swap in the first pass

b1A1: First and second passes correct – so end two numbers in place

b2A1ft: Third and fourth passes correct following through from the candidate’s second pass

b3A1: CSO (correct solution only) – including either a ‘sort complete’ statement or final list rewritten/sixth pass

Right to left bubble sort in (b)

Notes

c1M1: Choosing middle right pivot (choosing middle left is M0) + discarding/retaining half the list. So 53 (the 11th value) found as a pivot and either rejecting the first 11or 10 values or retaining the final 9 or 10 values

c1A1: First and second passes correct i.e. 53 found and either using 67 to 91 in 2nd pass or discarding 9 to 53 (so therefore no ‘sticky’ pivots in the first two passes — sticky is when the pivot is retained in the next pass). Then 77 found and either using 67 to 75 in 3rd pass or discarding 77 to 91

c2A1: CSO - search complete + ‘found’ (accept ‘found’, ‘located’, ‘stop’, etc. but not just, for example, the number underlined; must be convinced that 68 has been located and is not a pivot or a number in a sublist with only one value)

Notes

a1M1: First four items placed correctly in bins 1, 2 and 3. (Condone cumulative totals here only.)

a1A1: First eight terms placed correctly.

a2A1: CSO – all correct.

Notes

b1M1: Quick sort – pivots, p, selected and first pass gives <p, p, >p. If only choosing one pivot per iteration M1 only.

b1A1: First pass correct, next two pivots chosen correctly for second pass.

b2A1ft: Second and third passes correct (follow through from their first pass and choice of pivots) – and net pivot(s) chosen consistently for fourth pass.

b3A1: CSO including choice of pivots for the fifth pass and ‘sort complete’ – this could be shown either by a ‘stop’ statement or final list being re-written or using each item as a pivot.

Sorting list into ascending order in (b)

• If the candidate sorts the list into ascending order and reverse the list in (b) then they can score full marks in (b).
• If the list is not reversed in (b) then mark as a misread (so remove the last two A marks earned in (b)). If the list is reversed at the start of (c) but not in (b) then still treat this as a misread. If the list is still in ascending order in (c) award no marks for first fit increasing. If the candidate says that the list needs reversing in (b) but doesn’t actually show the reversed list in (b) then remove the final A mark in (b).

Misreads

• If they have misread a number at the start of (a), so genuinely miscopied a number (before starting the question) then please mark the whole question as a misread (so remove the final two A/B marks earned).
• If they make an error during the quick sort then mark this as an error. They can still earn the M mark in (c) (see SC in (c)).

Middle left

Ascending order (middle right)

Ascending order (middle left)

Notes

c1M1: Must be using list in descending order (independent of (b)). First seven terms placed correctly.

c1A1: CAO

SC for (c): if the ‘sorted’ list they use in (c) has one ‘error’ from (b) (e.g. a missing number, an extra number or one number incorrectly placed) then M1 only can be awarded in (c) (for the first seven items). If there is more than one ‘error’ then M0. Allow full marks in (c) if a correct list is used in (c) even if the list is incorrect at the end of (b).

Notes

d1M1: E.g. Attempt to find lower bound \((265 \pm 47)/60\), (oe) could remark on number of items \(>30\). The argument must be numerical in nature.

d1A1: CSO including 5.

Notes

a1M1 First four items placed correctly and at least six values put in bins (so bin 1 correct and the \(x\) in bin 2). If a candidate gives \(x\) a value in the given interval then allow this for the M mark in (a) only.

a1A1 First seven items placed correctly (so bins 1 and 2 correct and 25 in bin 3)

a2A1 cso – all correct

Notes

b1M1 Quick sort, pivot, p, chosen (must be choosing middle left or right – choosing first/last item as pivot is M0) and first pass gives >p, p, <p. So after the first pass the list should read (values greater than the pivot), pivot, (values less than the pivot). If only choosing one pivot per iteration M1 only

b1A1 First pass correct, next two pivots chosen correctly for second pass. If a candidate gives \(x\) a value in the given interval then allow this for the M mark and first A mark only in (b).

b2A1ft Second and third passes correct (follow through from their first pass and choice of pivots) – need not be choosing pivot(s) for the fourth pass for this mark.

b3A1 CSO (correct solution only- all previous marks in this part must have been awarded) including choice of pivots for the fifth pass and ‘sort complete’ – this could be shown either by a ‘stop’ statement or final list being re-written or using each item as a pivot.

Part (b) Using middle left as pivot

Misreads

• If they have used the correct numbers at any point in part (a) and then use incorrect numbers in part (b) (say 71 instead of 17) from the beginning of the sort or misread their own numbers during part (b) then count it as an error in part (b) (so they will lose at least the final A mark but should be able to gain at least the M mark and ft A mark) – then mark part (c) according to the SC above.

Sorting list into ascending order in (b)

• If the candidate sorts the list into ascending order and reverse the list in part (b) then they can score full marks in (b).
• If the list is not reversed in part (b) then mark as a misread (so remove the last two A marks if earned in (b)). If the list is reversed at the start of (c) but not in (b) then still treat this as a misread. If the list is still in ascending order in part (c) award no marks for first fit increasing. If the candidate says that the list needs reversing in part (b) but doesn’t actually show the reversed list in (b) then remove the final A mark in (b).

Ascending (middle left)

Ascending (middle right)