A-level Further Maths Year 12 · Topic 8
Decision mathematics
Decision maths is about finding the best way to do something.
We will run algorithms, use graphs and networks, and find minimum spanning trees and shortest paths.
Then we solve route inspection, linear programming and critical path problems.
- 5 subtopics
- 74 questions
- Free: 8.1 notes and 10 questions
In this topic
- 8.1Algorithms: sorting, bin packing and order of an algorithmFree below · 15 questions
- 8.2Graphs and networks: minimum spanning trees with Kruskal's and Prim's algorithmsOpen in Full Marks · 15 questions
- 8.3Shortest paths with Dijkstra's algorithm and route inspectionOpen in Full Marks · 11 questions
- 8.4Linear programming: formulating problems and the graphical methodOpen in Full Marks · 15 questions
- 8.5Critical path analysis: activity networks, floats and Gantt chartsOpen in Full Marks · 18 questions
8.1 · Free notes
Algorithms: sorting, bin packing and order of an algorithm
Key points
- An algorithm is a finite sequence of precise instructions. It can be shown as a list of steps, a flowchart or pseudocode, and traced with a table.
- Bubble sort compares adjacent items and swaps them if out of order; after each pass the largest unsorted item is in place. Quick sort chooses a pivot and splits the list into items less than and greater than it, then repeats on each sublist.
- Bin packing fits items into bins of fixed capacity: first-fit (each item in the first bin with room), first-fit decreasing (sort largest first, then first-fit, usually better), and full-bin (look for combinations that fill bins). The lower bound = total size ÷ bin capacity, rounded up.
- The order of an algorithm describes how its run time grows with the size n of the problem: for example bubble sort is quadratic, O(n²). If n doubles, a quadratic algorithm takes about 4 times as long.
In more detail
- Worked example (first-fit decreasing): sizes 7, 6, 5, 4, 3 into bins of 10: B1: 7, 3; B2: 6, 4; B3: 5. Three bins, matching the lower bound, so this is optimal.
- Quick sort pivot: using the middle item as the pivot is common in exams; each pass fixes at least one item.
- Exam tip: show the list after every pass, and state the number of comparisons and swaps if asked.
Practice
Algorithms: sorting, bin packing and order of an algorithm: 10 questions
Pick an answer to check it, or open the answer for the explanation.
1. After one pass of bubble sort (ascending), where is the largest number?
- At the end of the list
- At the start
- In the middle
- It has not moved
Show answer
A: At the end of the list. It bubbles to the end.
2. What does quick sort use to divide the list?
- A bin
- A spanning tree
- A pivot
- A critical path
Show answer
C: A pivot. Items are split around the pivot.
3. Items of size 4, 7, 3, 6, 5 are packed into bins of size 10. What is the lower bound for the number of bins?
- 2
- 3
- 4
- 5
Show answer
B: 3. 25/10 = 2.5, round up to 3.
4. Which bin packing algorithm sorts items into decreasing order first?
- First-fit
- Full-bin
- Bubble sort
- First-fit decreasing
Show answer
D: First-fit decreasing. Largest items first.
5. An algorithm is O(n²). If n goes from 100 to 300, how much longer does it take?
- About 9 times
- About 3 times
- About 6 times
- The same
Show answer
A: About 9 times. (300/100)² = 9.
6. Using first-fit on 4, 7, 3, 6, 5 (bins of 10), how many bins are used?
- 3
- 2
- 4
- 5
Show answer
C: 4. 4 → B1; 7 → B2; 3 → B1 (7); 6 → B3; 5 does not fit B1 (7), B2 (7) or B3 (6), so it needs B4.
7. What is the order of bubble sort?
- Linear, O(n)
- Quadratic, O(n²)
- Cubic, O(n³)
- Constant
Show answer
B: Quadratic, O(n²). About n²/2 comparisons.
8. What is a trace table used for?
- Drawing graphs
- Packing bins
- Finding critical paths
- Recording the values of variables at each step of an algorithm
Show answer
D: Recording the values of variables at each step of an algorithm. It shows how the algorithm runs.
9. Why is first-fit decreasing usually better than first-fit?
- Large items are placed first, leaving small ones to fill gaps
- It is faster
- It always gives the optimal answer
- It needs no sorting
Show answer
A: Large items are placed first, leaving small ones to fill gaps. Better packing, though not always optimal.
10. What makes an algorithm different from a vague set of instructions?
- It is written in English
- It is long
- It is finite and precise
- It uses numbers
Show answer
C: It is finite and precise. Each step is unambiguous.
Keep going in Full Marks
Full Marks has 15 questions on Algorithms: sorting, bin packing and order of an algorithm (5 more than here), set out in practice levels. You also get notes and 3D models for all 5 subtopics of Decision mathematics, plus games, timed exams and past papers.
On your exam board
- AQATopic 10: Option: Discrete
- OCR ATopic 8: Option: Discrete
- OCR BTopic 8: Option: Modelling with algorithms
- EdexcelTopic 11: Option: Decision Mathematics 1
Not in the Cambridge specification.