Algorithms
D1 Topic 1, spec point by spec point (Algorithms). Each spec point has the method, worked examples written the way the mark scheme wants them, how the marks go and the mistakes that cost the most marks.
The D1 paper (WDM11) is 1 hour 30 minutes and 75 marks, with an answer book that has the diagrams and tables printed for you. Method marks depend on showing the algorithm working (the order you choose arcs, the working values, each pass of a sort), not just the final answer.
How maths marks work
M marks are for a correct method, even with a slip in the numbers. A marks are for accurate answers and need the M mark before them. B marks stand alone (a value or a statement). dM means the method mark depends on an earlier M mark.
ft (follow through) lets a later mark be earned from your own earlier wrong value. cso (correct solution only) means every step must be right, which is common on "show that" answers. awrt means "answers which round to", so keep extra figures and round at the end. isw means extra working after a correct answer is ignored.
When a question says "use algebra", "show all stages of your working" or "solutions relying on calculator technology are not acceptable", an answer with no method scores nothing, even if it is right.
Each spec point below has the idea behind it first, then the method, worked examples written the way a mark scheme would want, how the marks go, and the mistakes that cost the most marks. The paper references, such as (WMA11 Jan 2022 Q4), are past questions from the IAL Prep question bank that use the point.
Spec1.1Algorithms and flowcharts
The general ideas of algorithms, and carrying out an algorithm given as a flowchart or as text. (The order of an algorithm is not expected.)
The idea
An algorithm is a finite list of precise instructions that solves a problem. In D1 you'll be given one (as numbered steps or a flowchart) and asked to carry it out exactly, recording every value in a trace table, then say what it does.
How to trace an algorithm
- Make a column for every variable (and one for the output or any yes/no decision).
- Work line by line. Write a new value only when a step changes it.
- At a decision box, write the answer (yes or no) and follow the right arrow.
- Stop when the algorithm says stop, and state the output.
The middle item rule (used in every D1 algorithm that needs a "middle"): in a list of \(N\) items, the middle is position \(\frac{N + 1}{2}\) if \(N\) is odd and \(\frac{N + 2}{2}\) if \(N\) is even. In other words, round up. So for \(N = 9\) it's the 5th, and for \(N = 6\) it's the 4th.
trace and interpret
Algorithm: 1. Input \(A\). 2. Let \(x = \frac{A}{2}\). 3. Let \(y = \frac12\left(x + \frac{A}{x}\right)\). 4. If \(\lvert y - x \rvert < 0.01\), output \(y\) and stop. 5. Let \(x = y\) and go to step 3.
Trace with \(A = 20\) (to 4 d.p.):
| \(x\) | \(y\) | \(\lvert y - x \rvert < 0.01\)? |
|---|---|---|
| 10 | 6 | no |
| 6 | 4.6667 | no |
| 4.6667 | 4.4762 | no |
| 4.4762 | 4.4721 | yes |
Output 4.472. The algorithm finds \(\sqrt{A}\) (here \(\sqrt{20} = 4.472\)).
- M1 for completing the first row, A1 first three rows correct, A1ft the next rows, A1 cso the output (WDM11 Jun 2026 Q2a). Leaving out the "no" entries at a decision can lose the final mark.
- "Explain what the algorithm does": state it precisely, e.g. "\(h\) is the lowest common multiple of \(a\) and \(b\)". "The product of \(a\) and \(b\)" is wrong (WDM11 Jan 2025 Q3b).
Often asked as: complete a trace table; state the output; say what the algorithm does; say what happens with a different input.
Skipping rows or overwriting values, so the examiner can't follow your working.
Rounding to fewer decimal places than the question asks for.
Spec1.2Sorting, searching and bin packing
Bin packing, bubble sort, quick sort and binary search. For quick sort, the pivot is the middle item of the list.
Bubble sort
Work from the left. Compare each adjacent pair and swap if they're in the wrong order. After one pass, the last item is fixed. Repeat until a pass makes no swaps: that final pass must be shown.
Quick sort
- Choose the middle item as the pivot.
- Write the items that belong before it (larger, for descending) in their original order, then the pivot, then the rest (in original order).
- Each sublist then gets its own pivot (its middle item) in the next pass. Continue until every item has been a pivot or is alone.
Show the list after every pass and mark the pivots (e.g. underline or circle them).
Binary search (on an ordered list)
- Find the middle item of the current list (round up: \(\left[\frac{\text{first} + \text{last}}{2}\right]\)).
- If it's the target, stop. If the target comes before it, discard the middle item and everything after; otherwise discard it and everything before.
- Repeat on what's left. If the list becomes empty, the item isn't there.
Bin packing
| Method | How it works |
|---|---|
| First fit | take items in the given order; put each in the first bin it fits |
| First fit decreasing | sort into descending order first, then first fit |
| Full bin | look for combinations that fill bins exactly, then first fit the rest |
Lower bound for the number of bins \(= \dfrac{\text{total size}}{\text{bin capacity}}\), rounded up. If a method reaches the lower bound, it's optimal.
First fit is quick but usually not optimal. First fit decreasing usually does better. Full bin often gives good solutions but is hard with many items.
bubble sort (descending)
14, 27, 8, 19, 31, 12.
Pass 1: 27, 14, 19, 31, 12, 8
Pass 2: 27, 19, 31, 14, 12, 8
Pass 3: 27, 31, 19, 14, 12, 8
Pass 4: 31, 27, 19, 14, 12, 8
Pass 5: no swaps, so the list is sorted.
quick sort (descending)
22, 37, 15, 41, 28, 9, 33, 17, 25. Nine items, so the first pivot is the 5th: 28.
Pass 1 (pivot 28): 37, 41, 33, 28, 22, 15, 9, 17, 25
Pass 2 (pivots 41 and 9): 41, 37, 33, 28, 22, 15, 17, 25, 9
Pass 3 (pivots 33 and 17): 41, 37, 33, 28, 22, 25, 17, 15, 9
Pass 4 (pivot 25): 41, 37, 33, 28, 25, 22, 17, 15, 9. Sorted.
binary search
Find Jade in: 1 Ahmed, 2 Bella, 3 Chen, 4 Dara, 5 Ella, 6 Farid, 7 Grace, 8 Hana, 9 Ivan, 10 Jade, 11 Kofi.
\(\left[\frac{1 + 11}{2}\right] = 6\): Farid. Jade is after it, so keep 7 to 11.
\(\left[\frac{7 + 11}{2}\right] = 9\): Ivan. Keep 10 to 11.
\(\left[\frac{10 + 11}{2}\right] = 11\) (10.5 rounded up): Kofi. Jade is before it, so keep 10.
Middle of a one-item list is 10: Jade. Found.
bin packing
Bins of size 20; items 8, 7, 14, 9, 6, 9, 5, 15, 6, 7, 8.
Lower bound: \(\frac{94}{20} = 4.7\), so 5 bins.
First fit: [8, 7, 5], [14, 6], [9, 9], [15], [6, 7], [8]: 6 bins.
First fit decreasing (15, 14, 9, 9, 8, 8, 7, 7, 6, 6, 5): [15, 5], [14, 6], [9, 9], [8, 8], [7, 7, 6]: 5 bins, which equals the lower bound, so this is optimal.
- Lower bound: M1 for total ÷ capacity, A1 for the rounded-up answer with the calculation seen. A bare answer scores M0 (WDM11A Jan 2026 Q1a).
- Quick sort: M1 for the middle item as pivot and a correct first pass, A1 first and second passes, A1ft later passes, A1 cso. Using the first or last item as pivot, or a bubble sort, is M0 (WDM11 Jan 2025 Q1b).
- Bubble sort: M1 consistent direction with the right first pass, A1 A1ft for the passes, A1 cso including a final pass with no swaps (WDM11 Jun 2021 Q1c).
- Identifying a pivot after one pass needs a two-sided reason: larger items all on one side and smaller all on the other (WDM11 Jun 2023 Q2a).
Often asked as: the most examined D1 point (69 questions). Nearly every paper opens with a sort, a search or bin packing.
Taking the pivot as the first item, or rounding the middle position down.
Reordering items within a sublist during quick sort.
Stopping a bubble sort without showing the pass with no swaps.