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,396 pages⌘K- 2,629 algorithms
- 432 data structures
- 1,614 problems
- 2,410 proofs
- 2,719 implementations in 10 languages
- 3 scenes
Start here
The full reading path- 0-1 BFS
Shortest paths in graphs with weights 0 or 1 using a deque, in linear time.
1 languagesintro - 1/e stopping rule
Observe the first ⌊n/e⌋ candidates without hiring, then hire the first one who is better than all before. It hires the best with probability tending to 1/e.
1 languagesintro - 2-SAT
SAT where each clause has at most two literals. It is solvable in linear time with the implication graph, while its counting and maximization versions are hard.
intro - 2-SAT algorithm
Solve 2-SAT in linear time. Find the strongly connected components of the implication graph; UNSAT when a variable and its negation share one, else read a model from their order.
1 languagesintro - 2P-Set
A replicated set built from two grow-only sets, one of added and one of removed elements. Remove wins over a concurrent add, and a removed element can never be added again.
1 languagesintro - 3-SAT
SAT restricted to clauses of at most three literals. It is NP-complete by Karp's reduction from SAT, and the best known algorithms take about 1.307^n time.
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.