Algorithms, explained, proved and run.
Each page explains one algorithm or idea in plain words. It gives the pseudocode, a proof that you can check, the cost, code with tests in many languages and a picture that you can step through.
Search 8 pages⌘K- 3 algorithms
- 0 data structures
- 2 problems
- 3 proofs
- 30 implementations in 10 languages
- 3 scenes
Start here
The full reading path- Binary search
Find a key in a sorted array. Compare the key with the middle item, and keep only the half that can hold the key.
10 languagesvisualintro - Insertion sort
Sort an array one item at a time. Take the next item and move it left until the item before it is not larger.
10 languagesvisualintro - Loop invariant
A statement about the variables of a loop that is true before each step. It is the main tool to prove that a loop is correct.
intro - Merge sort
Sort an array by divide and conquer. Sort each half, then merge the two sorted halves into one sorted array.
10 languagesvisualintro - Search in a sorted array
Given a sorted array and a key, find an index of the key, or report that the key is not in the array.
intro - Sorting
Put the items of a sequence in non-decreasing order by a key.
intro
See it run
All scenes- Binary searchFind a key in a sorted array. Compare the key with the middle item, and keep only the half that can hold the key.
- Insertion sortSort an array one item at a time. Take the next item and move it left until the item before it is not larger.
- Merge sortSort an array by divide and conquer. Sort each half, then merge the two sorted halves into one sorted array.
Areas
All areas- FoundationsThe models, the measures and the proof methods that the rest of the site uses.
- TechniquesThe general methods of algorithm design, such as divide and conquer and dynamic programming.
- Data structuresThe ways to store data so that the operations on it are fast.
- SortingAlgorithms that put items in order, and the problems near sorting.
- SearchingAlgorithms that find an item, or a value with a property, in a collection.
- SequencesProblems on arrays and sequences, such as sums, subarrays, subsequences and intervals.
- GraphsAlgorithms on graphs and trees, such as traversal, paths, flows and matching.
- StringsAlgorithms that match, index and compare strings.
- Automata and parsingFinite automata, regular expressions and parsers.
- Number theoryAlgorithms on integers, such as divisibility, primes, modular arithmetic and factoring.
- AlgebraExact arithmetic on numbers, polynomials and matrices, and fast transforms.
- NumericalAlgorithms on real numbers in floating point.
- GeometryAlgorithms on points, lines and shapes in the plane and in space.
- CombinatoricsAlgorithms that generate and count combinatorial objects.
- OptimizationAlgorithms that find the best solution under constraints.
- Logic and constraintsSolvers for logic formulas and constraint problems.
- RandomizedAlgorithms that use random choices, and how to analyse them.
- ApproximationAlgorithms that find a near-best solution with a proved bound.
- Online and streamingAlgorithms that get the input one item at a time.
- ParallelAlgorithms for many processors that share memory or work in bulk steps.
- DistributedAlgorithms for many machines that send messages to each other.
- ConcurrencyAlgorithms for threads that share memory at the same time.
- CryptographyAlgorithms that keep data secret and prove who sent it.
- Compression and codingAlgorithms that make data smaller, or protect it from errors.
- Machine learningAlgorithms that learn a model from data.
- SystemsAlgorithms inside operating systems, databases and networks.
- BiologyAlgorithms for sequences and structures in biology.
- Graphics and signalsAlgorithms for images, curves, rendering and signals.
- Games and searchAlgorithms that play games, plan and solve puzzles.
- QuantumAlgorithms for quantum computers.
- ComplexityWhat each problem needs, with classes, reductions and lower bounds.
Languages
All languagesHow a page earns trust
- Plain words. The text uses short sentences and simple words. A reader who knows some code can follow it.
- Proof. A human proof shows why the algorithm is correct. A Lean proof lets a computer check it.
- Tests. Each implementation has native tests. The build runs them in a pinned toolchain.
- Honest badges. The build computes each badge from evidence. Nobody writes a badge by hand. Read about the badges.