D1.1.1 The general ideas of algorithms and the implementation of an…

Section
D1.1 Algorithms and graph theory
Level
AS & A level
Statement
The general ideas of algorithms and the implementation of an algorithm given by a flow chart or text.
Guidance
The meaning of the order of an algorithm is expected. Students will be expected to determine the order of a given algorithm and the order of standard network problems.
Since 2018
14 parts, 33 marks · topic pages: Algorithms, sorting, bin packing and graph theory

Back to the checklist

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 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 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(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) · 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(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)
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(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)

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.