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.
Stay in "Robot Mode"
Exam questions usually use small lists, so it's tempting to just "see" the answer using common
sense. Don't. You get marks for showing that you followed the algorithm's exact steps — not for
getting the right final number. Write down every value the algorithm tells you to, and state the
output separately at the end, even if it feels obvious.
Optimal vs. sufficient solutions
optimal
good enough
speed/efficiency
accuracy
Worked Example — Following a Flow Chart
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 |
| 5 |