Further Mathematics · OCR H245 · Option D · Topic 7.03

Algorithms

Definition of an algorithm, awareness of the uses and practical limitations of algorithms, working with algorithms, the order of an algorithm, efficiency and complexity, strategies for sorting, strategies for packing.

  • 7 sub-topics
  • Taught in Year 12
  • 64 practice questions
  • 7 animated lessons
Practice questions (64) Lessons Worksheets coming soon All OCR Further Mathematics topics

What the specification says

Every sub-topic OCR 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. 7.03aDefinition of an algorithmY12
  2. 7.03bAwareness of the uses and practical limitations of algorithmsY13
  3. 7.03cWorking with algorithmsY13
  4. 7.03dThe order of an algorithmY12
  5. 7.03e-iEfficiency and complexityY13
  6. 7.03j-kStrategies for sortingY12
  7. 7.03l-mStrategies for packingY12

Try 2 questions

Easy and medium questions from this topic, each with a worked solutions and the mark for every step. All 64 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.
  1. (a)
    Estimate the time taken for a problem of size 250.
    (2)
  2. (b)
    Explain why your answer is only an estimate.
    (1)
Show worked solutionHide worked solution

Part (a)2 marks

  1. 2.4×(25050)32.4 \times \left(\frac{250}{50}\right)^3
  2. =300 s= 300\text{ s}

Part (b)1 mark

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

Total3

  • M
  • A
  • B
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.
  1. (a)
    Calculate a lower bound for the number of bins needed.
    (2)
  2. (b)
    Use the first-fit decreasing algorithm to pack the items.
    (3)
  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

  1. 14740=3.67\frac{147}{40} = 3.67
  2. Round up.lower bound=4\text{lower bound} = 4

Part (b)3 marks

  1. Sort into decreasing order first.sorted: 35,23,23,22,19,11,6,5,3\text{sorted: } 35, 23, 23, 22, 19, 11, 6, 5, 3
  2. Each item goes into the first bin with room.bin 1:35,5 ∣ bin 2:23,11,6 ∣ bin 3:23,3 ∣ bin 4:22 ∣ bin 5:19\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

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

Total6

  • M
  • A
  • B
How did it go?

Report a problem with this question