Concept

Algorithm

A finite procedure of precisely stated steps that takes an input and is guaranteed to stop with an answer. What usually matters about one is how many steps it needs as the input grows, which decides whether it can be run on large cases at all.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

A cheapest assignment, and the proof that it is cheapest. A 4 by 4 cost table with the cheapest assignment marked, and a row price and column price beside each. Every used cell's two prices add to its cost, and the prices total the assignment's cost.

A price for every person and task

The cheapest assignment can be found without comparing it to any other. Attach a number to each person and each task so that no pair's two numbers exceed its cost, and if the numbers add to an assignment's total, that assignment is cheapest — proved, by an argument that never mentions the alternatives.

applied · Assignment

Bhāskara's cyclic method on x² − 61y² = 1, step by step. A table of the cyclic method's rows: the helper m chosen at each step and the near miss a² − Db² = k it produces, ending at k = 1 with the fundamental solution.

A method that is allowed to miss

Bhāskara's cyclic method solves x² − Dy² = 1 by aiming at the wrong target. It keeps a pair a, b with a² − Db² = k for some small k, combines it with a helper chosen so that k can be divided out, and repeats until k is 1. For D = 61 it reaches the ten-digit fundamental solution in 13 steps, where walking the convergents of √61 takes 22 — and for every D up to 100 it is faster.

number · Pell

Named alongside it

The objects these essays reach for when they reach for this one.

Assignment Certificate Complementary slackness Continued fractions Convergent Duality Fundamental solution Linear programming Matching Modular arithmetic Optimisation Pell equation

All concepts