Algorithmics §
Algorithmics studies what can be computed, how data is organized for efficient access, and how procedures transform data into results. It is relevant whenever a problem must be decided, represented, solved, or optimized before implementation.
Utility §
- It formalizes what can be computed and what cannot.
- It chooses data representations that make operations cheap.
- It designs algorithms and bounds their time and space cost.
- It optimizes continuous and discrete objectives.
Details
Algorithmics sits at the leftmost end of the computation pipeline: it takes a problem statement and produces a precise procedure with a provable cost bound. The sub-areas are tightly coupled: the choice of data structure (a representation) determines which algorithms are efficient, and the complexity of the algorithm determines whether the problem is tractable at scale. Optimization extends this to continuous settings where the “algorithm” is an iterative procedure whose convergence rate replaces the discrete step count, and learning adds a statistical layer on top of optimization to map data to predictions.
History §
- 1936: Turing formalizes computation with Turing machines.
- 1972: Karp’s 21 NP-complete problems clarify the landscape of hard combinatorial problems.
- 1990s: LSM-trees and B-trees mature as the dominant key-value storage structures.
- 2010s: Deep learning makes gradient descent and neural architectures central to algorithmics.
Classes §
| Page | Core object | Key metric | Boundary |
|---|---|---|---|
| Computability and Complexity Classes | Turing machines, decidability, P/NP, complexity classes | Decidability, P/NP membership, asymptotic bounds | What is computable and at what asymptotic cost; does not choose a concrete data structure |
| Space and Parallel Complexity | Space complexity classes (L, NL, PSPACE, EXPSPACE), hierarchy theorems, circuit complexity, NC hierarchy | Space bounds, circuit depth, parallel speedup | Theoretical limits on memory and parallelism; does not model physical hardware caches or design concrete parallel algorithms |
| Search and data structures | Lists, key-value stores, text search, database theory, graphs | Access time, space, cache locality | How to organize data for cheap access; does not model the physical memory hierarchy |
| Optimization and differentiation | Gradients, iterative solvers, convexity | Convergence rate, loss | How to find a minimum of a differentiable objective; does not specify how to encode or transmit the solution |
| Learning paradigms and models | Neural architectures, losses, data paradigms, compute | Perplexity, parameter count, generalization | How to map data to predictions with a parametric model; does not specify how to compute gradients efficiently |
Authoritative sources