Topics
Logic, probability, theory of computation, graphs and optimisation: the mathematics beneath computing, explained at the blackboard.
Discrete mathematics
Logic, sets, relations, induction, combinatorics and modular arithmetic with concrete examples.
Probability & statistics
Probability, distributions, samples, tests, correlation and the most common statistical mistakes.
Theory of computation
Automata, formal languages, Turing machines, computability, complexity and P versus NP.
Graphs & optimisation
Shortest paths, trees, flows, linear and dynamic programming, heuristics and metaheuristics.
Featured articles
Check digits: Luhn, ISBN and IBAN explained with remainders
How check digits work for payment cards, ISBNs and IBANs: the Luhn algorithm, weights modulo 10 and 11, the modulo 97 check, and which errors they catch.
Bayes' theorem and false positives: the diagnostic test case
Bayes' theorem applied to a test with 99% sensitivity: why a positive result can be wrong in 5 cases out of 6 and how to update the estimate step by step.
Approximation with guarantees: when the optimum is NP-hard
Approximation ratios, guaranteed algorithms for vertex cover and the travelling salesman, schemes for knapsack and the limits proved by inapproximability.
The A* algorithm: pathfinding with an admissible heuristic
A* combines Dijkstra with an estimate of the remaining distance: admissible and consistent heuristics, Manhattan distance, grids and speed trade-offs.
Equivalence relations, classes and partitions of a set
Equivalence relations, equivalence classes and partitions: how the three ideas connect, concrete examples, and the union-find structure for computing them.
Conditional probability and independence explained with examples
How to compute conditional probability, what independence between events really means and why confusing P(A|B) with P(B|A) leads to serious mistakes.
The class P: what solving in polynomial time really means
Definition of the class P, why polynomial time is the boundary of tractability, the role of input encoding and why pseudo-polynomial ones fall short.
Dijkstra's algorithm: shortest paths with non-negative weights
How Dijkstra's algorithm works: relaxation, a heap-based priority queue, why it needs non-negative weights and how to apply it to real maps and networks.
Injective, surjective and bijective functions with examples
Domain, codomain and image; when a function is injective, surjective or bijective, how to invert it, and why it matters for hashes, keys and encodings.
Mean, median and mode: which measure to use and when
Arithmetic mean, median, mode, trimmed, geometric and harmonic mean: how to compute them, how they react to extremes and which to choose case by case.
The halting problem: why it is undecidable
The diagonalization proof that no algorithm can decide whether a program halts, explained step by step, with its practical consequences for software.
Graph colouring: timetables, frequencies and registers without clashes
Graph colouring applied to exam timetables, radio frequencies and register allocation: chromatic number, the greedy algorithm, DSatur and practical limits.