The Ledger — An Illustrated Handbook of Data Structures and Algorithms

An illustrated handbook of data structures and algorithms. Every chapter is an animation you scroll through at your own pace, written from primary sources and cited by DOI.

Published chapters

27 of 404 planned

Bloom Filter

Probabilistic membership: probably yes, definitely no.

Read chapter

Union-Find

Merge sets, compress paths, answer connectivity fast.

Read chapter

Ring Buffer

Fixed-size queues for streams, logs, and low-latency systems.

Read chapter

Priority Queue

Always pull the highest-priority item next.

Read chapter

Deque

Push and pop efficiently from both ends.

Read chapter

Skip List

Ordered search with coin-flip express lanes.

Read chapter

Treap

A randomized binary search tree with heap priorities.

Read chapter

Splay Tree

A search tree shaped by the keys accessed most recently.

Read chapter

Van Emde Boas Tree

Integer-key operations in doubly logarithmic time.

Read chapter

Red-Black Tree

Balanced search with strict coloring invariants.

Read chapter

AVL Tree

Height-balanced search with strict local invariants.

Read chapter

Scapegoat Tree

Rebuild unbalanced subtrees instead of storing balance metadata.

Read chapter

Binary Heap

The compact array-backed priority queue.

Read chapter

Binomial Heap

A forest of power-of-two heaps built for merging.

Read chapter

Fibonacci Heap

Lazy merging with excellent amortized graph operations.

Read chapter

Pairing Heap

A practical meldable heap with simple pointer structure.

Read chapter

Tournament Tree

Keep winners visible while merging many sorted streams.

Read chapter

Trie

Prefix search, autocomplete, routing tables, and dictionaries.

Read chapter

Rope

A text buffer structure for large editable documents.

Read chapter

Zipper

Navigate and edit immutable trees with local focus.

Read chapter

LSM Tree

Append now, sort in memory, merge the debt later.

Read chapter

Big-O Notation

Describe growth rates without counting machine cycles.

Read chapter

Amortized Analysis

Charge expensive operations against the cheap ones around them.

Read chapter

Recurrence Relations

Solve the cost of algorithms that call themselves.

Read chapter

Master Theorem

Read off the complexity of divide-and-conquer recurrences.

Read chapter

Space Complexity

Account for auxiliary memory, not just running time.

Read chapter

Loop Invariants

Prove a loop correct by stating what never changes.

Read chapter

Part One

Data Structures

How data is arranged in memory and on disk, and what each arrangement costs.

Vol. I

Foundations

The small structures that show up everywhere else.

20 published 23 topics

Sets, Queues, And Membership

Ordered Search Structures

Heaps And Merge Structures

Text And Functional Structures

Trie Prefix search, autocomplete, routing tables, and dictionaries.
Rope A text buffer structure for large editable documents.
Zipper Navigate and edit immutable trees with local focus.
Persistent Data Structures Keep old versions without copying the whole world.
Finger Tree A functional sequence structure for fast access near fingers.
HAMT Hash-array mapped tries for persistent maps and sets.

Vol. II

Databases

Indexes, logs, filters, and storage layouts behind real engines.

1 published 32 topics

Write-Heavy Storage

LSM Tree Append now, sort in memory, merge the debt later.
Write-Ahead Log Durability before mutation: the recovery backbone.
Bitcask / Hash Index Append-only files with an in-memory key directory.

Advanced Write-Heavy Indexes

Cuckoo Filter A deletable membership filter for storage engines.
Bloom Filter Cascade Layered filters for multi-level LSM lookups.
Masstree A cache-conscious trie of B+ trees for modern hardware.
Log-Structured Merge Forest Many LSMs working together instead of one tree.
Fractal Tree Index Buffer updates inside a tree to reduce random writes.
Bw-Tree A latch-free B-tree variant built from delta records.

Read-Heavy Storage

B+ Tree The classic page-oriented index for range scans.
B-tree vs LSM Tree Why reads, writes, and compaction trade places.
Roaring Bitmap Compressed posting lists and fast set operations.
Segment Tree Range queries with logarithmic updates.
Fenwick Tree Compact prefix sums for mutable numeric data.
Zone Map Skip blocks by storing min/max summaries per chunk.
Sparse Index Index representative keys instead of every row.

Columnar And Analytical Layouts

Column Store Store each field separately for scans and compression.
Dictionary Encoding Replace repeated values with compact integer ids.
Run-Length Encoding Compress repeated values as value and count pairs.
Bitmap Index Use bitsets to answer analytical filters quickly.

Caches And Memory Indexes

LRU Cache Evict the least recently touched item.
LFU Cache Evict by access frequency instead of recency.
ARC Cache Balance recent and frequent access patterns adaptively.
Clock Cache Approximate LRU with a circular reference-bit scan.
Slab Allocator Group fixed-size allocations for predictable memory reuse.

Search And Vector Indexes

TF-IDF / BM25 The scoring model behind practical keyword search.
Suffix Array / Suffix Tree Substring search without scanning every character.
Aho-Corasick Automaton Match many patterns in one pass.
HNSW Graph Approximate nearest-neighbor search at scale.
Locality-Sensitive Hashing Put similar vectors into the same buckets.
IVF Index Partition vector space into coarse clusters before search.
Product Quantization Compress vectors into codebooks for fast approximate search.

Vol. III

Distributed Systems

Data representations for partitioning, causality, replication state, and distributed logs.

19 topics

Partitioning And Placement

Hash Ring Represent key ownership around a circular token space.
Partition Map Map key ranges or shards to replica owners.
Virtual Nodes Smooth load across uneven machines in a hash ring.
Shard Map Route keys through an explicit partition ownership table.

Replica State

Merkle Tree Compare replica state by hashing whole subtrees.
Replica Set Represent the nodes responsible for each shard copy.
Replication Log Store ordered state changes for followers to replay.

Time, Causality, And Ordering

Vector Clock Track causal order without one global clock.
Lamport Clock Create a partial ordering of events with counters.
Hybrid Logical Clock Blend physical time with causal ordering.
Version Vector Track per-replica versions for conflict detection.

Conflict-Free Collaboration

CRDT A family of mergeable replicated data structures.
Causal Tree Represent collaborative text as ordered causally linked inserts.
Last-Writer-Wins Register A simple conflict rule with sharp tradeoffs.
Observed-Remove Set A CRDT set that makes adds and removes mergeable.

Queues, Logs, And Streams

Partitioned Commit Log Scale ordered event storage across independent partitions.
Consumer Offset Index Track per-reader progress through an append-only log.
Delay Queue Release work only after its scheduled time arrives.
Dead Letter Queue Preserve failed messages for diagnosis and replay.

Vol. IV

Spatial And Geometry

Indexes and representations for points, polygons, maps, and collision worlds.

18 topics

Point And Region Indexes

KD-tree Split space by alternating coordinate axes.
Quadtree / R-tree Partition or bound space for map and region queries.
Interval Tree Find overlapping ranges efficiently.
Geohash Encode nearby coordinates with shared prefixes.
S2 Cell Index the globe with hierarchical cells on a projected cube.
H3 Hex Index Represent Earth with hierarchical hexagonal cells.

Collision And Acceleration Structures

Bounding Volume Hierarchy Nested boxes for fast intersection tests.
BSP Tree Recursively split space with planes for visibility and collision.
AABB Tree Maintain axis-aligned boxes for dynamic collision worlds.
Spatial Hash Grid Bucket nearby objects by grid cell for broad-phase queries.

Planar Geometry Structures

Voronoi Diagram Divide space by nearest site.
Delaunay Triangulation Connect points into well-shaped triangles.
Arrangement Store vertices, edges, and faces induced by curves or segments.
Quad-Edge Represent primal and dual planar subdivisions together.

Mesh And Polygon Representation

Half-Edge Data Structure Store mesh adjacency for traversal and editing.
DCEL A planar subdivision structure for faces, edges, and vertices.
Winged-Edge Mesh Store rich edge adjacency for manifold surfaces.
Face-Vertex Mesh Store geometry as vertex arrays plus indexed faces.

Vol. V

Graphics Programming

The rendering pipeline from pixels to scenes.

19 topics

Rasterization Pipeline

Z-buffer Depth testing so nearer fragments win.
Barycentric Coordinates Interpolate values across triangles.
Anti-Aliasing MSAA, FXAA, and TAA for smoother edges.
G-buffer Store per-pixel material and geometry data for deferred rendering.

GPU Programs And Surfaces

Shader Vertex and fragment programs in the GPU pipeline.
Texture Mapping / UVs Wrap images onto mesh surfaces.
Normal Mapping Fake surface detail by perturbing normals.
Signed Distance Field Represent shapes by distance to the nearest surface.

Scene Organization And Visibility

Scene Graph Represent transforms and hierarchy in a world.
Level-of-Detail Hierarchy Store alternate mesh resolutions for distance-based rendering.
Portal Graph Represent visible room-to-room connections in indoor scenes.

Lighting And Render Architecture

Ambient Occlusion Darken creases where nearby geometry blocks light.
Deferred vs Forward Rendering Choose where lighting work happens.
Global Illumination Model indirect light bouncing through a scene.
Lightmap Store baked lighting in texture space.

Curves, Volumes, And Transforms

Bezier Curves / B-splines Smooth curves for paths, fonts, and animation.
Quaternion Represent 3D rotation without Euler angle traps.
Skeletal Animation Drive meshes with bone hierarchies and skin weights.
Dual Quaternion Skinning Blend rigid transforms with fewer collapsing artifacts.

Vol. VI

Sketches And Approximation

Tiny summaries for huge streams and uncertain answers.

21 topics

Probabilistic Summaries

HyperLogLog Estimate distinct counts in a tiny amount of memory.
Count-Min Sketch Approximate frequencies in streaming data.
Cuckoo Filter vs Bloom Filter Membership tests when deletion matters.
Quotient Filter A compact deletable approximate membership structure.
Xor Filter Fast static membership filters with low memory overhead.
T-Digest Approximate quantiles accurately at distribution tails.
KLL Sketch A compact quantile sketch with strong error bounds.

Time-Series Structures

Time-Series Chunk Store ordered samples in compressed time-window blocks.
Delta-of-Delta Series Block Store timestamps as changes in spacing inside compressed blocks.
Gorilla Block A time-series block layout for timestamp and float compression.
Downsampling Rollup Precompute coarser windows for long-range queries.
Retention Tier Index Organize hot, warm, and cold series by age.
Time-Partitioned B+ Tree Route recent and historical samples through time ranges.
TSM File Influx-style immutable time-series blocks and indexes.
LSM Time-Series Layout Use sorted runs optimized for append-heavy metrics.

Stream Windows And Heavy Hitters

Sliding Window Counter Track recent activity without storing every event.
Exponential Histogram Approximate counts over a moving time window.
Heavy-Hitter Summary Track dominant keys in high-volume streams with bounded memory.
Reservoir Sample Store a representative sample from an unknown stream.
Misra-Gries Summary Track frequent items with bounded counters.
Lossy Counting Summary Store approximate frequent items over stream buckets.

Vol. VII

Graph Structures

Representations for relationships, dependencies, control flow, and graph-shaped data.

18 topics

Graph Representations

Adjacency List Store sparse graph neighbors compactly.
Adjacency Matrix Constant-time edge checks for dense graphs.
Compressed Sparse Row Pack graph edges into arrays for fast traversal.
Edge List Represent graphs as sortable relationship records.
Property Graph Attach labels and attributes to nodes and edges.

Graph Families And Components

Directed Graph Store relationships where edges have orientation.
Undirected Graph Store symmetric relationships between vertices.
Directed Acyclic Graph Represent dependencies with no directed cycles.
Multigraph Allow multiple edges between the same pair of vertices.
Hypergraph Represent edges that can connect more than two vertices.

Specialized Graph Structures

Dominator Tree Represent dominance relationships in a control-flow graph.
SPQR Tree Decompose a graph by its triconnected components.
Link-Cut Tree Maintain a changing forest with path queries.
Graph-Structured Stack Share parser stack prefixes across ambiguous parses.

Flow And Constraint Graphs

Residual Graph Track remaining capacity and reverse corrections in flow.
Bipartite Matching Graph Pair two sets under compatibility constraints.
Factor Graph Represent variables and constraints as a bipartite graph.
Decision Diagram Compactly represent boolean functions as a directed graph.

Vol. VIII

Compilers And Runtimes

Structures that turn source code into execution.

15 topics

Parsing And Syntax

Token Stream The linear structure produced by lexical analysis.
Parse Tree Represent grammar derivations before semantic cleanup.
Abstract Syntax Tree The program shape compilers actually transform.
Pratt Parser Table Encode expression precedence with binding powers.
Concrete Syntax Tree Preserve source-level syntax details for tooling.

Intermediate Representation

Control-Flow Graph Represent basic blocks and jumps between them.
Static Single Assignment Give every value one definition for easier optimization.
Use-Def Chain Link variable definitions to the places that use them.
Symbol Table Map names to scopes, types, and declarations.
Type Environment Track inferred and declared types across scopes.

Runtime Memory

Call Stack Store frames, locals, returns, and control flow.
Heap Arena Allocate many objects from large memory regions.
Free List Track reusable memory blocks after deallocation.
Heap Object Graph Represent object references for tracing and garbage collection.
Generational Heap Separate young and old objects for faster collection.

Vol. IX

Networking And Security

Packet paths, identity, integrity, and authenticated storage.

10 topics

Network Lookup And Routing

Radix Tree Compress prefixes for routing tables and string maps.
Patricia Trie Bitwise compressed trie for IP prefix lookup.
Routing Table Choose next hops by destination prefix.
Connection Table Track active flows by five-tuple keys.
Token Bucket Rate-limit bursts with refillable capacity.

Cryptographic Structures

Merkle Tree Authenticate large sets through recursive hashes.
Merkle Patricia Trie Authenticated key-value storage for blockchain state.
Sparse Merkle Tree Prove membership in a huge mostly-empty key space.
Hash Chain Link records so tampering changes every later hash.
Accumulator Compactly prove set membership with cryptographic witnesses.

Vol. X

Machine Learning And IR

Structures for retrieval, ranking, tensors, and learned representations.

10 topics

Retrieval Indexes

Inverted Index Map terms to documents and positions.
Posting List Store document ids, positions, and term payloads.
Skip Pointer Jump across long posting lists during intersection.
FST Term Dictionary Compress sorted terms into a finite-state transducer.
WAND Index Skip low-scoring documents during top-k retrieval.

Vector And Tensor Layouts

Embedding Matrix Store learned vector rows for tokens or entities.
Tensor Strides Map multidimensional indexes onto flat memory.
Sparse Tensor Store only non-zero coordinates and values.
Quantized Tensor Pack approximate numeric values into smaller types.
KV Cache Reuse transformer attention keys and values during generation.

Part Two

Algorithms

What you do with the data once it is arranged: search, sort, traverse, optimise, agree.

Vol. XI

Foundations And Techniques

The analysis vocabulary and the handful of patterns the rest of the book reuses.

6 published 18 topics

Analysis

Core Patterns

Binary Search Halve the search space, and get the boundary cases right.
Binary Search On Answer Search the result space when the input is not sorted.
Two Pointers Walk a sequence from both ends to avoid a nested loop.
Sliding Window Maintain a moving range and update it incrementally.
Prefix Sums Precompute cumulative totals for constant-time range queries.
Difference Array Apply many range updates in constant time each.
Divide And Conquer Split, solve independently, and combine the halves.
Meet In The Middle Halve an exponential search by enumerating both sides.

Bit Manipulation

Bitwise Tricks Masks, shifts, and the identities worth memorising.
Population Count Count set bits without looping over them.
Subset Enumeration Iterate every submask of a bitmask efficiently.
Gray Code Order values so consecutive entries differ by one bit.

Vol. XII

Sorting And Selection

Putting things in order, and finding the k-th item without bothering.

20 topics

Comparison Sorts

Quicksort Partition around a pivot and recurse on both sides.
Merge Sort Sort halves independently and merge them in linear time.
Heapsort Build a heap, then repeatedly extract the maximum.
Insertion Sort Grow a sorted prefix one element at a time.
Selection Sort Repeatedly move the smallest remaining item into place.
Bubble Sort Swap neighbours until no swaps remain.
Shell Sort Insertion sort over decreasing gap sequences.
Comparison Sort Lower Bound Why no comparison sort beats n log n.

Non-Comparison Sorts

Counting Sort Sort small integer keys by tallying occurrences.
Radix Sort Sort digit by digit using a stable inner sort.
Bucket Sort Distribute into ranges, sort each, concatenate.
Pigeonhole Sort Place keys directly into their own slots.

Production Sorts

Timsort The adaptive merge sort behind Python and Java.
Introsort Quicksort that falls back to heapsort on bad pivots.
Pattern-Defeating Quicksort Detect adversarial and presorted inputs cheaply.
External Merge Sort Sort data far larger than memory.
Parallel Sorting Split, sort, and merge across cores.

Selection And Order Statistics

Quickselect Find the k-th smallest without a full sort.
Median Of Medians Guarantee a good pivot in linear worst-case time.
Top-K Selection Keep only the best k items from a large stream.

Vol. XIII

Graph Algorithms

Traversal, shortest paths, spanning trees, connectivity, and flow.

32 topics

Traversal

Breadth-First Search Explore level by level; shortest paths on unweighted graphs.
Depth-First Search Follow each branch to exhaustion and backtrack.
Topological Sort Order a DAG so every edge points forward.
Cycle Detection Find cycles in directed and undirected graphs.
Bipartite Check Two-colour a graph, or prove you cannot.
Flood Fill Expand through a connected region of a grid.

Shortest Paths

Dijkstra's Algorithm Greedy shortest paths with non-negative weights.
Bellman-Ford Handle negative weights and detect negative cycles.
Floyd-Warshall All-pairs shortest paths by dynamic programming.
A* Search Guide the search with an admissible heuristic.
Bidirectional Search Search from both endpoints and meet in the middle.
Johnson's Algorithm All-pairs shortest paths on sparse weighted graphs.
0-1 BFS Shortest paths when every edge costs zero or one.

Spanning Trees And Connectivity

Kruskal's Algorithm Build a minimum spanning tree edge by edge.
Prim's Algorithm Grow a minimum spanning tree from one vertex.
Borůvka's Algorithm Merge components in parallel rounds.
Tarjan's SCC Algorithm Find strongly connected components in one pass.
Kosaraju's Algorithm Two traversals, one on the reversed graph.
Bridges And Articulation Points Find the edges and vertices that hold a graph together.
Lowest Common Ancestor Answer ancestor queries with binary lifting or Euler tours.

Flow And Matching

Ford-Fulkerson Augment along paths until no capacity remains.
Edmonds-Karp Ford-Fulkerson with shortest augmenting paths.
Dinic's Algorithm Level graphs and blocking flows for faster max flow.
Min-Cut Max-Flow Why the smallest cut equals the largest flow.
Hopcroft-Karp Maximum bipartite matching in near-linear time.
Hungarian Algorithm Optimal assignment under a cost matrix.
Min-Cost Max-Flow Push maximum flow at the lowest total cost.

Graph Ranking And Traversal Paths

PageRank Rank nodes by the random surfer stationary distribution.
HITS Separate hubs from authorities in a link graph.
Eulerian Path Walk every edge exactly once.
Hamiltonian Path Visit every vertex once, and why it is hard.
Travelling Salesman Exact and approximate tours of every city.

Vol. XIV

Dynamic Programming

Recognising overlapping subproblems, and the classic recurrences worth knowing by heart.

22 topics

Method

Memoization vs Tabulation Top-down and bottom-up, and when each is clearer.
State Design Choosing the smallest state that still has optimal substructure.
Optimal Substructure The property that makes dynamic programming legal.
Space Optimization Collapse a table to a row when only the last one matters.

Classic Recurrences

0/1 Knapsack Take or leave each item under a weight budget.
Unbounded Knapsack Unlimited copies of each item.
Coin Change Minimum coins, and counting the ways.
Longest Common Subsequence The alignment behind diff tools.
Longest Increasing Subsequence The n log n patience-sorting solution.
Edit Distance Insertions, deletions, and substitutions between strings.
Kadane's Algorithm Maximum subarray sum in one pass.
Matrix Chain Multiplication Parenthesise products to minimise work.
Rod Cutting Maximise revenue from cut lengths.
Subset Sum And Partition Hit a target total from a set of numbers.
Palindrome Partitioning Fewest cuts so every piece reads the same both ways.

Advanced Formulations

DP On Trees Combine child answers into a parent answer.
Bitmask DP Encode visited-set state in an integer.
Digit DP Count numbers in a range satisfying digit constraints.
Interval DP Solve over ranges by growing the interval length.
Convex Hull Trick Optimise linear transitions with a hull of lines.
Divide And Conquer Optimization Exploit monotone split points to drop a factor.
Knuth Optimization Narrow transition ranges using quadrangle inequalities.

Vol. XV

Strings And Text

Matching, indexing, and compressing sequences of characters.

24 topics

Pattern Matching

Naive String Search The baseline every other algorithm improves on.
Knuth-Morris-Pratt Never re-examine a character, using the failure function.
Rabin-Karp Rolling hashes to compare windows in constant time.
Boyer-Moore Skip ahead by scanning the pattern backwards.
Z-Algorithm Prefix-match lengths at every position in linear time.
Aho-Corasick Match thousands of patterns in a single pass.
Manacher's Algorithm All palindromic substrings in linear time.

Text Indexes

Suffix Array Construction Build a sorted suffix index efficiently.
LCP Array Longest common prefixes between adjacent suffixes.
Suffix Automaton A minimal automaton recognising every substring.
String Hashing Compare substrings in constant time, and avoid collisions.

Similarity And Alignment

Levenshtein Distance The edit distance used for fuzzy matching.
Needleman-Wunsch Global sequence alignment for biological data.
Smith-Waterman Local alignment of the best-matching region.
Jaccard And MinHash Estimate set similarity from tiny signatures.
Soundex And Metaphone Match names that sound alike.

Compression

Huffman Coding Optimal prefix codes from symbol frequencies.
LZ77 And LZ78 Replace repeats with references to earlier text.
Arithmetic Coding Encode a whole message as one fractional number.
Burrows-Wheeler Transform Reorder text so repeats cluster together.
Run-Length Encoding Store repeated values as value and count.

Automata

Regular Expression Engines Backtracking versus automaton-based matching.
NFA To DFA Subset construction and why it can explode.
DFA Minimization Merge indistinguishable states.

Vol. XVI

Mathematics And Number Theory

Arithmetic, primes, transforms, and the algebra underneath everything else.

19 topics

Number Theory

Euclidean Algorithm The oldest algorithm still in daily use.
Extended Euclidean Algorithm Solve linear Diophantine equations and find inverses.
Modular Exponentiation Raise to huge powers by repeated squaring.
Modular Inverse Division under a modulus.
Chinese Remainder Theorem Reconstruct a value from its remainders.
Euler Totient Function Count integers coprime to n.

Primes And Factorization

Sieve of Eratosthenes Mark composites to enumerate primes.
Linear Sieve Compute primes and multiplicative functions in O(n).
Miller-Rabin Primality Test Probabilistic primality with tunable confidence.
Pollard's Rho Factor large integers with a cycle-finding walk.

Transforms And Linear Algebra

Fast Fourier Transform Multiply polynomials and signals in n log n.
Number Theoretic Transform The FFT over a finite field, without rounding error.
Matrix Exponentiation Jump ahead in a linear recurrence.
Gaussian Elimination Solve linear systems by row reduction.
Karatsuba Multiplication Multiply big integers with three products instead of four.

Combinatorics

Binomial Coefficients Compute n choose k without overflow.
Inclusion-Exclusion Count unions by alternating over intersections.
Catalan Numbers The counting sequence behind balanced structures.
Permutation Generation Enumerate arrangements in lexicographic order.

Vol. XVII

Computational Geometry

Points, lines, polygons, and the sweep that makes them tractable.

13 topics

Primitives

Orientation Test The cross-product predicate underneath everything.
Line Segment Intersection Decide whether two segments cross.
Point In Polygon Ray casting and winding numbers.
Polygon Area The shoelace formula and signed area.

Hulls And Proximity

Graham Scan Convex hull by angular sort.
Andrew Monotone Chain Convex hull by sorting on x.
Closest Pair Of Points Divide and conquer in n log n.
Rotating Calipers Diameter and width from a convex hull.

Sweep And Subdivision

Line Sweep Process events in x-order with an active set.
Bentley-Ottmann Report all segment intersections output-sensitively.
Fortune's Algorithm Build a Voronoi diagram with a beach line.
Delaunay Triangulation Triangulate so no point lies inside a circumcircle.
Half-Plane Intersection Intersect linear constraints into a convex region.

Vol. XVIII

Search, Greedy, And Optimization

Exploring huge spaces when exact enumeration is out of reach.

27 topics

Exhaustive And Guided Search

Backtracking Build candidates incrementally and abandon dead ends.
N-Queens The canonical backtracking problem.
Sudoku Solving Constraint propagation plus search.
Branch And Bound Prune subtrees that cannot beat the best answer.
Iterative Deepening Depth-first search with breadth-first guarantees.
Minimax And Alpha-Beta Adversarial search with pruning.
Monte Carlo Tree Search Sample playouts to guide the tree.

Greedy Methods

Greedy Choice Property When local decisions produce a global optimum.
Interval Scheduling Fit the most non-overlapping intervals.
Huffman Construction Greedy merging of the two smallest frequencies.
Fractional Knapsack Where greedy beats dynamic programming.
Matroid Theory The structure that explains why greedy works.

Approximation And Metaheuristics

Approximation Ratios Provable bounds on how wrong a fast answer can be.
Set Cover Greedy The logarithmic approximation and its tightness.
Simulated Annealing Accept worse moves early to escape local optima.
Genetic Algorithms Selection, crossover, and mutation over populations.
Hill Climbing Local search and the traps it falls into.
Gradient Descent Follow the slope downhill to a minimum.
Simplex Method Walk vertices of a polytope to optimise a linear program.

Randomized Algorithms

Las Vegas vs Monte Carlo Always correct versus always fast.
Randomized Quicksort Random pivots defeat adversarial inputs.
Reservoir Sampling Sample k items from a stream of unknown length.
Fisher-Yates Shuffle Produce a uniformly random permutation.
Karger's Min Cut Contract random edges to find a minimum cut.

Complexity Classes

P vs NP What the question actually asks.
NP-Completeness Reductions and the problems everything maps to.
Undecidability The halting problem and its consequences.

Vol. XIX

Concurrency And Distributed Algorithms

Coordination, consensus, and correctness when there is more than one machine.

25 topics

Synchronization

Mutex And Semaphore The primitives every lock is built from.
Compare-And-Swap The atomic instruction behind lock-free code.
The ABA Problem Why a matching pointer is not proof of no change.
Lock-Free Queues Progress guarantees without mutual exclusion.
Read-Copy-Update Readers proceed while writers publish new versions.
Deadlock Detection Find cycles in the wait-for graph.
Peterson's Algorithm Mutual exclusion from plain loads and stores.

Consensus And Replication

Two-Phase Commit Atomic commitment, and how it blocks.
Three-Phase Commit Trading a round trip for non-blocking behaviour.
Paxos The consensus algorithm everything else is compared to.
Raft Consensus restructured for understandability.
Leader Election Agree on one coordinator without a coordinator.
Gossip Protocols Spread state epidemically without a central node.
Quorum Reads And Writes Choosing R and W so they overlap.

Consistency And Transactions

Linearizability The strongest single-object consistency model.
Eventual Consistency Convergence without coordination.
CAP And PACELC What you actually trade under partition and latency.
Multi-Version Concurrency Control Readers never block writers.
Snapshot Isolation Consistent reads and the write-skew anomaly.
Two-Phase Locking The protocol that makes schedules serializable.

Distributed Computation

MapReduce Partition, compute locally, shuffle, reduce.
Consistent Hashing Add and remove nodes without reshuffling everything.
Rendezvous Hashing Pick an owner by highest random weight.
Vector Clock Comparison Decide causal order between two events.
Distributed Snapshots The Chandy-Lamport marker algorithm.

Vol. XX

Hashing And Cryptography

Turning data into fixed-size values, and doing it when an adversary is watching.

19 topics

Hashing

Hash Functions What makes a hash uniform, fast, and hard to break.
Open Addressing Linear, quadratic, and double-hash probing.
Separate Chaining Buckets of collided keys, and the load factor.
Robin Hood Hashing Even out probe distances by stealing from the rich.
Cuckoo Hashing Two tables, two hashes, constant worst-case lookup.
Perfect Hashing Collision-free hashing for a fixed key set.
Universal Hashing Randomise the hash so no input is adversarial.
Locality-Sensitive Hashing Hash similar inputs to the same bucket on purpose.

Cryptographic Primitives

SHA-2 And SHA-3 The construction inside modern digest functions.
HMAC Authenticate a message with a shared key.
Password Hashing bcrypt, scrypt, and Argon2, and why speed is the enemy.
AES The block cipher and its modes of operation.
Birthday Attack Why collisions arrive at the square root.

Public Key And Proofs

RSA Encryption and signatures from integer factorisation.
Diffie-Hellman Agree on a shared secret over an open channel.
Elliptic Curve Cryptography Smaller keys from harder group structure.
Digital Signatures Prove authorship without revealing the key.
Merkle Proofs Prove membership with a logarithmic path of hashes.
Zero-Knowledge Proofs Convince a verifier while revealing nothing else.