Further Mathematics · Pearson Edexcel 9FM0 · Option D1 · Topic 1

Algorithms and graph theory

What an algorithm is, sorting and bin-packing algorithms, and the language of graphs: vertices, edges, degrees, paths and cycles.

4 sub-topics
3 in Year 12, 1 in Year 13
68 practice questions
4 animated lessons

Practice questions (68) Lessons Worksheets All Edexcel Further Mathematics topics

What the specification says

Every sub-topic Pearson Edexcel can examine in this topic, with its reference number from the official specification. The Y12 and Y13 tags show when each sub-topic is usually taught.

1.1Algorithms and orderY12
1.2Bin packing and sortingY12
1.3Graph theoryY12
1.4Planarity algorithm and Hamiltonian cyclesY13

Try 3 questions

Easy, medium and hard questions from this topic, each with a worked solutions and the mark for every step. All 68 questions in this topic, free, no account needed.

Algorithms and graph theory

Easy

Algorithms and order · Year 12 · 3 marks

An algorithm has cubic order. A computer takes 2.4 seconds to run it on a problem of size 50.

(a)
Estimate the time taken for a problem of size 250.
(2)
(b)
Explain why your answer is only an estimate.
(1)

Show worked solutionHide worked solution

Part (a)2 marks

$2.4 \times \left(\frac{250}{50}\right)^3$
$= 300\text{ s}$

Part (b)1 mark

The order describes how time grows for large $n$ ; lower-order terms and constants are ignored.

Total3

MMethod mark: for a correct method, even with a slip.
AAccuracy mark: for a correct answer from a correct method.
BIndependent mark: for a correct fact or result on its own, with no method needed.

How did it go?

Report a problem with this question

Algorithms and graph theory

Medium

Bin packing · Year 12 · 6 marks

Nine items of sizes 11, 35, 19, 22, 3, 23, 6, 5, 23 are to be packed into bins of capacity 40.

(a)
Calculate a lower bound for the number of bins needed.
(2)
(b)
Use the first-fit decreasing algorithm to pack the items.
(3)
(c)
State whether your solution is optimal.
(1)

Check your answer before you look at the solution

Show worked solutionHide worked solution

Part (a)2 marks

$\frac{147}{40} = 3.67$
Round up. $\text{lower bound} = 4$

Part (b)3 marks

Sort into decreasing order first. $\text{sorted: } 35, 23, 23, 22, 19, 11, 6, 5, 3$
Each item goes into the first bin with room. $\text{bin }1: 35, 5 \ | \ \text{bin }2: 23, 11, 6 \ | \ \text{bin }3: 23, 3 \ | \ \text{bin }4: 22 \ | \ \text{bin }5: 19$

Part (c)1 mark

Not necessarily: it uses 5 bins and the lower bound is 4.

Total6

MMethod mark: for a correct method, even with a slip.
AAccuracy mark: for a correct answer from a correct method.
BIndependent mark: for a correct fact or result on its own, with no method needed.

How did it go?

Report a problem with this question

Algorithms and graph theory

Not needed for Year 12Hard

The planarity algorithm · Year 13 · 5 marks

A graph has the Hamiltonian cycle ABCDEFA and the four further edges AD, AE, BD, CF.

(a)
Explain what is meant by a Hamiltonian cycle.
(1)
(b)
Use the planarity algorithm to determine whether the graph is planar.
(4)

Show worked solutionHide worked solution

Part (a)1 mark

A cycle that visits every vertex exactly once and returns to the start.

Part (b)4 marks

Draw the Hamiltonian cycle as a polygon; the other edges must go inside or outside it.
Two chords cross if their end vertices alternate round the cycle.Crossing pairs: AD and CF, AE and CF, BD and CF.
Inside: CF; outside: AD, AE, BD. No crossings remain, so the graph is planar.

Total5

MMethod mark: for a correct method, even with a slip.
AAccuracy mark: for a correct answer from a correct method.
BIndependent mark: for a correct fact or result on its own, with no method needed.

How did it go?

Report a problem with this question