Notes, worked examples and practice for this topic are being written by our tutors. The past-paper questions below are ready now: work each one on paper, then open the mark scheme and the examiner's comment.
Tap a question to zoom it. Mark scheme and examiner's comment open under each question.
June 2025 · AS Paper 2 (Decision 1) · Q1(a)3 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This was a very accessible opener, with a significant number of learners scoring full marks, however a surprising number of learners did not score highly being full marks despite it being a very accessible question. Part a) was generally answered very well with a majority of learners scoring at least two out of the three available marks, and most securing full marks. Very few descending sorts or quick sorts were seen, and most were able to show just the final results of each pass rather than every comparison. A small group of learners chose to write out every swap, and not just the result at the end of the pass, which was very time consuming for them on an already tightly timed paper. It was most common to just stop after the 5th pass, with no 6th pass or “sort complete” statement made. Some learners used a more unusual “cross arrow” notation, where learners were trying to show all the swaps that took place in a single line – this was confusing to follow and more often than not led to a mistake in one of the passes. Part b) saw a number of learners use Kruskal’s or a version of the nearest neighbour algorithm, or considering and rejecting arcs in a hybrid version of Prim’s and Kruskal’s. Several learners chose to draw the distance matrix in order to perform Prim’s, which was an unnecessary use of their time. The third arc dictated whether a candidate had correctly used Prim’s, and therefore if the wrong algorithm was used, the candidate lost both the method and the accuracy mark. Nonetheless a majority scored all marks here. Part c) provided easy marks for those who had correctly used Prim’s in part b), but also the opportunity for full marks even if Kruskal’s had been used in part b). There were a few errors in adding up the arc lengths, with a variety of total lengths in the range 85-89. Almost all learners who had a correct MST in b) also scored the two marks in c), and thus a large majority scored both of these marks).
Key points from the mark scheme and examiner's report
bubble sort from the left, ascending: give only the list after each pass
30 in place after pass 1
must state "sort complete" or show a final pass with no swaps (often omitted)
writing every swap wastes time
June 2025 · AS Paper 2 (Decision 1) · Q3(a)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Part (a) was generally well answered with the majority of learners knowing that the graph was semi-Eulerian. As the mark scheme did not insist on the work “exactly”, many learners were able to secure this first mark. Learners were able to give a clear textbook definition or state that nodes D and G were odd. Very few gave an incorrect answer or did not give a reason. Part b) was a standard application of Dijkstra’s algorithm and many learners scored full marks; getting the correct quickest path and shortest time. A few learners did not show regard for the order of working values and were penalised heavily for this, but generally the majority scored highly. If mistakes were made, this was most common with the working values at D (missing 18), H (missing 26) or F (additional values). Other marks lost came from errors in the order of labelling, or missing values, although very few learners required the follow through mark and the path and length were generally correct, even with errors on the diagram.
Key points from the mark scheme and examiner's report
semi-Eulerian: exactly two odd vertices (D and G)
June 2025 · Paper 3D (Decision 1) · Q1(a)3 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
common mistakes in part (a) relating to missing out a value from the list or transcription errors. A common mistake in part (b) was to misplace the final three items: 2.9, 2.8 and 1.4 with
Key points from the mark scheme and examiner's report
first fit: 4.7 2.9 1.4 2.8
5.5 5.8
3.8 6.5
5.1 6.3
4.1
check every bin from the first
omitted or mis-copied values were common
June 2025 · Paper 3D (Decision 1) · Q1(b)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
A common mistake in part (b) was to misplace the final three items: 2.9, 2.8 and 1.4 with several candidates not realising there was space for 1.4 in Bin 2. Another common error was to misread 4.7 and 4.1. A small number of candidates found it challenging to reorder the given list before applying the first fit decreasing algorithm, with a few using a sorting algorithm to achieve this. Candidates should be reminded that, unless explicitly asked to use a sorting algorithm, this is not necessary. A small number of candidates attempted to use first fit increasing to place the items in part (b), which was a clear error.
Key points from the mark scheme and examiner's report
first-fit decreasing: 6.5 6.3
5.8 5.5 1.4
5.1 4.7 2.9
4.1 3.8 2.8
1.4 fits in bin 2
reorder by inspection (no sort algorithm needed)
4.7 and 4.1 misread
June 2025 · Paper 3D (Decision 1) · Q2(a)4 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
The quick sort proved a very accessible question with a large number of candidates performing an entirely correct sort. Candidates demonstrated a consistent approach to picking pivots, whether middle right or middle left, and generally recognised the need to perform iterations until only single-item sublists remained. A small number of candidates were inconsistent with their treatment of single-item sublists, choosing some as pivots but others not, and candidates should be reminded that a consistent approach in all algorithms is a key aspect of good practice in Decision Mathematics. As always, a minority of candidates sorted into ascending rather than descending order and this limited the number of marks available for their response.
Key points from the mark scheme and examiner's report
quick sort into descending order with consistent middle pivots
keep 028 as written
pivot every single-item sub-list consistently
ascending order limits the marks
June 2025 · Paper 3D (Decision 1) · Q2(b)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Part (b) proved more challenging. A significant number of candidates had memorised the number of comparisons in the worst-case for bubble sort and quoted a correct result. Candidates should be reminded that Decision Mathematics is a ‘methods’ paper and therefore quoting results may not result in full credit (although this was condoned for this series) Candidates generally understood the need to consider the number of comparisons in each pass, although a common error was to start with n comparisons in the first pass rather than n -1. Other common mistakes included multiplying rather than summing the comparisons from each pass, or not reducing the number of comparisons after each pass.
Key points from the mark scheme and examiner's report
worst case (n − 1) + (n − 2) + … + 1 = ½n(n − 1)
starting with n comparisons or multiplying instead of summing were common errors
June 2025 · Paper 3D (Decision 1) · Q2(c)3 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Part (c) had a variety of approaches seen, with most candidates electing to start a new row in the table when a value was updated. The instruction “show the results obtained at each step of the algorithm” does not require candidates to use a new row for each step, although this is a valid alternative. In all cases, the table should be completed in “reading order”, that is from left to right and top to bottom, such that the algorithm can be traced by reading the table. A common error, not penalised in this series, was to write the values for b one row higher than expected. As this did not alter the accuracy of the final output, this was condoned, and a significant number of candidates had this approach. 2 for 𝑑𝑑 rather than 3 5 2, and Common mistakes in applying the algorithm were achieving terminating the algorithm one iteration too soon. Candidates worked with both fractions and decimals in this question, where candidates who worked with decimals occasionally made rounding errors. Part (d) was not always completed by candidates who achieved an output from part (c), and a surprisingly large number of candidates rounded to 3 decimal places rather than 3 significant figures. A small number of candidates used the output as their ‘true’ value when calculating the percentage error, which is an incorrect method and did not gain credit.
Key points from the mark scheme and examiner's report
trace the algorithm: d = 1, 2, 5/2, 8/3, 65/24, 163/60, 1957/720
output 1957/720 = 2.71806 (2.72 to 3 s.f.)
stopping one iteration early was common
June 2025 · Paper 3D (Decision 1) · Q2(d)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Part (d) was not always completed by candidates who achieved an output from part (c), and a surprisingly large number of candidates rounded to 3 decimal places rather than 3 significant figures. A small number of candidates used the output as their ‘true’ value when calculating the percentage error, which is an incorrect method and did not gain credit.
Key points from the mark scheme and examiner's report
(1957/720 − e)/e × 100 = 0.00832%
0.0632% if 2.72 used
June 2024 · AS Paper 2 (Decision 1) · Q1(a)3 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This was generally a very accessible start to the paper and the majority of candidates scored highly overall. In part a) the candidates performed the quick sort algorithm efficiently and the majority scored full marks. There were few attempts at middle left pivot seen but, where seen, these were performed equally well. Common mistakes were to use a mixture of middle left and middle right pivots, or to ‘move’ the 4.5 too far on the second pass and then pivot on it. Both errors lost the second and third mark. Scores of 110 were seldom seen – candidates who completed the first three passes usually completed the sort. As always, a small number of candidates sorted the list into ascending order (then reversing their list in many cases) but this was heavily penalised, as were errors in ordering either side of the pivot. In part b) the first-fit decreasing algorithm was generally performed well, with scores of 2 and 3 out of 3 being extremely common. The most common mistakes here were with the 1.3 or 1, which lost the final A mark only. A small minority of candidates attempted full bin method, although a surprising number attempted first-fit increasing (including those who had sorted into descending order). Part c) was again generally well-attempted, with the most common reason for losing the A mark being simply an incorrect packing from part b). There were a reasonable number of candidates who divided their sum of weights by 11 rather than 10, demonstrating a misconception with the lower bound calculation. A very small number of candidates stated that n-1/2 or n+1/2 gave the minimum number of bins, which is an entirely false statement. Finally, part d) was generally well answered with candidates able to describe that 1.6 should be the penultimate number in the list, but very few appreciated that the sort could have been carried out from right to left, as opposed to left to right. Several candidates focused on the larger values in the list, which didn’t result in thorough enough reasoning, and a small group of candidates
Key points from the mark scheme and examiner's report
descending order: values greater than the pivot first
consistent middle right (or left) pivots, several per pass
mixing left and right pivots or moving 4.5 too far on pass two lost two marks
sorting ascending then reversing heavily penalised
June 2024 · AS Paper 2 (Decision 1) · Q1(b)3 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This was generally a very accessible start to the paper and the majority of candidates scored highly overall. In part a) the candidates performed the quick sort algorithm efficiently and the majority scored full marks. There were few attempts at middle left pivot seen but, where seen, these were performed equally well. Common mistakes were to use a mixture of middle left and middle right pivots, or to ‘move’ the 4.5 too far on the second pass and then pivot on it. Both errors lost the second and third mark. Scores of 110 were seldom seen – candidates who completed the first three passes usually completed the sort. As always, a small number of candidates sorted the list into ascending order (then reversing their list in many cases) but this was heavily penalised, as were errors in ordering either side of the pivot. In part b) the first-fit decreasing algorithm was generally performed well, with scores of 2 and 3 out of 3 being extremely common. The most common mistakes here were with the 1.3 or 1, which lost the final A mark only. A small minority of candidates attempted full bin method, although a surprising number attempted first-fit increasing (including those who had sorted into descending order). Part c) was again generally well-attempted, with the most common reason for losing the A mark being simply an incorrect packing from part b). There were a reasonable number of candidates who divided their sum of weights by 11 rather than 10, demonstrating a misconception with the lower bound calculation. A very small number of candidates stated that n-1/2 or n+1/2 gave the minimum number of bins, which is an entirely false statement. Finally, part d) was generally well answered with candidates able to describe that 1.6 should be the penultimate number in the list, but very few appreciated that the sort could have been carried out from right to left, as opposed to left to right. Several candidates focused on the larger values in the list, which didn’t result in thorough enough reasoning, and a small group of candidates
Key points from the mark scheme and examiner's report
June 2024 · AS Paper 2 (Decision 1) · Q1(c)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This was generally a very accessible start to the paper and the majority of candidates scored highly overall. In part a) the candidates performed the quick sort algorithm efficiently and the majority scored full marks. There were few attempts at middle left pivot seen but, where seen, these were performed equally well. Common mistakes were to use a mixture of middle left and middle right pivots, or to ‘move’ the 4.5 too far on the second pass and then pivot on it. Both errors lost the second and third mark. Scores of 110 were seldom seen – candidates who completed the first three passes usually completed the sort. As always, a small number of candidates sorted the list into ascending order (then reversing their list in many cases) but this was heavily penalised, as were errors in ordering either side of the pivot. In part b) the first-fit decreasing algorithm was generally performed well, with scores of 2 and 3 out of 3 being extremely common. The most common mistakes here were with the 1.3 or 1, which lost the final A mark only. A small minority of candidates attempted full bin method, although a surprising number attempted first-fit increasing (including those who had sorted into descending order). Part c) was again generally well-attempted, with the most common reason for losing the A mark being simply an incorrect packing from part b). There were a reasonable number of candidates who divided their sum of weights by 11 rather than 10, demonstrating a misconception with the lower bound calculation. A very small number of candidates stated that n-1/2 or n+1/2 gave the minimum number of bins, which is an entirely false statement. Finally, part d) was generally well answered with candidates able to describe that 1.6 should be the penultimate number in the list, but very few appreciated that the sort could have been carried out from right to left, as opposed to left to right. Several candidates focused on the larger values in the list, which didn’t result in thorough enough reasoning, and a small group of candidates
Key points from the mark scheme and examiner's report
lower bound 44.8 ÷ 10 = 4.48 so at least 5 bins: yes, optimal
dividing by 11 instead of 10 was a common misconception
June 2024 · AS Paper 2 (Decision 1) · Q1(d)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
ignored or overlooked this final part.
Key points from the mark scheme and examiner's report
after two passes of a descending bubble sort the two smallest values must be in the last two positions, but 1.6 is not
few noticed the sort could run from either end
June 2024 · AS Paper 2 (Decision 1) · Q3(a)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This question saw a much wider range of scores awarded. Part a) required pupils to accurately define a “tree”, however few candidates correctly used the appropriate technical terms; those that did had clearly learnt the definition. Many incorrectly described a spanning tree or used “loops” instead of “cycles” or missed that it needed to be connected. Candidates were clearly unfamiliar with how to accurately convey the definition and often confused it with elements of other definitions that have been previously assessed and hence this part was often omitted. In part b) it was clear that candidates had learned Dijkstra’s algorithm, however the use of unknowns proved too much for some who either tried to deal with purely numerical values, or quickly made significant errors. However, a pleasing number of candidates scored 4, 5 or 6 marks on part i) for generally accurate attempts along with correct routes and lengths in terms of x. Common errors tended to occur at H (either 22 or 21 missing), G (30 or 26 missing), E and F or G and L labelled in the wrong order. Most candidates achieved the shortest route from A to M, but candidates were not necessarily clear that the length of their shortest route could be given as an expression, even though the question asked for the answer in this format. Some candidates are still obliterating their working values or writing them down in the incorrect order, indicating a lack of understanding of the process required. In part c) most candidates recognised the nodes BCHM as odd, however the most common response was to fail to appreciate that B and C were the start and end nodes and were not required as part of the correct calculation. Those that did identify HM as the pair, generally gave the correct arcs, however it was not uncommon to see vertices listed as opposed to arcs. Part d) produced a slender majority of correct answers, however frequently candidates stated 2, 6, or other integers, possibly from listing the nodes as opposed to the arcs. Most understood the need to add in the length of the repeated arcs from c) in part e). Those that had listed BC as one of their arcs ended up with e.g. x + y = 20 and were then able to progress further, often giving a wrong answer such as x = 9, y = 11. Those that correctly identified HL and LM in c) generally achieved both marks in e).
Key points from the mark scheme and examiner's report
a connected graph with no cycles
"loops", "paths" or spanning-tree descriptions score 0
June 2024 · Paper 3D (Decision 1) · Q1(a)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This first question proved to be accessible to all candidates. In part (a) many candidates answered this fluently recognising the relevance of the first two bins leading to and . Those who did not get the mark mostly restricted their reasoning to the fact that bin 2 had the highest packing at 40.
Key points from the mark scheme and examiner's report
16 not in bin 1 gives n < 17 + 8 + 16 = 41, and bin 2 holds 16 + 24 = 40, so n = 40
"bin 2 is the fullest" alone is not enough
June 2024 · Paper 3D (Decision 1) · Q1(b)4 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This first question proved to be accessible to all candidates. In part (b) many candidates gained full marks confidently using the quick sort algorithm. Surprisingly, a few incorrectly chose 24 or 23 as their first pivot therefore losing all four marks. The quality of presentation was variable, ranging from those with new and previous pivots clearly distinguished, to confused, crossed out circled or underlined numbers. The most common error was carrying out the quick sort in ascending order. Candidates should be advised that this loses at least two marks, being marked as a misread, as has been indicated in previous reports. A subsequent reversed list does not recover those marks. Another error was to fail to pivot from the sub-list {8, 4}, presumably because it was already ordered. This lost two marks. It was rare to see just one pivot per pass, leading to the loss of three marks. Only a handful of candidates lost marks due to slips changing or losing a number.
Key points from the mark scheme and examiner's report
middle pivot 19 first, then consistent middle pivots
descending order (ascending is marked as a misread)
pivot the sub-list 8, 4 even though ordered
24 or 23 as first pivot scores 0
June 2024 · Paper 3D (Decision 1) · Q1(c)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This first question proved to be accessible to all candidates. In part (c) most candidates correctly completed this straightforward first fit decreasing bin pack, though some had 8 and/or 4 misplaced, losing the second mark.
Key points from the mark scheme and examiner's report
first-fit decreasing on the sorted list: 24 16
23 17
20 19
13 12 11 4
8
8 and 4 sometimes misplaced
June 2024 · Paper 3D (Decision 1) · Q4(a)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This question required both accurate technical knowledge of the topic and good communication skills. Many candidates demonstrated one or the other, but not both. In part (a) some candidates did give the simplest answer, that a graph cannot have an odd number of odd nodes. However, many candidates opted to sum the degrees and then struggled to convey why 21 was impossible. It was quite common to see true statements, which failed to answer the question, for example “the sum of the degrees must be even” but with no supporting working relating to the question. Euler’s Handshaking Lemma was popular with candidates but not always quoted in a relevant fashion. A common misconception was that, as there were six nodes, no node could have a degree of more than five and some stated that the sum of the degrees could not exceed 12. Part (b) was slightly better answered than part (a), although not all candidates knew that the nodes of a Eulerian graph are all even. Some of those who did so, correctly answered by simply stating that the node of order 1 is odd. Others wasted time considering which of the four expressions in x would be odd or even, depending on whether x was an odd or even number.
Key points from the mark scheme and examiner's report
a graph cannot have an odd number (three) of odd vertices
or sum of degrees 21 is odd, so not twice the number of arcs
"sum must be even" without linking to 21 scored 0
June 2024 · Paper 3D (Decision 1) · Q4(b)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This question required both accurate technical knowledge of the topic and good communication skills. Many candidates demonstrated one or the other, but not both. Part (b) was slightly better answered than part (a), although not all candidates knew that the nodes of a Eulerian graph are all even. Some of those who did so, correctly answered by simply stating that the node of order 1 is odd. Others wasted time considering which of the four expressions in x would be odd or even, depending on whether x was an odd or even number.
Key points from the mark scheme and examiner's report
a node of degree 1 is odd, and an Eulerian graph needs all even degrees
June 2024 · Paper 3D (Decision 1) · Q4(c)5 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This question required both accurate technical knowledge of the topic and good communication skills. Many candidates demonstrated one or the other, but not both. In part (c)(i) those candidates who knew that a tree with 6 nodes has five edges arrived at the equation with ease and solved this to get . This method was not often seen. Most candidates used inequalities, often getting in quite a muddle. Many did state either or but then wrote down all the other possible inequalities, getting some of them wrong such as leading to . Exhaustive testing of all positive integers up to 4 was an acceptable method for full marks and proved successful for a minority. Some optimistically just stated that , ruling themselves out of all three marks. For (ii) as this part of the question starts “hence” candidates were obliged to use the value of x, whether or not calculated legitimately. This part was often correct with candidates getting both marks for listing the six valencies, or those of at least two more odd nodes, and drawing the correct conclusion. Some were hampered by ignorance of what is meant by semi-Eulerian or used an incorrect term such as non-Eulerian.
Key points from the mark scheme and examiner's report
a tree on 6 nodes has 5 arcs so the degree sum is 10: 8x − 14 = 10, x = 3
degrees 1, 2, 1, 1, 1, 4: more than two odd nodes so not semi-Eulerian
inequality methods often muddled
June 2024 · Paper 3D (Decision 1) · Q4(d)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This question required both accurate technical knowledge of the topic and good communication skills. Many candidates demonstrated one or the other, but not both. In part (d) there were many correct graphs seen, with loops proving popular. However, the graphs of a minority were isomorphic and quite a few made no attempt to draw a graph.
Key points from the mark scheme and examiner's report
any graph with degrees 1, 2, 3, 3, 3, 4 (8 arcs) not isomorphic to G, e.g. the degree-1 vertex joined to the degree-2 or degree-4 vertex
loops and multiple arcs allowed
June 2023 · AS Paper 2 (Decision 1) · Q14 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Examiners commented on the fact that many fully complete and correct responses were seen to this question. For the quick sort, most candidates used middle right pivots, rather than middle left. A few lost marks for using both middle left and right pivots during the sort. In rare cases candidates lost three of the four marks due to using only one pivot per iteration, after the first pass. Some lost the final mark for failing to pivot on the 56 (or the 59, for middle left) in the sub-list ’59 56’. Candidates need to look out for correctly ordered two item sub-lists like this and pivot accordingly. Incorrectly sorting into ascending order, followed by reversing the resulting list, was penalised with the loss of two marks (as the question specifically asked for the sort to be completed in descending order).
Key points from the mark scheme and examiner's report
quick sort into DESCENDING order: values greater than the pivot first
middle pivot (right or left) used consistently, several pivots per pass
pivot on two-item sub-lists such as 59 56
sorting ascending then reversing loses two marks
June 2023 · AS Paper 2 (Decision 1) · Q5(a)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
The responses to this question were mixed; some candidates left the entire question blank or only attempted the first two parts. Part (a), when attempted, was usually answered correctly (with most realising that adding a single arc between B and C would make G Eulerian). Similarly, in part (b), most candidates realised that the given route was not an example of a path
Key points from the mark scheme and examiner's report
1 arc (BC) makes all vertices even
June 2023 · AS Paper 2 (Decision 1) · Q5(b)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
The responses to this question were mixed; some candidates left the entire question blank or Similarly, in part (b), most candidates realised that the given route was not an example of a path but not all correctly articulated the reason why; general arguments were not accepted and specific mention had to be made to vertex C appearing twice (or the appearance of the cycle CFEC). Several candidates in this part thought that the given route was a path because all vertices appeared at least once (or thought this was the reason why it wasn’t a path). The responses, as expected, to part (c) were mixed with very few candidates scoring all six marks.
Key points from the mark scheme and examiner's report
not a path because vertex C appears twice (cycle C F E C)
general or "visits every vertex" arguments score 0
June 2023 · Paper 3D (Decision 1) · Q1(a)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Part (a) was generally well answered with most candidates identifying ‘neither’, and giving a suitably correct reason. A few candidates showed a lack of understanding, saying the graph was Eulerian because it had an even number of odd nodes. Furthermore, some candidates gave definitions for Eulerian and semi-Eulerian graphs without stating why graph G was neither.
Key points from the mark scheme and examiner's report
neither: four odd nodes (A, C, D, E), more than two
"contains odd nodes" or "at least 2 odd nodes" is not enough
some said Eulerian because the number of odd nodes is even
June 2023 · Paper 3D (Decision 1) · Q1(b)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Part (b) was mostly correct with only a small number of candidates not returning to their starting node (when stating their Hamiltonian cycle). Although part (c) was generally well answered there was a good number of candidates who
Key points from the mark scheme and examiner's report
e.g. A–B–C–D–E–A
must return to the start node
June 2023 · Paper 3D (Decision 1) · Q1(c)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Although part (c) was generally well answered there was a good number of candidates who stated that the graph could be drawn without arcs crossing but did not actually demonstrate this (by drawing the graph as planar) or explain how it could occur (e.g., by stating that AC should be moved ‘outside’). Most candidates in part (d) stated the correct answer of 2 but a significant number of
Key points from the mark scheme and examiner's report
planar: redraw with AC outside (or BE and BD outside)
stating it "can be drawn without crossings" without showing how scores 0
June 2023 · Paper 3D (Decision 1) · Q1(d)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Most candidates in part (d) stated the correct answer of 2 but a significant number of candidates stated 4 in this part. Examiners noted that very few incorrect answers were seen to part (e) but where they did it
Key points from the mark scheme and examiner's report
K₅ has 10 arcs and G has 8, so 2
4 was a common wrong answer
June 2023 · Paper 3D (Decision 1) · Q3(b)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Most candidates scored at least one mark in part (b), but often not both. While most responses indicated that the candidates understood that a ratio of the two values for n was required, many did not convert appropriately from seconds to minutes. There was a minority of candidates who incorrectly concluded that n(n2) implied that a cubic ratio of the two values for n was required.
Key points from the mark scheme and examiner's report
order n²: 0.0312 × (9000/9)² = 31 200 s = 520 minutes
convert to minutes
cubic ratio is wrong
June 2023 · Paper 3D (Decision 1) · Q4(a)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This question was accessible and was attempted by most candidates, most of whom earned at least some marks. Part (a) was generally well done with the majority gaining the mark. In previous series, with similar questions, candidates have been seen to assign a value to the unknown, 𝑥, at the outset but this was very rarely seen this series. A variety of valid approaches were employed such as comparing the total of the numbers (excluding 𝑥) to the capacity of 3 bins; comparing the total of the numbers (including 𝑥 taking its lower bound value) to the capacity of 3 bins; determining the required size of 𝑥 if the numbers were to fit into 3 bins followed by a deduction that 𝑥 would need to be negative and, less commonly, arguments based on the fact that four numbers had a magnitude that was at least half the bin size. Candidates should be reminded that their reasoning should always be specific to the question and the values given in the question, rather than more general statements which cannot be given credit. Those candidates who attempted arguments based on bin-packing were often less successful and rarely gained the mark.
Key points from the mark scheme and examiner's report
the known numbers total 132 and x > 23, so the total exceeds 120 = 3 × 40 (or lower bound 156/40 = 3.9)
reasoning must be specific
June 2023 · Paper 3D (Decision 1) · Q4(b)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This question was accessible and was attempted by most candidates, most of whom earned at least some marks. Part (b) was also generally well attempted with nearly all candidates finding at least one critical value and earning at least one mark, and most earning both marks. Many gave correct equivalent ranges such as 24 <= 𝑥 <= 28 or 23 < 𝑥 < 29. Common errors involved the strictness of the inequality with answers such as 23 < 𝑥 < 28. A minority of candidates gave the incorrect range of values as 23 < 𝑥 < 40, which did not take account of the fact that the numbers could fit into four bins. Others lost a mark for only stating one end of the range of values for 𝑥 e.g. 𝑥 <= 28.
Key points from the mark scheme and examiner's report
x > 23 (largest) and total ≤ 160 so x ≤ 28: 23 < x ≤ 28
strictness errors, 23 < x < 40, or only one end stated
June 2023 · Paper 3D (Decision 1) · Q4(c)3 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This question was accessible and was attempted by most candidates, most of whom earned at least some marks. The application of bin-packing in part (c) was done well with very few errors seen. When errors did occur, they were usually due to slips rather than misconceptions in the application of the algorithm and most candidates earned either two or three marks in this part. The most common error seemed to arise from a belief that only four bins could be used and in these cases the ‘13’ was placed in bin 3 with the ‘𝑥’ and the ‘4’, or the ‘4’ was placed in bin 2 with the ‘9’, ‘23’ and ‘5’ (even though this gave a bin size of 41). Cumulative totals were rare and only occurred as an apparent slip in one or two cases. “First-fit increasing” was also thankfully very rare. A minority of candidates repeated a digit (usually the ‘4’ or the ‘5’) which cost them the final two marks. A very small number of candidates assigned a value to x which limited the number of marks that could be achieved.
Key points from the mark scheme and examiner's report
15 22 3
9 23 5
x 4
18 20
13 (five bins)
forcing four bins put the 13 or 4 in the wrong bin
June 2023 · Paper 3D (Decision 1) · Q4(d)4 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This question was accessible and was attempted by most candidates, most of whom earned at least some marks. Most candidates were well-prepared for the quick sort in part (d) and most earned at least some of the four available marks. The question was accessible to almost all candidates with the extreme value x being the middle of the eleven items making the initial method mark very achievable. Common errors included inconsistency in the choice of middle-right or middle- left pivots, re-ordering numbers during a pass (commonly swapping the 3 and the 4 on the second pass), omission of the sixth pass, sorting into ascending rather than descending order, or very occasionally, the choice of a pivot for the first pass which was not middle-left or middle-right. Miscopies were rare, and values were lost from one pass to the next in only a minority of cases. The layout of candidates’ sorts was sometimes quite difficult to follow when the fixed value was not rewritten in subsequent passes. This was somewhat better when candidates drew vertical arrows, but candidates should be reminded that their solutions should be set out as clearly and logically as possible to avoid their own slips and to enable examiners to see the application of the sorting algorithm. Candidates employing a ‘slow-sort’, involving one pivot per iteration, were very rare as were applications of a Bubble sort.
Key points from the mark scheme and examiner's report
quick sort into descending order with consistent middle pivots, x first
six passes needed
swapping 3 and 4 in a pass and ascending order were common errors
June 2023 · Paper 3D (Decision 1) · Q4(e)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This question was accessible and was attempted by most candidates, most of whom earned at least some marks. In part (e), candidates who had found the correct upper bound for x in part (b) were usually successful in identifying 28 as the correct value of x. However, there were some errors seen in the manipulation of inequalities and some candidates incorrectly stated that 𝑥+ 15 < 40 and 𝑥+ 13 < 40 and so concluded that 𝑥 = 24 or 𝑥 = 26. Where 𝑥 = 28 was achieved, the justification for this value was often clearly given, but sometimes there was little reference to why ‘27’ was a critical value. Many candidates attempted to place items into bins, but many omitted the 13.
Key points from the mark scheme and examiner's report
first-fit decreasing: 15 not in bin 1 so x + 15 > 40
13 not in bin 1 so x + 13 > 40, x > 27
with x ≤ 28, x = 28
inequality reversals gave 24 or 26
June 2022 · AS Paper 2 (Decision 1) · Q1(a)4 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Examiners commented on the fact that many fully complete and correct responses were seen to this question. In (a), for the quick sort, most candidates used middle right pivots, rather than middle left. A few lost marks for using both middle left and right pivots during the sort. In rare cases candidates lost three of the four marks due to using only one pivot per iteration, after the first pass. Some lost the final mark for failing to pivot on the 47 (or the 44, for left middle) in the sub-list ’44 47’. Candidates need to look out for correctly ordered two item sub-lists like this and pivot accordingly. Incorrectly sorting into descending order, followed by reversing the resulting list, was penalised with the loss of two marks (as the question specifically asked for the sort to be completed in ascending order). In (b) (applying Kruskal’s algorithm) full marks
Key points from the mark scheme and examiner's report
pivot is the middle item (middle right or middle left, used consistently)
several pivots per pass after the first
remember to pivot on two-item sub-lists such as 44 47
sorting descending then reversing loses two marks
June 2022 · AS Paper 2 (Decision 1) · Q3(a)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Although “Path” is defined in the glossary, very few candidates were able to reproduce the definition in full for both marks. A minority just correctly stated that no vertex appears more than once (or equivalent), gaining only one mark. Many more candidates did score the next
Key points from the mark scheme and examiner's report
finite sequence of edges, end vertex of one is the start of the next, no vertex appears more than once
few gave all three points
June 2022 · AS Paper 2 (Decision 1) · Q3(b)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
mark in (b) for stating either that there were ‘six odd nodes’, or, ‘more than two odd nodes’, so the graph was neither Eulerian nor semi-Eulerian. Many candidates gained all five marks for correctly using Dijkstra’s algorithm in (c), though errors were often seen in the order of
Key points from the mark scheme and examiner's report
neither: six odd vertices (more than two)
"does not have two odd nodes" scores 0
June 2022 · Paper 3D (Decision 1) · Q1(a)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This question was accessible to nearly all candidates. The modal score was full marks and most candidates found this to be a straightforward start to the paper. There was however a common misconception in (a) in that several candidates added up all the items and dividing by the number of items rather than the size of each bin. In general candidates should ensure that their numbers are written clearly as often mistakes in reading their own handwriting meant that some candidates did not achieve an answer of 3.75 (and therefore 4) in (a).
Key points from the mark scheme and examiner's report
total length over bin size: 37.5/10 = 3.75 so at least 4 balls
dividing by the number of items was a common misconception
4 with no working scores 0
June 2022 · Paper 3D (Decision 1) · Q1(b)3 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This question was accessible to nearly all candidates. The modal score was full marks and most candidates found this to be a straightforward start to the paper. There was however a common Part (b) was also well answered by most candidates. However, the most common error was when it came to placing the fifth (and subsequent) items, where sometimes these values found their way into the wrong bin, implying that some candidates are not checking carefully each bin starting with the first bin which is not completely full. A small minority of candidates repeated values or missed a value out or applied the first-fit decreasing algorithm. 4
Key points from the mark scheme and examiner's report
4.3 5.1 0.4
6.1 2.5 1.3
4.7 3.4 1.7
5.9 2.1
check every bin from the first for each item
using first-fit decreasing is wrong
June 2022 · Paper 3D (Decision 1) · Q6(a)3 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This question was answered extremely well with most candidates making very good progress in the first three parts. In (a) some candidates did not output the value of c as requested even though an answer line was provided in the Answer Book. There was a definite improvement in the quality of responses seen in (b)(i) compared to previous series. A minority of
Key points from the mark scheme and examiner's report
trace for n = 5: (a, b, c) = (1, 3, 3), (2, 2, 8), (3, 1, 13), (4, 0, 16)
output 16 must be stated
June 2022 · Paper 3D (Decision 1) · Q6(b)5 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This question was answered extremely well with most candidates making very good progress in the quality of responses seen in (b)(i) compared to previous series. A minority of candidates did not sort into ascending order and instead sorted into descending. Several candidates used a quick sort rather than the requested bubble sort. A few candidates are still unaware of how to end the algorithm; too many assumed that once the values in the list were in the correct order, they did not need to complete a sixth pass. Most candidates in (b)(ii) stated the total number of comparisons as 39 although some did get confused here and stated the value as 45 instead (which was the answer to the next part). Although there were several good responses to (d) many candidates found this part too demanding and many left this blank. Those candidates who realised the link between their answer to (c) and this part were usually successful in determining the maximum total number of comparisons required to sort the weights of the arcs of K50 into ascending order using bubble sort. 7
Key points from the mark scheme and examiner's report
bubble sort from the left into ascending order: 6 passes including a final pass with no swaps
9 + 8 + 7 + 6 + 5 + 4 = 39 comparisons
quick sort or descending order lost marks
45 was a confusion with (c)
June 2022 · Paper 3D (Decision 1) · Q6(c)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This question was answered extremely well with most candidates making very good progress
Key points from the mark scheme and examiner's report
10 items: 9 + 8 + … + 1 = 45
June 2022 · Paper 3D (Decision 1) · Q6(d)3 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This question was answered extremely well with most candidates making very good progress
Key points from the mark scheme and examiner's report
use n = 5 with 45 comparisons (or n = 3 with 3) to get λ = 1/8
then (1/8)(50)(49)(51)(48) = 749 700
often left blank
Nov 2021 · Paper 3D (Decision 1) · Q1(a)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Part (a) was answered very well with almost all candidates giving the correct Hamiltonian cycle.
Key points from the mark scheme and examiner's report
C, V, E, X, A, W, D, Y, B, U, C
must return to C
Nov 2021 · Paper 3D (Decision 1) · Q1(b)3 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
When errors occurred it was usually in those who failed to return to C. In part (b) most candidates applied the planarity algorithm correctly although some did not make their method clear or just provided a pictorial justification for why the graph wasn’t planar (which was not acceptable).
Key points from the mark scheme and examiner's report
draw the Hamiltonian cycle as a polygon
label the remaining arcs I/O (e.g. AU inside, so BV, CW, DX, EY outside)
BV and CW both outside and cross, so not planar
a picture alone is not a justification
Nov 2021 · Paper 3D (Decision 1) · Q5(a)4 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Most candidates found parts (a) and (c) of this question straight-forward (quick-sort and bin- packing). Part (b) less so, as candidates had to explain why n must be either 44 or 45. Very few
Key points from the mark scheme and examiner's report
quick sort with middle pivots throughout, several pivots per pass after the first
state the sort is complete
first or last item as pivot scores 0
Nov 2021 · Paper 3D (Decision 1) · Q5(b)3 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
packing). Part (b) less so, as candidates had to explain why n must be either 44 or 45. Very few gave an argument along the lines of: • The 5 has been put in Bin 2 rather than Bin 1 which indicates that the size of the bins is 46 n <= less than 30 + 12 + 5 = 47 and so therefore 44 n >= • The fact that there is still room for the 2 in Bin 1 indicates that 5 23 18 46 n < + + = which implies that n • The 18 cannot fit in Bin 2 and so therefore is either 44 or 45
Key points from the mark scheme and examiner's report
5 not in bin 1 so n < 30 + 12 + 5 = 47
2 fits in bin 1 so n ≥ 44
18 not in bin 2 so n < 46
hence 44 or 45
few gave full reasoning
Nov 2021 · Paper 3D (Decision 1) · Q5(c)3 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Most candidates found parts (a) and (c) of this question straight-forward (quick-sort and bin- packing). Part (b) less so, as candidates had to explain why n must be either 44 or 45. Very few
Key points from the mark scheme and examiner's report
first-fit decreasing using the sorted list: 36 5 2
30 15
24 18
23 12 10
Nov 2021 · Paper 3D (Decision 1) · Q6(b)3 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Part (b), the most demanding part of the paper, was not answered correctly by any of the candidates taking the paper this series. No one realised that if one application of Dijkstra’s 2 n then repeated applications of the same algorithm to produce a table of algorithm had order 3. n Even though no candidate scored full marks in (b), the shortest distances would have order mark in (c), for explaining why the value in (b) was only an approximation, could still be earned (and was by some).
Key points from the mark scheme and examiner's report
n applications of an order n² algorithm is order n³
0.082 × (200/10)³ = 656 s
no candidate saw the cubic order
Nov 2021 · Paper 3D (Decision 1) · Q6(c)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
mark in (c), for explaining why the value in (b) was only an approximation, could still be earned (and was by some).
Key points from the mark scheme and examiner's report
order n³ only describes the dominant term
run-time is not exactly proportional to n³
"n³ is not exact" alone scores 0
Oct 2020 · AS Paper 2 (Decision 1) · Q1(a)3 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Examiners reported that a significant number of candidates struggled in applying the first-fit bin packing algorithm in part (a). This was mainly down to not applying the algorithm correctly. First fit is just that; candidates must decide if the current item under consideration will fit in the first bin rather than the most recent bin used. In this part several candidates placed the 1.9 in the second bin (and not the first bin) and so failed to score any marks in this part. Those candidates who did place the 1.9 in the first bin usually went on to score all three marks. Part (b) required
Key points from the mark scheme and examiner's report
first fit: each item goes in the FIRST bin it fits, not the latest bin
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Examiners reported that a significant number of candidates struggled in applying the first-fit bin who did place the 1.9 in the first bin usually went on to score all three marks. Part (b) required candidates to determine the order of the first-fit bin packing algorithm by considering the worst case. Although the question asked candidates to make both their method and working clear a significant number simply stated that the order was quadratic. For those candidates that attempted to show algebraic working many assumed that there were 1 + 2 + 3 + … + n 1 ( ) 1 . 2 n n + The correct approach comparisons in total and therefore gave an incorrect answer of was to realise that in the worst case the second number must be compared with the first number so one comparison, then the third number must be compared with the first and second numbers so two comparisons and so on giving in total 1 + 2 + 3 + … + (n – 1) comparisons leading to the 1 ( ) 1 2 n n - and hence quadratic order. correct answer of
Key points from the mark scheme and examiner's report
worst case: item k compared with k − 1 bins, total 1 + 2 + … + (n − 1) = ½n(n − 1), so quadratic order
1 + 2 + … + n is the common error
just stating "quadratic" scores B1 only
Oct 2020 · AS Paper 2 (Decision 1) · Q3(a)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Part (a) was found to be particularly demanding and very many candidates seem to suggest erroneous arguments along the lines of: • ‘an extra odd node would have no other node to pair with’: These candidates often stated that an even number of vertices of odd degree were required to apply the route inspection algorithm • Many candidates stated that ‘an odd number of odd degrees would make it impossible to traverse the graph’: These candidates often also stated that the graph would not be semi- Eulerian and sometimes argued that there would be half an arc with no end point • Many candidates stated simply ‘handshaking lemma’ but usually with little success as it was often accompanied by little or no supporting comment or argument • Some candidates attempted an induction-based argument stating that if there are only even degreed vertices then every arc added must create two vertices of odd degree Stronger candidates were able to score one of two marks – usually the first mark for stating a relationship between the number of arcs and the sum of the order of the vertices. There were also a significant minority of candidates who were able to provide clear and precise arguments and gain both marks.
Key points from the mark scheme and examiner's report
each arc adds 1 to the order of two vertices, so sum of orders = 2 × arcs is even, hence an even number of odd vertices
"handshaking lemma" alone or "nothing to pair with" arguments score 0
technical language required
Oct 2020 · Paper 3D (Decision 1) · Q5(a)3 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
were essential in (a), but relatively few candidates realised this, particularly related to x < 21. Both marks were frequently scored in (b) where the answer successful in (a) were often also able to make a good attempt in (c). Not many candidates realised that the word ‘distinct’ could inform their answer here. As previously, precise use of the strict inequality symbol resulted in the correct answer. It is worth noting that when candidates are required to give explanations or reasons they must leave nothing vague. For example, having spotted that 21 + 19 + 10 = 50, candidates must then state that therefore bin 2 is full, and not leave it to the examiner to make that deduction.
Key points from the mark scheme and examiner's report
18 not fitting bin 2 gives x > 50 − 37 = 13
10 fitting after x gives x ≤ 21
distinct numbers so x < 21
reasons must be explicit
Oct 2020 · Paper 3D (Decision 1) · Q5(b)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
related to x < 21. Both marks were frequently scored in (b) where the answer could just be written down with no supporting working. Those who were successful in (a) were often also able to make a good attempt in (c). Not many
Key points from the mark scheme and examiner's report
x passed 24 but not 17 in the first bubble-sort pass: 13 < x < 17
Oct 2020 · Paper 3D (Decision 1) · Q5(c)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
successful in (a) were often also able to make a good attempt in (c). Not many candidates realised that the word ‘distinct’ could inform their answer here. As previously, precise use of the strict inequality symbol resulted in the correct answer. It is worth noting that when candidates are required to give explanations or reasons they must leave nothing vague. For example, having spotted that 21 + 19 + 10 = 50, candidates must then state that therefore bin 2 is full, and not leave it to the examiner to make that deduction.
Key points from the mark scheme and examiner's report
first-fit decreasing: x in bin 3 gives x ≤ 15
bin 2 (21 + 19 + 10) is the full bin so bin 3 is not full: x = 14
must state bin 2 is full
Oct 2020 · Paper 3D (Decision 1) · Q6(a)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Surprisingly some candidates left part (a) blank. Others correctly stated that the graph was semi-Eulerian with their reason that it had two odd nodes but omitted the word ‘exactly’ (or equivalent), losing the second mark. It is worth noting that the two odd nodes were A and G, which is key information to be used later in the question. It is commonly the case that candidates would be well advised to keep earlier content in mind throughout questions. Although the question said ‘using appropriate algorithms’, the diagram in the answer book provided a strong clue to use Dijkstra and route inspection was also clearly indicated. Almost all candidates set about filling in labels and values on the diagram, applying the algorithm largely correctly, with many realising that expressions in x and y resulted as the second working values at F and G respectively, and therefore their final values. As is always the case, the length(s) of the resulting shortest path(s) should be stated too. A minority of candidates scored M0, and lost the next four marks too, due to stating only one working value at all vertices, including C, D, F and G. They should be reminded that the working values demonstrate the application of the correct method for this algorithm. Many candidates struggled with the remainder of this question, though some scored just one mark by adding their two lengths to equal 140, obtaining an equation in x and y. Use of the two odd nodes A and G along with 409 produced a variety of second equations in x and y, but some correctly added AG(= 60 + y) to 320 + x + y to complete their solution, by solving the two equations simultaneously.
Key points from the mark scheme and examiner's report
exactly two odd nodes (A and G) so semi-Eulerian
omitting "exactly" lost the second mark
June 2019 · AS Paper 2 (Decision 1) · Q1(a)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
As a ‘new specification’ question, this was met with varying degrees of success on the part of candidates. There were some perfect or near perfect responses but also many responses which lacked understanding K in part (a), others were clearly confused by the and/or knowledge. While most were able to draw 5 K .Some candidates missed out a single arc and terminology. Some drew a pentagon, others drew 6 K appeared here. many other subgraphs of 5 Part (b)(ii) was often well answered, even when part (a) had not been. Most candidates drew semi- Eulerian subgraphs of K5 but were sometimes let down by both graphs having the same number of arcs. Others incorrectly drew graphs with multiple arcs between pairs of nodes and some drew graphs with fewer than 5 nodes. Examiners noted that a few Eulerian graphs were provided here as well as some non-semi-Eulerian graphs with multiple nodes of order 1.
Key points from the mark scheme and examiner's report
complete graph on 5 vertices: every pair joined (10 arcs)
some drew a pentagon, K₆ or a subgraph
June 2019 · AS Paper 2 (Decision 1) · Q1(b)3 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
As a ‘new specification’ question, this was met with varying degrees of success on the part of candidates. There were some perfect or near perfect responses but also many responses which lacked understanding In part (b)(i), most candidates were familiar with the term ‘semi-Eulerian’, however often definitions fell short of the rigour required. It was common to see comments which did not imply ‘exactly’ two nodes of odd order. Examiners often commented that the phrase ‘at least two odd nodes’ was seen on a number of occasions. Many candidates also provided non credit-worthy descriptions involving the ability to ‘traverse each arc’. Part (b)(ii) was often well answered, even when part (a) had not been. Most candidates drew semi- Eulerian subgraphs of K5 but were sometimes let down by both graphs having the same number of arcs. Others incorrectly drew graphs with multiple arcs between pairs of nodes and some drew graphs with fewer than 5 nodes. Examiners noted that a few Eulerian graphs were provided here as well as some non-semi-Eulerian graphs with multiple nodes of order 1.
Key points from the mark scheme and examiner's report
(i) EXACTLY two nodes of odd order ("two odd nodes" or "at least two" not enough
"traverse each arc" answers score 0)
(ii) two semi-Eulerian subgraphs on 5 vertices with different numbers of edges
multiple arcs or fewer than 5 nodes seen
June 2019 · AS Paper 2 (Decision 1) · Q1(c)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
As a ‘new specification’ question, this was met with varying degrees of success on the part of candidates. There were some perfect or near perfect responses but also many responses which lacked understanding Part (c) discriminated well. It was common to see no response here and extremely common to see incorrect attempts. Nonetheless, the most able candidates were able to provide coherent and concise arguments which focussed on the key issues – most usually, the number of arcs required for a tree with the stated orders compared to the number of arcs on a tree with five nodes. Examiners noted that some candidates gave arguments based on the direct connection between the vertex of order 4 and each of the other vertices together with the resulting need for all other nodes to have order 1 for a tree. Other valid arguments were rarer but also appeared from time to time. For some candidates, there was a lot of confusion between arcs and nodes and many stated that there must be 6 nodes on a graph with the stated orders. Other candidates incorrectly deduced that ‘because the graph is Semi-Eulerian’ it could not be a tree, and some candidates seemed to think that there was only one odd node here. There were a substantial number of candidates who were able to pick up one mark out of two here for making some progress towards a correct explanation.
Key points from the mark scheme and examiner's report
sum of orders 12 so 6 arcs, but a tree on 5 nodes has 4 arcs (or vertex of order 4 forces all others to order 1)
drawing examples scores 0
arcs and nodes often confused
June 2019 · AS Paper 2 (Decision 1) · Q2(a)4 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Examiners commented on the fact that many fully complete and correct responses were seen to this question. However, they further commented that a number of applications of the algorithm in part (a)(i) went wildly awry. This was often precipitated by the first application of stage 10. Most candidates who ended up with approximations to I running into the tens and hundreds of thousands did not seem perturbed, perhaps indicating a lack of engagement with the problem. There were many approaches employed when completing the table and some candidates wasted time filling in every cell for A, B, N, H and C for the first several rows; this did not lose marks but certainly lost time. Others spread their values out across the table with one entry per row which was acceptable. Unfortunately, some candidates omitted key elements of the first and second row completely – quite often, 0 was missing from line one and sometimes 1 from line two. Most candidates worked with decimals with a significant minority using the fraction equivalents. Most candidates kept the output exact following their table, but some used a rounded value in part (b) which usually lost the final accuracy mark. More worryingly, some miscopied or lost digits transferring their answer from part (a) to part (b). It seems evident that candidates are less well prepared for questions such as these involving the application of relatively straightforward (but unseen) algorithms. their approximation from part (a). The vast majority were able to determine the exact value of I although there were a significant number who did not use their calculator and either spent longer than necessary calculating the value or made errors in the integration. Candidates should be advised that in such cases calculator use is perfectly acceptable and, indeed, is advisable. It was surprising the number of candidates who were unable to calculate the percentage error correctly. Despite being GCSE level work, candidates seemed stumped and were creative with their own version of the percentage error formula. Often, the denominator was the approximation rather than the exact answer. Sometimes, candidates simply found the ratio of the exact and approximate value. Others were not alarmed by huge percentage errors obtained by incorrect answers from part (a). The question requested that answers were given to 3 significant figures and a small number of candidates fell at this final hurdle giving answers to just 2 significant figures.
Key points from the mark scheme and examiner's report
trace table: H = 0.5, C = 0.25, D = 82, 92.125, 124.125, 202.25
output F = 50.5625
0 in row one and 1 in row two often missing
values running into thousands went unquestioned
June 2019 · AS Paper 2 (Decision 1) · Q2(b)3 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Examiners commented on the fact that many fully complete and correct responses were seen to this some used a rounded value in part (b) which usually lost the final accuracy mark. More worryingly, some miscopied or lost digits transferring their answer from part (a) to part (b). It seems evident that candidates are less well prepared for questions such as these involving the application of relatively straightforward (but unseen) algorithms. Part (b) asked for the evaluation of a definite integral and the calculation of the percentage error for their approximation from part (a). The vast majority were able to determine the exact value of I although
Key points from the mark scheme and examiner's report
exact I = 48.4
(50.5625 − 48.4)/48.4 × 100 = 4.47%
using a rounded or miscopied output from (a) lost the A mark
June 2019 · Paper 3D (Decision 1) · Q1(a)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Examiners reported that a significant number of candidates struggled in applying the first-fit bin packing algorithm in part (a). This was mainly down to not applying the algorithm correctly. First fit is just that; candidates must decide if the current item under consideration will fit in the first bin rather than the most recent bin used. In this part several candidates placed the 1.2 in the third bin (and not the first bin) and others did not place the 0.2 in the third bin. Many correct solutions were seen in part (b), but several candidates did not choose their pivots
Key points from the mark scheme and examiner's report
bins: 2.1 1.7 1.2
3.0 1.9
3.2 1.4 0.2
3.3 1.5
first fit checks every bin from the first, not just the most recent
common slips were 1.2 put in bin 3 and 0.2 not put in bin 3
June 2019 · Paper 3D (Decision 1) · Q1(b)4 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Examiners reported that a significant number of candidates struggled in applying the first-fit bin packing Many correct solutions were seen in part (b), but several candidates did not choose their pivots consistently, switching between middle-left and middle-right pivots during the quick sort algorithm. Several candidates either lost an item or changed an item during the sort, and in a small number of cases only one pivot was chosen per iteration. As stated in previous examiners’ reports candidates must make it clear that the sort is complete by either explicitly stating that the sort is complete or by choosing each item as a pivot or by rewriting the final list. A common error included the 1.5 not being used as a pivot for the fifth pass; candidates should be reminded that items should remain in the order from the previous pass as they move into sub-lists. There were only a few instances where candidates selected the first or last items as the pivot. Pivots were usually chosen consistently although the spacing and notation on some solutions made these difficult for examiners to follow. Some candidates over complicated the process by insisting on using a different ‘symbol’ to indicate the pivots for each pass. Those candidates who sorted into ascending order usually remembered to reverse their list at the end to gain full credit although several candidates left their list in ascending order.
Key points from the mark scheme and examiner's report
middle pivot (left or right) used consistently, more than one pivot per pass after the first
keep sub-list order from the previous pass (1.5 often missed as a pivot)
show the sort is complete
reverse an ascending list
June 2019 · Paper 3D (Decision 1) · Q1(c)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Examiners reported that a significant number of candidates struggled in applying the first-fit bin packing In part (c) many candidates scored both marks for showing correct working (for example, 2.32 11250log11250 t 2.32 log t k n n or starting with an equation of the form with and 450log450 n 450 to find k) followed by a final answer of 88.6. A sizeable minority did not score the accuracy mark for giving an answer of 88.56 or 90, as the question required an answer to the nearest tenth of a second. Those candidates with a correct answer, but no supporting working, scored one mark only, as the question explicitly stated that both method and working needed to be shown.
Key points from the mark scheme and examiner's report
2.32 × (11250 log 11250)/(450 log 450) = 88.6 s
must give 88.6, not 88.56 or 90
answer without working scores 1 mark only
June 2018 · AS Paper 2 (Decision 1) · Q1(b)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This question was the most successfully attempted question on the paper. Application of Dijkstra’s shortest time and/or the quickest route. Part (b) was generally well attempted. A significant proportion of students were clearly well prepared for this question. Others were confused though and treated the relationship as linear rather than as quadratic. Others incorrectly squared the constant of proportionality. A lot of students carried out a fairly substantial amount of working which sometimes lead to a correct answer (albeit sometimes with errors).
Key points from the mark scheme and examiner's report
1.5 × (9500/250)² = 2166 seconds
common errors were treating the relationship as linear or squaring the constant
June 2018 · AS Paper 2 (Decision 1) · Q1(c)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This question was the most successfully attempted question on the paper. Application of Dijkstra’s Part (c) was generally something of a challenge to many students. There were a large number of creative solutions which often featured discussions about the differing processing speeds of different computers, the validity of scaling up the relationship to a far larger value of n, and the impact of the rounding of 1.5 seconds. Some students were confused by the meaning of ‘run’ in the context of algorithms and talked about getting tired when ‘running long distances’. Very few gave ‘textbook’ explanations but there were a reasonable number of students who were able to refer to the lack of exact direct proportionality between run-time and n2.
Key points from the mark scheme and examiner's report
order n² only means the dominant term is n², so run-time is not exactly proportional to n²
answers about computer speed or rounding of 1.5 s score 0
June 2018 · AS Paper 2 (Decision 1) · Q2(a)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This question contained new content which has not appeared previously in 6689/01 and this was clear in the general standard of responses seen. It was common for (a) not to be completely correct. Common answer for this part were 4 and 6 but examiners saw a whole range of answers for the minimum and maximum number of arcs.
Key points from the mark scheme and examiner's report
minimum 3 arcs, maximum 6 (K₄)
4 and 6 was a common wrong pair
June 2018 · AS Paper 2 (Decision 1) · Q2(b)(i)3 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This question contained new content which has not appeared previously in 6689/01 and this was clear Part (b)(i) was more successful and most students managed to drawn a correct graph. In (ii) most stated that there were two odd nodes, so the graph was semi-Eulerian, but relatively few gained both marks as they failed to state the key point that the graph contained exactly two odd nodes.
Key points from the mark scheme and examiner's report
e.g. a square with one diagonal
must state EXACTLY two odd nodes so semi-Eulerian
"two odd nodes" alone loses the second mark
June 2018 · AS Paper 2 (Decision 1) · Q2(c)5 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This question contained new content which has not appeared previously in 6689/01 and this was clear Part (c) proved to be extremely challenging for students with many responses scoring no marks. The most common marks to be earned were the first mark for stating that the orders of the vertices summed to 10 and the second method mark for the identification that the order of the vertices could be 2, 2, 3 and 3. A reasonable number of students were able to identify that no order could be greater than 3 but they were then usually unable to develop this argument into a discussion of what this implied about possible orders and most did not consider orders of 1, 3, 3 and 3. The final mark for this part was the least commonly earned. Many students approached this question in terms of building up the graph from the bottom up and as such often did not properly consider the orders of the vertices as requested in the question. Most often students discussed the number of odd vertices and the number of even vertices rather than considering directly the possible numerical order of vertices. Examiners noted very few good attempts although there was very often a tendency to write copious amounts rather than to focus on the key issues. This was furthermore problematic given the standard of some handwriting which made reading responses very challenging.
Key points from the mark scheme and examiner's report
sum of orders = 2 × arcs = 10
no vertex can exceed order 3, so orders 1,3,3,3 (impossible) or 2,2,3,3 (unique, order-2 vertices not adjacent)
most did not consider 1,3,3,3 and the final mark was rarely earned
Find an Edexcel Further Maths tutor
Stuck on this? Book a trial lesson with our Further Maths tutor.