1
Every step must be unambiguous
"Choose a good pivot" is not a step. If two people executing the description could do different things, it is not an algorithm.
Lesson · Algorithms and Complexity · Foundations
Algorithms and Pseudocode
An algorithm is a finite sequence of precise steps producing an output from an input. Pseudocode is how it is communicated: precise enough to analyse, free of the details of any language.
INPUT DEFINITENESS FINITENESS OUTPUT EFFECTIVENESS
pseudocode: precise about the method, silent about the language
the same problem admits many algorithms
correctness first, efficiency second
Five requirements
Core ideas
What this lesson establishes
The definition rules out things that look like algorithms and are not, and each requirement rules out a specific failure.
2
It must terminate
On every valid input. A procedure that may run forever is not an algorithm, however useful it is.
3
Pseudocode is for humans
Detailed enough to analyse and implement, free of syntax. Analysis is about the method, not the language.
The material
What an algorithm is
The five requirements, pseudocode conventions, and one problem solved three ways.
Definition · Algorithm
A finite sequence of precise instructions transforming an input into an output. It must have: input from a specified set; definiteness, every step unambiguous; finiteness, terminating after finitely many steps; output in a specified relation to the input; and effectiveness, every step performable exactly.
Each requirement excludes something real. Definiteness excludes "pick a suitable value"; finiteness excludes a loop that may never exit; effectiveness excludes "decide whether this program halts", which “Decidability and the Halting Problem” shows is not performable at all.
Pseudocode
MAXIMUM(a₁, …, aₙ):
max = a₁
for i = 2 to n:
if aᵢ > max: max = aᵢ
return max
The conventions used on this course: indentation for blocks, = for assignment, ← avoided, one-based indexing, and enough English to keep it readable. Nothing depends on a language, and the analysis of “Analysing Iterative Algorithms” counts the comparisons regardless of how it is implemented.
One problem, three algorithms
Computing xⁿ for a positive integer n:
A. repeated multiplication n − 1 multiplications
result = x
repeat n−1 times: result = result · x
B. repeated squaring about 2·log₂ n multiplications
as in “Modular Exponentiation” in Number Theory and Cryptography
C. addition-chain exponentiation slightly fewer than B, sometimes
precompute an optimal chain of products
All three are correct and they differ enormously in cost. At n = 1000, A performs 999 multiplications and B performs about 15. That gap is the subject of this course, and it is a property of the algorithm rather than of the machine.
Correctness before efficiency
An algorithm that is fast and wrong is worthless, and the order of work is therefore fixed: establish correctness (“Correctness and Termination”), then measure cost (growth rates, asymptotic bounds, iterative analysis, searching and sorting, divide and conquer, recursion trees and amortised analysis), then look for a better method (“Greedy Algorithms” and “Dynamic Programming”).
The order is worth stating because the temptation runs the other way. Optimising an algorithm before knowing it is right produces a faster wrong answer, and the speed makes the error harder to find.
Interactive
Algorithms and growth
Counts from running, not from quoting
Method
Writing an algorithm down
State the contract before the steps.
1
State the input and the output
What is given, what is produced, and the relation between them. This is the specification, and “Correctness and Termination” proves the algorithm meets it.
2
Write the steps unambiguously
No step may require judgement. If it does, it is a subproblem needing its own algorithm.
3
Check it terminates on every valid input
Exhibit a quantity that strictly decreases and is bounded below, as in “Recursive Algorithms and Correctness” in Induction and Recursion.
4
Only then consider the cost
Count the dominant operation as a function of the input size. That is “Analysing Iterative Algorithms”.
Algorithms
Score 0 / 0Choose the answer you can justify.
Specifying and writing linear search
The specification is the part usually skipped.
INPUT a list a₁ … aₙ and a value x
OUTPUT an index i with aᵢ = x, or 0 if x does not occur
LINEAR-SEARCH(a, x):
for i = 1 to n:
if aᵢ = x: return i
return 0
definiteness every step is a comparison or a return ✓
finiteness the loop runs at most n times ✓
output returns an index or 0, as specified ✓
cost n comparisons in the worst case
The specification says "an index", not "the first index". If the caller needs the first occurrence that must be stated, because it constrains which algorithms are acceptable — binary search on a sorted list with duplicates does not guarantee it without modification.
Common mistakes
1
Leaving a step to judgement"Pick a good pivot" hides an entire algorithm. Every step must be mechanically performable.
2
Optimising before proving correctA faster wrong answer is worse than a slow right one, and the speed makes the error harder to notice.
3
Specifying the output loosely"Find the element" leaves open whether the first, any, or all occurrences are wanted, and different algorithms answer different questions.
Check your understanding
✓
Finish when you write the specification before the pseudocode.
Specify and write an algorithm that returns the two largest values in a list. State what happens when the list has fewer than two elements — the edge case the specification exists to settle.
Note: "Algorithm" comes from al-Khwārizmī, the ninth-century mathematician whose book on Hindu–Arabic numerals gave Europe both the word and the method of calculation. "Algebra" comes from the title of another of his works.