Algorithms
Revise Algorithms for Further Decision Mathematics 1 WDM11 (AS Level) — revision notes and instant AI marking. Free to start.
Summary — What This Chapter Is Really About
- An algorithm is a set of precise instructions that, if followed exactly, solves a problem. It can be written as text, pseudocode, or a flow chart.
- "Robot mode" is the golden rule of this whole chapter: never take a shortcut just because you can "see" the answer. Follow every instruction, in order, exactly as a machine would.
- Order (complexity) of an algorithm tells you how the number of steps grows as the amount of input data grows — linear, quadratic, cubic, and so on.
- Bubble sort repeatedly compares neighbouring pairs and swaps them if they're the wrong way round, "bubbling" the largest value to the end of the list each pass.
- Quick sort picks a middle "pivot" value and splits the list into a sub-list of smaller values and a sub-list of bigger values, then repeats on each sub-list.
- Bin packing algorithms (first-fit, first-fit decreasing, full-bin) try to pack objects into as few equal-sized bins as possible — never guaranteed to be perfect, just "good enough."
- The lower bound for bin packing tells you the theoretical minimum number of bins you could ever need — your algorithm's answer should be compared against it.
1. General Algorithms
What is an algorithm?
Think about a recipe for baking a cake. It doesn't say "make a cake" and leave you to figure it out — it tells you exactly what to do, in exactly what order: crack two eggs, add 200g of flour, mix for 3 minutes, bake at 180°C for 25 minutes. That's an algorithm. It's a set of precise instructions that, if you follow them strictly, will always lead to the solution to a problem.
Algorithms matter hugely for computers because computers can't "use their initiative" — they can only follow instructions exactly. A robot vacuum cleaner follows an algorithm to decide where to go next. A satnav follows an algorithm to find your route. Even you, cooking dinner or building flat-pack furniture, are following an algorithm.
How can an algorithm be presented?
- Written instructions — a numbered list of steps in plain words.
- Pseudocode — a mixture of everyday words and very basic code-like commands (Let, If, While, Input, Output). You don't need to know a real programming language to read it.
- Flow charts — a diagram using shapes to show the order of steps, especially useful when there are decisions or repeated loops.
Flow chart shapes
| Shape | Meaning | Alternative name |
|---|---|---|
| Oval | Start or End | Termination |
| Rectangle | An instruction | — |
| Diamond | A question (yes/no branch) | Decision box |
Note: the word "print" is sometimes used instead of "output" for the final result.
Optimal vs. sufficient solutions
Not every algorithm gives you the perfect (optimal) answer — sometimes it just gives you an answer that's good enough for the situation. For example, a touring band might use a quick algorithm to plan their UK tour route. If it's out by 200 miles across a total journey of thousands of miles, that's not a big deal — but working out the mathematically perfect route might take far too long to be worth it. In real life, there's often a trade-off between an algorithm's speed/efficiency and the accuracy of what it produces.
An algorithm (shown as a flow chart) inputs a number n, then repeatedly tests values of k and p = k² to check whether n is a square number.
For n = 23:
| n | k | p | Is p > n? | Is p = n? |
|---|---|---|---|---|
| 23 | 1 | 1 | NO | NO |
| 2 | 4 | NO | NO | |
| 3 | 9 | NO | NO | |
| 4 | 16 | NO | NO | |
| 5 | 25 | YES |
Output: 23 is not a square number.
Notice: once "Is p > n?" answers YES, the algorithm stops and outputs immediately — it never even checks "Is p = n?" on that final row. That's exactly the kind of precise, no-shortcuts following the examiners want to see.
An algorithm instructs: "Input a value x. If x is even, output 'even'. If x is odd, let y = x + 1 and output y." Trace the algorithm for x = 7.
2. Order (Complexity) of an Algorithm
The order of an algorithm describes how "complex" it is — specifically, how the maximum number of steps it needs grows as you feed it more input data. It's described using a mathematical function of n, the input size.
Common orders
| Order | Meaning | Example function |
|---|---|---|
| Linear | Steps ∝ size of input | n |
| Quadratic | Steps ∝ square of input | n² |
| Cubic | Steps ∝ cube of input | n³ |
| Other | Square roots, logs, exponentials, etc. | √n, n log n, ... |
For example, an algorithm that searches every item in a list, one at a time, to find a target value is of linear order — worst case, it checks all n items.
Using order to estimate completion time
Since the order tells you how steps scale with input size, you can use it to estimate (not calculate exactly) how long a bigger input will take, using proportionality.
An algorithm for sorting n values has order n ln n. It takes 0.12 seconds for a list of 3000 values. Estimate the time for 60,000 values.
0.12 seconds corresponds to order 3000 ln(3000).
Time ≈ 0.12 × [60000 ln(60000)] ÷ [3000 ln(3000)] = 3.298...
Estimated time ≈ 3.30 seconds (3 s.f.)
An algorithm of quadratic order takes 4 seconds to process an input of size 50. Estimate how long it takes to process an input of size 100.
3. Sorting Algorithms
Sorting algorithms arrange a list of items (usually numbers, but could be letters or words) into ascending or descending order. Easy for a human with a short list — but a computer needs a precise algorithm to do it reliably every time, even with thousands of items. Again: robot mode. Don't skip steps just because the answer looks obvious.
3.1 Bubble Sort
Imagine a bubble of air rising through water — each pass, the largest (or smallest, for descending) remaining value "bubbles" its way to the correct end of the list. Bubble sort does this by comparing neighbouring pairs: item 1 vs item 2, then item 2 vs item 3, and so on. If a pair is the wrong way round, swap them. If they're equal, that does not count as a swap.
One full sweep through the list like this is called a pass. After each pass, the item that ends up at the back of the working list is guaranteed to be in its final, correct position — so it can be dropped from the "working list" for future passes. This shrinking working list is what keeps bubble sort reasonably efficient.
Counting passes, comparisons and swaps (for n items)
| Quantity | Formula / Logic |
|---|---|
| Maximum number of passes | n − 1 |
| Comparisons in the kth pass | n − k |
| Maximum total comparisons | (n−1) + (n−2) + ... + 1 = ½n(n−1) → quadratic order |
| Maximum swaps in a pass | Same as comparisons in that pass (happens if list starts in reverse order) |
Sort 5, 7, 4, 9, 3, 5, 6 into ascending order. After pass 2, the list is: 4, 5, 3, 5, 6, 7, 9 (the last two items, 7 and 9, are already correctly placed).
Pass 3 — working list is now just: 4, 5, 3, 5, 6
| Full list during pass 3 | Comparison | ||||||
|---|---|---|---|---|---|---|---|
| 4 | 5 | 3 | 5 | 6 | 7 | 9 | 4 < 5, no swap |
| 4 | 5 | 3 | 5 | 6 | 7 | 9 | 5 > 3, SWAP |
| 4 | 3 | 5 | 5 | 6 | 7 | 9 | 5 = 5, no swap |
| 4 | 3 | 5 | 5 | 6 | 7 | 9 | 5 < 6, no swap |
1 swap made in pass 3. Two more passes are needed: pass 4 swaps 4 and 3 (one swap), and pass 5 has no swaps — so the algorithm is complete after pass 5, giving 3, 4, 5, 5, 6, 7, 9.
A list of 6 items is to be sorted using bubble sort. State (i) the maximum number of passes required, and (ii) the number of comparisons in the 2nd pass.
Perform one pass of bubble sort (ascending) on: 8, 3, 6, 1. Show every comparison and state the resulting list.
3.2 Quick Sort
Quick sort works completely differently to bubble sort. Instead of comparing neighbours, it picks a pivot — the middle value of the current sub-list — and splits everything else into two groups: values less than the pivot, and values greater than or equal to the pivot. Each of those groups becomes a new (smaller) sub-list, and the process repeats inside each one, picking a new pivot each time — until every single item has, at some point, been chosen as a pivot.
The three-step method (ascending order)
- Step 1: Find and highlight the pivot (middle value) of each current sub-list.
- Step 2: List items less than the pivot first (in their original order), then the pivot itself, then items greater than or equal to the pivot (in their original order). This creates two new sub-lists either side of the pivot.
- Step 3: Repeat steps 1–2 on every new sub-list until every item has been used as a pivot. For descending order, just flip which side "greater" and "less" values go on.
Sort 5, 3, 7, 2, 4, 5, 9, 6 into descending order.
Pass 1 — 8 items, pivot = 5th value = 4
Greater-than-pivot items first (descending), then pivot, then smaller items:
5, 7, 5, 9, 6, 4, 3, 2
Pass 2 — new sub-lists: {5,7,5,9,6} and {3,2}. Pivots: 5 (upper-middle of first) and 2.
7, 9, 6, 5, 5, 4, 3, 2
Pass 3 — sub-list {7,9,6}, pivot = 6 (no reordering needed); {3} already alone.
Pass 4 — sub-list {7,9}, pivot = 9 (upper position): → 9, 7
Pass 5 — {7} alone, becomes its own pivot.
Final sorted list: 9, 7, 6, 5, 5, 4, 3, 2
Perform pass 1 of quick sort (ascending order) on the list: 12, 4, 9, 15, 6, 20, 3. Identify the pivot and show the list after pass 1.
4. Bin Packing Algorithms
Bin packing is about fitting a set of objects into as few equal-sized bins as possible. Think of loading identical delivery vans with parcels of different weights, or cutting short cable lengths from large reels — you want to use the fewest vans/reels possible. "Packing" here is a loose word: it could mean separating, cutting, stacking, or loading.
All three bin packing algorithms in this chapter are heuristic — meaning they give you a good, workable solution, but not necessarily the optimal (best possible) one, and not necessarily the only correct-looking answer.
4.1 The Lower Bound
Before packing anything, you can calculate the theoretical minimum number of bins you could possibly need — this is the lower bound. It's found by dividing the total size of all the objects by the size of one bin, then rounding up to the next whole number (since you can't have a fraction of a bin).
4.2 First-Fit Bin Packing
This is the simplest and fastest method: objects are packed in the order they're given — no sorting first. Each object goes into the first bin that has room for it. If it doesn't fit in bin 1, try bin 2, then bin 3, and so on, opening a brand-new bin only when nothing existing has space.
Its big advantage: speed. No time wasted sorting the list first. Its downside: it often uses more bins than truly necessary.
Weights (kg): 12, 16, 18, 8, 16, 12, 10, 4, 6, 10, 12, 16, 20, 10, 24. Each shelf holds 40 kg.
Lower bound: total = 194, 194 ÷ 40 = 4.85 → LB = 5
| Shelf | Items placed (in original order) | |||
|---|---|---|---|---|
| 1 | 12 | 16 | 8 | 4 |
| 2 | 18 | 16 | 6 | |
| 3 | 12 | 10 | 10 | |
| 4 | 12 | 16 | 10 | |
| 5 | 20 | |||
| 6 | 24 | |||
First-fit uses 6 shelves — one more than the lower bound of 5. This shows first-fit doesn't always find the optimal solution.
4.3 First-Fit Decreasing Bin Packing
Exactly the same packing rule as first-fit — except you first sort the objects into decreasing (descending) order before packing them. Placing the biggest items first tends to leave more useful gaps for the smaller items later, which usually gets you much closer to (or exactly at) the optimal number of bins.
Same weights, now pre-sorted descending: 24, 20, 18, 16, 16, 16, 12, 12, 12, 10, 10, 10, 8, 6, 4. Shelf capacity 40 kg. Lower bound = 5.
| Shelf | Items placed | |||
|---|---|---|---|---|
| 1 | 24 | 16 | ||
| 2 | 20 | 18 | ||
| 3 | 16 | 16 | 8 | |
| 4 | 12 | 12 | 12 | 4 |
| 5 | 10 | 10 | 10 | 6 |
This uses exactly 5 shelves — matching the lower bound, so this solution is optimal!
Objects of size 7, 5, 4, 9, 3, 6 are to be packed into bins of capacity 12 using first-fit (in the order given). List the contents of each bin.
4.4 Full-Bin Packing
This method takes a completely different approach: instead of working through objects in a fixed order, you inspect the whole list to spot combinations of objects that add up exactly to the bin's capacity, and pack those combinations first. Any objects left over (that can't be grouped into an exact-fit combination) are then packed using the ordinary first-fit method.
Full-bin packing often finds the optimal solution — but it can be slow and time-consuming for long lists, since you're hunting for combinations "by eye." It's not suitable when speed matters more than getting the perfect answer.
Same weights: 12, 16, 18, 8, 16, 12, 10, 4, 6, 10, 12, 16, 20, 10, 24. Shelf capacity 40 kg.
Spot combinations that add to exactly 40:
| Shelf | Items | Sum | |||
|---|---|---|---|---|---|
| 1 | 12 | 12 | 16 | 40 | |
| 2 | 8 | 10 | 10 | 12 | 40 |
| 3 | 16 | 24 | 40 | ||
| 4 | 16 | 20 | 4 | 40 | |
Remaining objects, in original order: 18, 6, 10. These all fit together in one more shelf (18+6+10=34 ≤ 40), packed via first-fit:
| Shelf | Items | ||
|---|---|---|---|
| 5 | 18 | 6 | 10 |
5 shelves used — matches the lower bound, so this is optimal!
Objects 5, 7, 3, 8, 2, 6, 9 are to be packed into bins of capacity 15 using full-bin packing. Find at least one full-bin combination, then pack the rest with first-fit.
What to Memorise
Concepts Checklist
Exam Tips & Common Mistakes
Typical exam question patterns
- Trace a flow chart / pseudocode algorithm through a table for a given input, then state the output.
- State the maximum number of passes/comparisons/swaps for bubble sort on a list of n items.
- Perform a specific pass of bubble sort given the list state after a previous pass.
- Perform the full quick sort algorithm on a list, clearly marking pivots at each stage.
- Calculate a lower bound, then apply first-fit / first-fit decreasing / full-bin packing and compare to the lower bound to discuss optimality.
- Estimate an algorithm's completion time on a larger input, given its order and a known time for a smaller input.
Edexcel A Level Further Maths — Decision 1 · Algorithms · Revision Guide
- Exam Tips & Common Mistakes
Read the full Algorithms notes free
That's the preview — create a free account to read the rest, plus flashcards and practice questions with instant AI marking. No credit card.
Unlock the full notes free →