Algorithms, sorting, bin packing and graph theory Decision 1

Papers
A level Paper 3D; AS Paper 2 (option 27)
Level
AS and A level
Spec
D1.1.1, D1.1.2, D1.1.3, D1.1.4
Booklet
Nothing is given.
Since 2018
69 question parts, 161 marks

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.

Past-paper questions

Print this topic as a pack questions first, then the mark schemes

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
1 16 10 25 30 13 12 28 22 23 20 The list of ten numbers above is to be sorted into ascending order. (a) Carry out a bubble sort, starting at the left-hand end of the list, to produce the sorted list. You should only give the state of the list after each pass. (3)
June 2025 · AS Paper 2 (Decision 1) · Q3(a) 1 mark
3 B H A F C J E G Figure 2 [The total weight of the network is 153] Figure 2 models a network of roads in a town, where the nodes represent road junctions. The numbers on the edges are the times, in minutes, taken to walk along the corresponding roads. (a) State, with a reason, whether the graph in Figure 2 is Eulerian, semi-Eulerian or neither. (1)
June 2025 · Paper 3D (Decision 1) · Q1(a) 3 marks
1. 4.7 2.9 5.5 1.4 5.8 2.8 3.8 6.5 5.1 6.3 4.1 (a) Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 13 (3)
June 2025 · Paper 3D (Decision 1) · Q1(b) 2 marks
(b) Use the first-fit decreasing bin packing algorithm to determine how the numbers listed above can be packed into bins of size 13 (2)
June 2025 · Paper 3D (Decision 1) · Q2(a) 4 marks
2. 271 828 182 845 904 523 536 028 747 135 The list of ten numbers above is to be sorted into descending order. (a) Perform a quick sort on the list to obtain the sorted list. You should show the result of each pass and identify the pivots clearly. (4)
June 2025 · Paper 3D (Decision 1) · Q2(b) 2 marks
A list of n numbers is to be sorted into descending order using bubble sort. (b) Determine, in the worst case, the total number of comparisons required to sort the list. Give your answer as a simplified expression in terms of n. (2)
June 2025 · Paper 3D (Decision 1) · Q2(c) 3 marks
The following algorithm determines an approximation to the value of e Step 1 Start Step 2 Let a = 1 Step 3 Let b = 1 Step 4 Let c = 1 Step 5 Let d = a Step 6 Let c c ; b 1 1 Step 7 Let d d c Step 8 If b = 6 go to Step 11 Step 9 Let b = b + 1 Step 10 Go to Step 6 Step 11 Output d Step 12 Stop (c) Complete the table in the answer book to show the results obtained at each step of the algorithm. (3)
June 2025 · Paper 3D (Decision 1) · Q2(d) 1 mark
(d) Calculate, to 3 significant figures, the percentage error in using the value found in (c) to approximate the value of e (1)
June 2024 · AS Paper 2 (Decision 1) · Q1(a) 3 marks
1. 4 6.5 7 1.3 2 5 1.5 6 4.5 6 1 The list of eleven numbers shown above is to be sorted into descending order. (a) Carry out a quick sort to produce the sorted list. You should show the result of each pass and identify the pivots clearly. (3)
June 2024 · AS Paper 2 (Decision 1) · Q1(b) 3 marks
(b) Use the first‑fit decreasing bin packing algorithm to pack the numbers into bins of size 10 (3)
June 2024 · AS Paper 2 (Decision 1) · Q1(c) 2 marks
(c) Determine whether your answer to part (b) uses the minimum number of bins. You must justify your answer. (2)
June 2024 · AS Paper 2 (Decision 1) · Q1(d) 1 mark
A different list of eleven numbers is to be sorted into descending order using a bubble sort. The list after the second pass is 4.5 5.6 3.8 6.7 5.4 1.6 4.8 9.1 3.3 1.7 1.5 (d) Explain how you know that at least one of the first two passes of the bubble sort was not carried out correctly. (1)
June 2024 · AS Paper 2 (Decision 1) · Q3(a) 1 mark
3. K F B y C G M A H x L E J Figure 3 [The total weight of the network is 139 + x + y] (a) Explain what is meant by the term “tree”. (1)
June 2024 · Paper 3D (Decision 1) · Q1(a) 1 mark
1. The eleven numbers listed above are to be packed into bins of size n where n is a positive integer. When the first-fit bin packing algorithm is applied to the eleven numbers, the bins are packed as shown below. Bin 1: Bin 2: Bin 3: Bin 4: Bin 5: (a) Explain why this packing means that the value of n must be 40 (1)
June 2024 · Paper 3D (Decision 1) · Q1(b) 4 marks
The original list of eleven numbers is to be sorted into descending order. (b) Use a quick sort to obtain the fully sorted list. You must make your pivots clear. (4)
June 2024 · Paper 3D (Decision 1) · Q1(c) 2 marks
(c) Apply the first-fit decreasing bin packing algorithm to the fully sorted list to pack the numbers into bins of size 40 (2)
June 2024 · Paper 3D (Decision 1) · Q4(a) 1 mark
4. (a) Explain why it is not possible to draw a graph with exactly six nodes with degrees 1, 2, 3, 4, 5 and 6 (1)
June 2024 · Paper 3D (Decision 1) · Q4(b) 1 mark
A tree, T, has exactly six nodes. The degrees of the six nodes of T are (4 – x) (2x – 5) (4x – 11) (3x – 5) where x is an integer. (b) Explain how you know that T cannot be Eulerian. (1)
June 2024 · Paper 3D (Decision 1) · Q4(c) 5 marks
(c) (i) Determine the value of x (ii) Hence state whether T is semi-Eulerian or not. You must justify your answer. (5)
June 2024 · Paper 3D (Decision 1) · Q4(d) 1 mark
Figure 2 Figure 2 shows a graph, G, with six nodes with degrees 1, 2, 3, 3, 3 and 4 (d) Using the vertices in Diagram 1 in the answer book, draw a graph with exactly six nodes with degrees 1, 2, 3, 3, 3 and 4 that is not isomorphic to G. (1)
June 2023 · AS Paper 2 (Decision 1) · Q1 4 marks
1. 67 59 46 71 40 48 53 63 45 54 56 The list of eleven numbers shown above is to be sorted into descending order. Carry out a quick sort to produce the sorted list. You should show the result of each pass and identify the pivots clearly.
June 2023 · AS Paper 2 (Decision 1) · Q5(a) 1 mark
5. B x + 4 2x + 1 5x – 8 2x – 2 C A x + 5 3x + 2 x + 7 E 5x – 6 F Figure 4 [The weight of the network is 20x + 3] Figure 4 shows a graph G that contains 8 arcs and 6 vertices. (a) State the minimum number of arcs that would need to be added to make G into an Eulerian graph. (1)
June 2023 · AS Paper 2 (Decision 1) · Q5(b) 1 mark
(b) Explain whether or not the route A – C – F – E – C – D – B is an example of a path on G. (1)
June 2023 · Paper 3D (Decision 1) · Q1(a) 1 mark
1. E A B C Figure 1 Figure 1 shows the graph G. (a) State whether G is Eulerian, semi-Eulerian, or neither, giving a reason for your answer. (1)
June 2023 · Paper 3D (Decision 1) · Q1(b) 1 mark
(b) Write down an example of a Hamiltonian cycle on G. (1)
June 2023 · Paper 3D (Decision 1) · Q1(c) 1 mark
(c) State whether or not G is planar, justifying your answer. (1)
June 2023 · Paper 3D (Decision 1) · Q1(d) 1 mark
(d) State the number of arcs that would need to be added to G to make the graph K5 (1)
June 2023 · Paper 3D (Decision 1) · Q3(b) 2 marks
2 , where n is the number of nodes in One application of Dijkstra’s algorithm has order n the network. It takes a computer 0.0312 seconds to find the shortest path from a given start node to a given end node in a network of 9 nodes. (b) Calculate approximately how long it would take, in minutes, for the computer to find the shortest path from a given start node to a given end node for a network of 9000 nodes. (2)
June 2023 · Paper 3D (Decision 1) · Q4(a) 1 mark
4. The eleven distinct numbers listed below are to be packed into bins of size 40 15 22 3 9 23 x 5 4 18 20 13 It is known that x • is an integer less than 40 • is the largest number in the list (a) Explain why it is not possible to pack the numbers into 3 bins of size 40 (1)
June 2023 · Paper 3D (Decision 1) · Q4(b) 2 marks
Given that it is possible to pack the numbers into 4 bins of size 40 (b) determine the range of values for x (2)
June 2023 · Paper 3D (Decision 1) · Q4(c) 3 marks
(c) Use the first-fit bin packing algorithm to determine how the numbers can be packed into bins of size 40 (3)
June 2023 · Paper 3D (Decision 1) · Q4(d) 4 marks
(d) Carry out a quick sort to produce a list of the numbers in descending order. You should show the result of each pass and identify your pivots clearly. (4)
June 2023 · Paper 3D (Decision 1) · Q4(e) 2 marks
When the first-fit decreasing bin packing algorithm is applied to the list, neither the 15 nor the 13 is placed in the first bin. (e) Determine the value of x. You must give reasons for your answer. (2)
June 2022 · AS Paper 2 (Decision 1) · Q1(a) 4 marks
1. 55 44 34 59 28 37 41 52 33 42 47 The list of eleven numbers shown above is to be sorted into ascending order. (a) Carry out a quick sort to produce the sorted list. You should show the result of each pass and identify your pivots clearly. (4)
June 2022 · AS Paper 2 (Decision 1) · Q3(a) 2 marks
3. B E C H A F G Figure 2 [The total weight of the network is 120] (a) Explain what is meant by the term “path”. (2)
June 2022 · AS Paper 2 (Decision 1) · Q3(b) 1 mark
(b) State, with a reason, whether the network in Figure 2 is Eulerian, semi-Eulerian or neither. (1)
June 2022 · Paper 3D (Decision 1) · Q1(a) 2 marks
1. A gardener needs the following lengths of string. All lengths are in metres. 4.3 6.1 5.1 4.7 2.5 5.9 3.4 1.7 2.1 0.4 1.3 She cuts the lengths from balls of string. Each ball contains 10 m of string. (a) Calculate a lower bound for the number of balls of string the gardener needs. You must make your method clear. (2)
June 2022 · Paper 3D (Decision 1) · Q1(b) 3 marks
(b) Use the first‑fit bin packing algorithm to determine how the lengths could be cut from the balls of string. (3)
June 2022 · Paper 3D (Decision 1) · Q6(a) 3 marks
6. The following algorithm determines the number of comparisons made when Prim’s algorithm is applied to Kn Step 1 Start Step 2 Input the value of n Step 3 Let a = 1 Step 4 Let b = n – 2 Step 5 Let c = b Step 6 Let a = a + 1 Step 7 Let b = b – 1 Step 8 Let c = c + (a x b) + (a – 1) Step 9 If b > 0 go to Step 6 Step 10 Output c Step 11 Stop (a) For K5, complete the table in the answer book to show the results obtained at each step of the algorithm. (3)
June 2022 · Paper 3D (Decision 1) · Q6(b) 5 marks
B C A 24 14 E Figure 4 The weights of the ten arcs in Figure 4 are 17 21 24 14 23 13 15 19 28 20 (b) (i) Starting at the left‑hand end of the above list, sort the list into ascending order using bubble sort. You need only write down the state of the list at the end of each pass. (ii) Find the total number of comparisons performed during the sort. (5)
June 2022 · Paper 3D (Decision 1) · Q6(c) 1 mark
(c) Find the maximum total number of comparisons required to sort the weights of the 10 arcs of K5 into ascending order using bubble sort. (1)
June 2022 · Paper 3D (Decision 1) · Q6(d) 3 marks
It is given that the maximum total number of comparisons required to sort the weights of the arcs of Kn into ascending order using bubble sort is λn(n – 1)(n + 1)(n – 2) where λ is a constant. (d) Determine the maximum total number of comparisons required to sort the weights of the arcs of K50 into ascending order using bubble sort. You must make your method and working clear. (3)
Nov 2021 · Paper 3D (Decision 1) · Q1(a) 1 mark
1. A U B V C W X E Y Figure 1 A Hamiltonian cycle for the graph in Figure 1 begins C, V, E, X, A, W, …. (a) Complete the Hamiltonian cycle. (1)
Nov 2021 · Paper 3D (Decision 1) · Q1(b) 3 marks
(b) Hence use the planarity algorithm to determine whether the graph shown in Figure 1 is planar. You must make your working clear and justify your answer. (3)
Nov 2021 · Paper 3D (Decision 1) · Q5(a) 4 marks
5. 30 12 5 2 23 18 36 10 15 24 (a) The list of ten numbers above is to be sorted into descending order. Use a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly. (4)
Nov 2021 · Paper 3D (Decision 1) · Q5(b) 3 marks
The ten numbers are to be packed into bins of size n, where n is a positive integer. When the first-fit bin packing algorithm is applied to the original list of ten numbers, the following allocation is obtained. Bin 1: 30 12 2 Bin 2: 5 23 10 Bin 3: 18 15 Bin 4: 36 Bin 5: 24 (b) Explain why the value of the integer n must be either 44 or 45 (3)
Nov 2021 · Paper 3D (Decision 1) · Q5(c) 3 marks
(c) Use the first-fit decreasing bin packing algorithm to determine how the numbers can be packed into bins of size 45 (3)
Nov 2021 · Paper 3D (Decision 1) · Q6(b) 3 marks
One application of Dijkstra’s algorithm has order n2 , where n is the number of nodes in the network. A computer produces a table of shortest distances between any two different nodes by repeatedly applying Dijkstra’s algorithm from each node of the network. It takes the computer 0.082 seconds to produce a table of shortest distances for a network of 10 nodes. (b) Calculate approximately how long it will take, in seconds, for the computer to produce a table of shortest distances for a network with 200 nodes. You must give a reason for your answer. (3)
Nov 2021 · Paper 3D (Decision 1) · Q6(c) 1 mark
(c) Explain why your answer to part (b) can only be an approximation. (1)
Oct 2020 · AS Paper 2 (Decision 1) · Q1(a) 3 marks
1. 3.7 2.5 5.4 1.9 2.7 3.2 3.1 2.7 4.2 2.0 (a) Use the first‑fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 8.5 (3)
Oct 2020 · AS Paper 2 (Decision 1) · Q1(b) 3 marks
The first‑fit bin packing algorithm is to be used to pack n numbers into bins. The number of comparisons is used to measure the order of the first‑fit bin packing algorithm. (b) By considering the worst case, determine the order of the first‑fit bin packing algorithm in terms of n. You must make your method and working clear. (3)
Oct 2020 · AS Paper 2 (Decision 1) · Q3(a) 2 marks
3. B C E 2x + 10 A F 3x – 2 G H Figure 2 [The weight of the network is 5x + 246] (a) Explain why it is not possible to draw a graph with an odd number of vertices of odd valency. (2)
Oct 2020 · Paper 3D (Decision 1) · Q5(a) 3 marks
5. The nine distinct numbers in the following list are to be packed into bins of size 50 23 17 19 x 24 8 18 10 21 When the first-fit bin packing algorithm is applied to the numbers in the list it results in the following allocation. Bin 1: 23 17 8 Bin 2: 19 x 10 Bin 3: 24 18 Bin 4: 21 (a) Explain why 13 < x < 21 (3)
Oct 2020 · Paper 3D (Decision 1) · Q5(b) 2 marks
The same list of numbers is to be sorted into descending order. A bubble sort, starting at the left-hand end of the list, is to be used to obtain the sorted list. After the first complete pass the list is 23 19 17 24 x 18 10 21 8 (b) Using this information, write down the smallest interval that must contain x, giving your answer as an inequality. (2)
Oct 2020 · Paper 3D (Decision 1) · Q5(c) 2 marks
When the first-fit decreasing bin packing algorithm is applied to the nine distinct numbers it results in the following allocation. Bin 1: 24 23 Bin 2: 21 19 10 Bin 3: 18 17 x Bin 4: 8 Given that only one of the bins is full and that x is an integer, (c) calculate the value of x. You must give reasons for your answer. (2)
Oct 2020 · Paper 3D (Decision 1) · Q6(a) 2 marks
6. E B x F A C y G Figure 4 [The total weight of the network is 320 + x + y] (a) State, with justification, whether the graph in Figure 4 is Eulerian, semi-Eulerian or neither. (2)
June 2019 · AS Paper 2 (Decision 1) · Q1(a) 1 mark
1. (a) Draw the graph K5 (1)
June 2019 · AS Paper 2 (Decision 1) · Q1(b) 3 marks
(b) (i) In the context of graph theory explain what is meant by ‘semi-Eulerian’. (ii) Draw two semi-Eulerian subgraphs of K5, each having five vertices but with a different number of edges. (3)
June 2019 · AS Paper 2 (Decision 1) · Q1(c) 2 marks
(c) Explain why a graph with exactly five vertices with vertex orders 1, 2, 2, 3 and 4 cannot be a tree. (2)
June 2019 · AS Paper 2 (Decision 1) · Q2(a) 4 marks
2. The following algorithm produces a numerical approximation for the integral B∫ x4 dx I = A Step 1 Start Step 2 Input the values of A, B and N Step 3 Let H = (B – A) / N Step 4 Let C = H / 2 Step 5 Let D = 0 Let D = D + A4 + B4 Step 6 Step 7 Let E = A Step 8 Let E = E + H Step 9 If E = B go to Step 12 Step 10 Let D = D + 2 x E4 Step 11 Go to Step 8 Step 12 Let F = C x D Step 13 Output F Step 14 Stop For the case when A = 1, B = 3 and N = 4, (a) (i) complete the table in the answer book to show the results obtained at each step of the algorithm. (ii) State the final output. (4)
June 2019 · AS Paper 2 (Decision 1) · Q2(b) 3 marks
(b) Calculate, to 3 significant figures, the percentage error between the exact value of I and the value obtained from using the approximation to I in this case. (3)
June 2019 · Paper 3D (Decision 1) · Q1(a) 2 marks
1. 2.1 1.7 3.0 1.9 3.2 1.2 3.3 1.4 1.5 0.2 (a) Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 5 (2)
June 2019 · Paper 3D (Decision 1) · Q1(b) 4 marks
The list of numbers is now to be sorted into descending order. (b) Perform a quick sort on the original list to obtain the sorted list. You should show the result of each pass and identify your pivots clearly. (4)
June 2019 · Paper 3D (Decision 1) · Q1(c) 2 marks
For a list of n numbers, the quick sort algorithm has, on average, order n log n. Given that it takes 2.32 seconds to run the algorithm when n = 450 (c) calculate approximately how long it will take, to the nearest tenth of a second, to run the algorithm when n = 11 250. You should make your method and working clear. (2)
June 2018 · AS Paper 2 (Decision 1) · Q1(b) 2 marks
For a network with n vertices, Dijkstra’s algorithm has order n? (b) If it takes 1.5 seconds to run the algorithm when n = 250, calculate approximately how long it will take, in seconds, to run the algorithm when 7 = 9500. You should make your method and working clear. (2)
June 2018 · AS Paper 2 (Decision 1) · Q1(c) 1 mark
(c) Explain why your answer to part (b) is only an approximation. (1)
June 2018 · AS Paper 2 (Decision 1) · Q2(a) 2 marks
2. A simply connected graph is a connected graph in which any two vertices are directly connected by at most one arc and no vertex is directly connected to itself. (a) Given that a simply connected graph has exactly four vertices, (i) write down the minimum number of arcs it can have, (ii) write down the maximum number of arcs it can have. (2)
June 2018 · AS Paper 2 (Decision 1) · Q2(b)(i) 3 marks
(b) (i) Draw a simply connected graph that has exactly four vertices and exactly five arcs. (ii) State, with justification, whether your graph is Eulerian, semi-Eulerian or neither. (3)
June 2018 · AS Paper 2 (Decision 1) · Q2(c) 5 marks
(c) By considering the orders of the vertices, explain why there is only one simply connected graph with exactly four vertices and exactly five arcs. (5)

Find an Edexcel Further Maths tutor

Stuck on this? Book a trial lesson with our Further Maths tutor.

Prefer email? Send an enquiry

If you are under 18, please include a parent's contact details. Enquiries go to enquiries@alevelfurthermathstutor.com and are deleted once handled.