Algorithms

Discrete Mathematics analysed algorithms and never built a structure to run one on. This course builds eight, and costs each by executing an operation sequence rather than by quoting a class — because the interesting facts here are all about the difference between a worst case, an amortised bound and an expectation, and those three are indistinguishable from a single fast run.

Discrete Mathematics proved no comparison sort beats n log n. That leaves open everything that matters: stability, whether the bound applies at all, what randomness buys, and how close to the bound a real sort gets. This is also the course where the analysis becomes probabilistic — randomised quicksort's exact expectation is the pattern every later expectation on this path follows.

Discrete Mathematics defined graphs and ran two algorithms on them. This course builds eleven, proves each correct, and counts what each one does on the graph you type. It is also where an algorithm first certifies its own answer: everywhere else on this path a lesson puts a measured count beside a proved bound, and here the maximum flow comes back with a cut of equal capacity attached.

This is the one course on the path where a lesson can do better than putting a measured count beside a proved bound. A greedy rule commits to a choice and never revisits it, so on a small instance the optimum is enumerable — and every verdict here is computed twice, once by running the rule and once by a search that has never heard of it. When the two disagree the lab names the subset that beats the rule, which is what a counterexample looks like when it is produced rather than quoted.

Greedy Algorithms and Matroids proved a rule correct wherever the structure allowed it. This course is what to do where it does not: the same optimal substructure, without the greedy choice property, evaluated by filling a table. Every page runs the table against at least one route that has no table in it — an exhaustive search, a memo-free recursion, or a re-costing of the object that came back — because a filled table is the easiest thing on this path to get confidently wrong.

This is the course where the asymptotically better algorithm loses, three times, on inputs one click apart. Naive matching beats Knuth–Morris–Pratt on prose with an absent pattern; Horspool beats both by a factor of three on English and loses to naive matching by a factor of five on a run of one letter; a rolling hash reports three positions that are not matches until the characters are compared. None of the bounds moves while any of that happens, and every page prints both columns.

Every other course on this path measures an algorithm. This one measures a PREDICATE: the same orientation test in exact integers and in double precision, on 29 magnitudes of the same input, with the wrong answers counted rather than warned about. The failure turns out to have a shape — the rounded test can lose a turn and provably cannot invent the opposite one — and the rest of the course is what that sign is used for, with degenerate input treated as the subject rather than excluded from it.

Everywhere else on this path a measured count sits beside a proved bound. Here the thing being bounded is itself random, and the easiest mistake in the subject is to run an algorithm a hundred times, take the average, and call it the expectation. So the labs enumerate: every tape of a shuffle, every execution of a quicksort, every contraction order, every base, every assignment. The exact fraction and the sample sit in the same row, and the gap between them is what the course is about.

Every course so far built algorithms that work. This one starts where none is known to, and it does two things with that. First it makes hardness constructive: a reduction is a construction, so each one here is built in front of you, both instances are solved exhaustively, and the map between their solution sets is checked for soundness, for injectivity and for surjectivity as three separate questions — because two of them have answers that change with the instance. Then it builds the six things that can honestly be done instead, and for each one it prints the algorithm's answer, the true optimum from an exhaustive search, the realised ratio and the promise, on one axis.