All 634 articles, sorted alphabetically
2-Edge-Connected Components + Bridge Tree, in depth: one iterative build, must-cross queries with LCA, and the best edge to add
2-edge-connected components and the bridge tree from first principles: why the relation is an equivalence, an iterative build that handles parallel ed…
Read article →A* Algorithm, in depth: designing the search space, with heading lattices, max-of-relaxation heuristics, hybrid A* keys and space-time planning
A* beyond the grid: what belongs in a state, successor functions and duplicate keys, heuristics as relaxations combined with max, measured expansions …
Read article →A* Pathfinding, in depth: admissible and consistent heuristics, grid heuristics, tie-breaking, weighted A* and when to move beyond it
How A* finds shortest paths: f = g + h from first principles, a correct Python implementation with lazy deletion, what admissibility and consistency e…
Read article →Activity Selection, in depth: earliest finish first, two proofs, failing orderings, endpoint rules, weighted DP and k rooms
Activity selection explained from first principles: the earliest-finish greedy, a full worked trace, stays-ahead and exchange proofs, counterexamples …
Read article →AES-GCM, in depth: counter mode plus GHASH, the GF(2^128) multiply, a tested implementation, nonce rules, what nonce reuse breaks and how to use it safely
How AES-GCM works and how to use it safely: the CTR and GHASH construction, reflected GF(2^128) arithmetic, a reference implementation checked against…
Read article →AES, in depth: GF(2^8) arithmetic, the derived S-box, the four round operations, a verified implementation, modes, nonces and side channels
AES from first principles: the GF(2^8) field, how the S-box is built, SubBytes, ShiftRows, MixColumns and the key schedule, a Python implementation th…
Read article →Aho-Corasick, in depth: one pass over the text for thousands of patterns
Aho-Corasick multi-pattern matching from first principles: trie, BFS failure links, output links, a tested Python implementation, a traced example on …
Read article →2D Geometry Algorithms, in depth: orientation, segment and line intersection, signed area, point in polygon, angle sorting and robust arithmetic
The primitive layer of 2D computational geometry: dot and cross products, the orientation predicate, segment intersection with collinear cases, exact …
Read article →2-SAT, in depth: implication graphs, strongly connected components and a tested solver
How 2-SAT is solved in linear time: turning two-literal clauses into an implication graph, why strongly connected components decide satisfiability, re…
Read article →3-SAT Reduction, in depth: proving SAT reduces to 3-SAT by clause splitting, witness mapping both ways, a brute-force test and the restricted variants that stay hard
How SAT reduces to 3-SAT: the clause-splitting chain with fresh variables, both proof directions, linear size, tested Python with witness mapping, a w…
Read article →A* Search Deep Dive, in depth: the optimality proof, consistency as reduced costs, measuring heuristics, open-list engineering and heuristics from relaxations
A* from first principles: why admissible heuristics give optimal paths, how consistency turns A* into Dijkstra on reduced costs, reopening under incon…
Read article →A* Variants, in depth: IDA*, bidirectional A*, jump point search, ARA* and D* Lite with working code and the conditions that keep them correct
Implement and choose A* variants: IDA* for linear memory, bidirectional A* with a correct stop rule, jump point search on uniform grids, anytime ARA* …
Read article →Accounting Method for Amortized Analysis, in depth: charges and credits, the two-stack queue, credits per element in a dynamic array, ledger tests and where credit arguments break
The accounting (banker's) method for amortized analysis: the non-negative bank invariant, an exact two-stack queue trace, dynamic-array credits w…
Read article →Aggregate Method for Amortized Analysis, in depth: total-cost bounds, multipop and monotonic stacks, pointer arguments, graph traversals and where it breaks
The aggregate method of amortized analysis from first principles: bounding the total cost of a sequence, multipop stacks, monotonic stacks with a trac…
Read article →Aho-Corasick Algorithm, in depth: the complete automaton, the failure tree, per-pattern counts and dynamic programming over states
Aho-Corasick as a data structure: building the complete transition table, why failure links form a tree, counting every pattern in O(n + S x A) regard…
Read article →Alias Method, in depth: constant-time sampling from a discrete distribution, the Vose construction, exact integer tables and when a sum tree wins
The alias method for O(1) weighted sampling: why every column needs at most two outcomes, the Vose O(n) construction traced step by step, Python and v…
Read article →Alpha-Beta Pruning, in depth: the fail-soft bound contract, the minimal tree, measured move ordering, PVS and MTD(f)
Alpha-beta pruning beyond the hand trace: what a search returns outside its window, the Knuth-Moore minimal tree and PV, CUT and ALL nodes, measured l…
Read article →Amortized Analysis, in depth: what the guarantee promises, choosing a method, deamortization and measured tail cost
What an amortized bound promises and what it does not, how it differs from worst-case, average and expected bounds, how to choose between aggregate, a…
Read article →ANS Coding, in depth: the state as a number, a hand trace, rANS renormalization, tANS tables and interleaving
Asymmetric numeral systems from first principles: encoding as growing an integer state, a hand trace with M = 16, a tested byte-wise rANS coder within…
Read article →Approximation Algorithms, in depth: the lower-bound sandwich, vertex cover, set cover, LP rounding, metric TSP and a knapsack FPTAS
Approximation algorithms from first principles: the approximation ratio and the lower-bound proof pattern, vertex cover by maximal matching, greedy se…
Read article →APX-Hard Problems, in depth: the approximation ladder, L-reductions, APX-completeness, a tested reduction chain and what hardness changes
APX and APX-hardness from first principles: approximation ratios and the class ladder, why Karp reductions do not preserve approximation, L-, AP- and …
Read article →ARC architecture
Deep-dive on ARC, the Adaptive Replacement Cache that beats LRU and LFU by adapting the recency-versus-frequency balance automatically per workload, w…
Read article →Argon2, in depth: the memory matrix, the compression function G, data-dependent versus independent indexing, a tested implementation, parameter choice and running it safely on a login path
How Argon2 works and how to deploy it: H0 and the lane/slice memory matrix, the BLAKE2b-based compression function with its multiply, Argon2d/i/id ind…
Read article →Arithmetic Coding, in depth: interval narrowing, integer renormalization with pending bits, a tested adaptive coder, models, termination and LLM-driven compression
Arithmetic coding from first principles: a hand-traced example, E1/E2/E3 renormalization and underflow, the precision contract, a complete tested adap…
Read article →Articulation Points (Cut Vertices), in depth: an iterative DFS that ranks single points of failure, and the block-cut tree
Finding cut vertices in O(V + E): the disc and low rules and why they hold, a stack-based implementation that also reports the size of every piece a f…
Read article →AVL Tree, in depth: the balance invariant, the Fibonacci height bound, four rotation cases, deletion and a tested implementation
How AVL trees stay balanced: the height invariant, why height stays under 1.44 log2 n, the four rotation cases, insertion versus deletion repair, Pyth…
Read article →Backtracking, in depth: choose, explore, unchoose, and the pruning that makes exponential search usable
A first-principles guide to backtracking: the state-space tree, the choose/explore/unchoose template, a bitmask N-Queens solver with measured node cou…
Read article →BFS and DFS, in depth: frontiers, visited sets, shortest paths, edge classification, cycle detection and the bugs that make traversals wrong or slow
Breadth-first and depth-first search from first principles: the frontier container, when to mark visited, BFS shortest paths and parent maps, DFS disc…
Read article →Biconnected Components, in depth: the edge-stack DFS done iteratively, parallel edges, the block-cut tree and what blocks are for
Biconnected components from first principles: three equivalent definitions, an iterative edge-stack DFS tested against a brute-force oracle, why multi…
Read article →Bidirectional Search, in depth: level-synchronous BFS, why growth rate decides the payoff, and MM for heuristic search
How bidirectional search works and when it pays: a tested level-synchronous bidirectional BFS with path recovery, measured 1.8x savings on a grid agai…
Read article →Big-O Notation: O, Omega, Theta and Time Complexity
Big-O notation done properly: formal O, Omega and Theta, why worst case differs from big-O, amortized and expected time, the Master Theorem, and the R…
Read article →2D Binary Indexed Tree, in depth: sparse coordinates, the offline-planned BIT of sorted lists, sweeps, and dominance chains
A 2D Fenwick tree for coordinates up to a billion: a planning pass that gives each outer node its own compressed inner tree in O(N log N) memory, a wo…
Read article →Bipartite Matching, in depth: problem variants, modelling, the flow reduction, Hopcroft-Karp, Konig and Hall certificates, and weighted assignment
A practical guide to bipartite matching: which variant you have, how to model real problems, why matching is max flow, a tested Hopcroft-Karp implemen…
Read article →Bit Hacks Catalog, in depth: lowest-bit tricks, SWAR popcount, De Bruijn, Gosper's hack and a test harness
A catalog of bit hacks derived from first principles: lowest-set-bit tricks, SWAR popcount, De Bruijn trailing-zero counts, power-of-two rounding, bra…
Read article →Bit Manipulation Fundamentals, in depth: two's complement, masks, shifts across languages and the core idioms
Bit manipulation from first principles: two's complement, AND/OR/XOR/NOT and shift semantics in C, Java, Python and JavaScript, masks and packed …
Read article →Bitboards for Chess, in depth: square mapping, set-wise move generation, magic and PEXT sliders, and perft testing
Chess bitboards from first principles: the LERF square mapping, shifts with file-wrap masks, set-wise pawn and knight moves, sliding attacks with ray …
Read article →Bitmask DP, in depth: subsets as integers, the add-one, submask and sum-over-subsets transitions, a worked assignment table, partitions and the limits of n
Bitmask dynamic programming from first principles: representing subsets as integers, the three transition shapes and their O(n 2^n) and O(3^n) costs, …
Read article →Bloom filter architecture, in depth: false positive math, two-hash indexing, cache-blocked layouts and sizing
Bloom filters from first principles: deriving the false positive rate and optimal k, sizing for n keys, double hashing, blocked and split-block layout…
Read article →Bloom Filter Variants, in depth: counting, partitioned, scalable, stable, rotating and invertible Bloom filters with code, sizing math and failure modes
The Bloom filter variants that remove each classic limitation: counting filters for deletes and the 4-bit overflow bound, partitioned and scalable fil…
Read article →Borůvka's Algorithm, in depth: cheapest-edge phases, the halving bound, tie-breaking, parallel contraction and when it beats Kruskal and Prim
Borůvka's MST algorithm from the cut property: a traced example, the log V phase bound, why (weight, id) tie-breaking is required, tested union-f…
Read article →Boyer-Moore String Matching, in depth: Horspool and Sunday variants, expected cost, alphabet design and how libraries ship it
An engineering guide to Boyer-Moore style search: the right-to-left idea, Horspool and Sunday Quick Search in tested Python, a traced example, expecte…
Read article →Bridges (Cut Edges) in Graphs, in depth: chain decomposition, XOR certificates and adding the fewest edges to remove every bridge
Bridges beyond low-link: the covering characterisation, Schmidt chain decomposition, random XOR labels that also reveal 2-edge cuts, the bridge tree a…
Read article →Brotli Compression, in depth: meta-blocks, context modelling, the static dictionary, measured quality levels and safe serving
How Brotli works from the bits up: windows and meta-blocks, combined insert-and-copy codes, the last-distance ring, context modes and maps, the 122,78…
Read article →BSP, in depth: the Bulk Synchronous Parallel model, its cost formula and superstep algorithms
Bulk Synchronous Parallel from first principles: supersteps and barriers, the w + h*g + l cost model, measuring g and l, a BSP prefix-sum simulator wi…
Read article →Chinese Remainder Theorem, in depth: constructive proof, Garner mixed radix, non-coprime merging, multi-prime NTT and RSA-CRT
The Chinese Remainder Theorem from first principles: proof by construction, the Garner mixed-radix algorithm, merging congruences with non-coprime mod…
Read article →Christofides Algorithm, in depth: the five steps, the full 3/2 proof, a runnable implementation, the tight instance and 2-opt clean-up
Christofides' 1.5-approximation for metric TSP from first principles: MST, odd vertices, minimum perfect matching, Euler circuit and shortcutting…
Read article →Chromatic Number and Chromatic Polynomial, in depth: closing the bounds gap, inclusion-exclusion in O*(2^n), and reductions that shrink n
Computing the chromatic number exactly: cheap bounds and the Grötzsch graph where they fail, the Björklund-Husfeldt-Koivisto inclusion-exclusion test …
Read article →Clique NP-Hardness Reduction, in depth: 3-SAT to CLIQUE, both proof directions, tested code and what hardness means in practice
The 3-SAT to CLIQUE reduction explained: construction, worked example, proof in both directions, certificate-mapping code with a brute-force cross-che…
Read article →Count-Min Sketch Architecture in Depth
A 2500-word walkthrough of Count-Min Sketch: d × w counter matrix, hash functions, insert + query, overestimate math, parameters, applications, varian…
Read article →Combinatorics, in depth: counting rules, binomials modulo a prime, Lucas's theorem, inclusion-exclusion, Catalan numbers and ranking combinations
Counting from first principles for programmers: the four selection cases, stars and bars, exact and overflow-safe binomials, factorial tables with Fer…
Read article →Computational Biology Algorithms, in depth: local alignment, minimizers, seed-chain-extend mapping, HMMs and neighbor joining
A working map of computational biology's core algorithms with runnable Python: Smith-Waterman with affine gaps, minimizer sampling, seed-chain-ex…
Read article →Consistent hashing architecture
Deep-dive on consistent hashing: ring, virtual nodes, replica walk, bounded loads, Anchor/Jump/Rendezvous variants, and cluster management.
Read article →Convex Hull, in depth: orientation tests, monotone chain, output-sensitive algorithms, robustness and rotating calipers
The convex hull from first principles: the n log n lower bound, the orientation predicate, Andrew's monotone chain with a full worked trace, Grah…
Read article →3D Convex Hull, in depth: the orientation determinant, horizons, randomized incremental construction and robust Qhull use
Building 3D convex hulls from first principles: Euler bounds, the signed-volume predicate, horizon stitching, tested Python, a worked example, conflic…
Read article →Convex Optimization, in depth: recognising convexity, the LP to SDP ladder, proximal and Newton methods with certificates
A practitioner guide to convex optimisation: why local equals global, how to prove convexity with atoms and rules, the LP, QP, SOCP and SDP ladder, CV…
Read article →Count-Min Sketch, in depth: the error proof, and the queries beyond point lookups: ranges, quantiles, heavy-hitter recovery and join sizes
Count-Min Sketch from first principles, past the point query: a four-step proof of the error bound, the strict-turnstile caveat and skew, dyadic range…
Read article →Count-Min Sketch Architecture, in depth: an implementation guide to memory layout, hashing once, concurrency, serialization and testing the error bound
How to build a production Count-Min sketch: a contiguous counter layout with power-of-two width, deriving all row indices from one stable hash, a refe…
Read article →Cuckoo filters, in depth: partial-key cuckoo hashing, sizing math, a full implementation and production failure modes
Cuckoo filters from first principles: fingerprints and alternate buckets, false-positive and space math against Bloom filters, a complete implementati…
Read article →Cuckoo Hashing, in depth: two-probe lookups, the cuckoo graph, bucketised load limits, stashes and a hash-correlation trap
Cuckoo hashing from first principles: an insertion trace, a complete tested implementation, why inserts fail (the cuckoo graph and the 50% wall), simu…
Read article →D* / D* Lite, in depth: the g and rhs invariant, backwards search, the km key trick, a tested implementation and a measured comparison with repeated A*
How D* Lite replans for a moving robot: lineage from Stentz's D* through LPA*, the g/rhs consistency invariant, why it searches from the goal, th…
Read article →De Bruijn Graph Assembly, in depth: k-mers, solid filtering, unitigs, tips, bubbles, repeats and choosing k
How de Bruijn graphs assemble genomes from short reads: k-mer counting and canonical k-mers, a worked k = 5 example with real output, error removal th…
Read article →Delta Encoding, in depth: gap entropy, zigzag and varints, block bit-packing, measured sizes and rsync-style binary deltas
Delta encoding from first principles: why gaps beat raw values, zigzag and varint code, Parquet-style block bit-packing, measured bytes per value on f…
Read article →Derandomization, in depth: conditional expectations, pessimistic estimators, seed enumeration and pseudorandom generators
How to remove the coins from a randomized algorithm and keep its guarantee: the method of conditional expectations on MAX-CUT and exact-3 MAX-SAT with…
Read article →Diffie-Hellman Key Exchange, in depth: a small-subgroup attack run end to end, public-key validation, key lifetime and wire encoding
Why a Diffie-Hellman party must validate the public value it receives: a runnable small-subgroup confinement attack that recovers a static key with CR…
Read article →Digit DP, in depth: prefix counting, the tight and started flags, sums and k-th queries, bottom-up tables and brute-force testing
Learn digit DP from first principles: f(R) - f(L-1), states built from position, summary, tight and started flags, a Python template, worked examples …
Read article →Dijkstra's Algorithm, in depth: the settled-frontier invariant, a correct implementation, negative edges and production pitfalls
A complete guide to Dijkstra's shortest-path algorithm: the invariant that makes it work, a lazy-deletion heap implementation with path reconstru…
Read article →Dinic's Algorithm, in depth: level graphs, blocking flows, current-arc pointers and a max-flow implementation you can trust
Dinic's maximum-flow algorithm from first principles: residual graphs, BFS level graphs, blocking flows with current-arc pointers, why each phase…
Read article →Discrete Logarithm Problem, in depth: why the group decides the cost, index calculus worked end to end, and parameters that stay hard
The discrete logarithm problem as a security assumption: DLP, CDH and DDH, the generic square-root bound, index calculus implemented and worked by han…
Read article →DiskANN architecture
Deep-dive on DiskANN: the Vamana low-diameter graph, product-quantized guidance in RAM with full vectors on disk, beam search and exact re-rank, alpha…
Read article →Distributed Consensus Architecture: Raft, Paxos, and Beyond, in depth: protocol choice, read paths, reconfiguration and placement
Consensus as an architectural component: Raft and Multi-Paxos rules in code, EPaxos and Flexible Paxos, ReadIndex versus lease reads, safe membership …
Read article →Divide and Conquer, in depth: recursion trees, the master theorem, worked algorithms and making recursive code fast
Divide and conquer from first principles: divide, conquer, combine, reading a recursion tree, the master theorem with worked recurrences, counting inv…
Read article →Coin Change DP, in depth: finite tills, trillion-unit amounts, residue-class shortest paths and counting with Bostan-Mori
Coin change beyond the textbook table: bounded dispensing from a finite till where greedy fails, a pigeonhole cut for huge amounts, residue-class Dijk…
Read article →Edit Distance, in depth: the Levenshtein recurrence, a full worked table, traceback, weighted costs, OSA vs true Damerau, banded checks and BK-tree search
Levenshtein edit distance from first principles: deriving the recurrence, the kitten to sitting table and edit script, weighted costs, why OSA breaks …
Read article →Egg Drop Puzzle DP, in depth: the monotone optimum, the two-egg closed form, lower bounds and an overflow-safe solver
Egg drop as a ladder of optimisations: the state and recurrence, an O(kn) monotone-pointer DP and the plateau subtlety, the two-egg closed form, the l…
Read article →0/1 Knapsack DP, in depth: state semantics, a computed worked table, reconstruction in linear memory, the value-indexed DP and a brute-force test oracle
Engineering the 0/1 knapsack dynamic programme: what a cell means, exact versus at-most initialisation, a computed worked example, recovering the chos…
Read article →Longest Increasing Subsequence, in depth: the O(n^2) recurrence, the patience method in O(n log n), reconstruction and the reductions that use it
Longest increasing subsequence from first principles: the quadratic dynamic program, the tails invariant and its proof, tested O(n log n) code with re…
Read article →Optimal BST, in depth: from access logs to a deployed lookup tree, with smoothed weights, root reconstruction, weight-balanced approximation and drift-based rebuilds
An applied guide to optimal binary search trees: turning probe logs into hit and gap weights, the Knuth-window DP with reconstruction, a worked exampl…
Read article →Rod Cutting DP, in depth: the first-piece recurrence, a full worked table, reconstruction, cut costs, piece limits and pseudo-polynomial time
Rod cutting dynamic programming from first principles: optimal substructure, the recurrence, a bottom-up Python implementation with reconstruction, a …
Read article →Wildcard Pattern Matching DP, in depth: the star recurrence, a worked table, linear-space DP, greedy and segment matchers with measured worst cases, and real glob semantics
Wildcard matching with ? and * explained from the recursion: why naive recursion explodes, the DP recurrence and a filled table, an O(m)-space impleme…
Read article →DSU on Tree (Small-to-Large), in depth: the keep-heavy sack, an iterative layout, offline subtree queries and the bugs that make it quadratic
The sack technique for offline subtree queries: why keeping the heavy child gives O(n log n), an iterative Euler-tour layout with no recursion, a test…
Read article →Dynamic Graph Connectivity, in depth: spanning forests, smaller-side replacement search, HDT levels and choosing the right variant
Online fully dynamic graph connectivity: the variants and their tools, why deleting a tree edge is the hard case, a tested Python structure with a loc…
Read article →Dynamic programming, in depth: states, recurrences, evaluation order and the bugs that break them
A first-principles guide to dynamic programming: optimal substructure and overlapping subproblems, the subproblem DAG, defining state and recurrence, …
Read article →ECC Deep Dive, in depth: the arithmetic engine under elliptic-curve crypto, from field reduction and Jacobian formulas to batch inversion, wNAF and constant time
How elliptic-curve libraries compute k times P: the M/S/I cost model, special-prime reduction, Jacobian doubling and mixed addition, Montgomery's…
Read article →ECDH, in depth: the X25519 Montgomery ladder, clamping and low-order points, P-256 validation and ECDH as a KEM in HPKE
Elliptic-curve Diffie-Hellman as a deployable primitive: X25519 from RFC 7748 verified against its test vector, clamping and the conditional swap, the…
Read article →Edge-Disjoint Paths, in depth: Menger's theorem, unit-capacity max flow, the min-cut certificate and vertex-disjoint reductions
Maximum edge-disjoint s-t paths from first principles: Menger's theorem, why greedy fails, residual cancellation traced on a trap graph, a tested…
Read article →Edmonds' Blossom Algorithm, in depth: contracting odd cycles, lifting paths and the Gallai-Edmonds decomposition
Edmonds' blossom algorithm from first principles: why bipartite search fails on odd cycles, a proof of the contraction lemma, a tested contract-r…
Read article →Ellipsoid Algorithm, in depth: central cuts, the volume argument, certified bounds and why polynomial did not mean fast
How the ellipsoid method works: separation oracles, the central-cut update formula, why volume shrinks by e^(-1/(2(n+1))) per step, objective cuts wit…
Read article →Entropy Coding Overview, in depth: the entropy bound, Kraft, models versus coders, and choosing Huffman, arithmetic, ANS or Rice
A map of entropy coding: Shannon's bound and Kraft-McMillan, why Huffman is stuck at whole bits, a harness to measure your data, measured worked …
Read article →Epoch-Based Reclamation, in depth: the epoch invariant, fences, crossbeam-epoch and stalled readers
Epoch-based memory reclamation for lock-free data structures from first principles: pin, retire, advance and collect, why two epochs and a full fence,…
Read article →Euler Tour on Tree, in depth: the 2n-1 sequence, LCA as range minimum, and Euler tour trees for dynamic forests
The full Euler tour of a tree: an iterative 2n-1 build, why LCA is the shallowest node between first visits, an O(1) sparse-table LCA with tested code…
Read article →Exchange Argument, in depth: proving greedy algorithms with swaps, Smith's rule, EDD and the transitivity trap
The exchange argument from first principles: its three obligations, the adjacent-swap template, Smith's rule and EDD derived from two-job swaps, …
Read article →Expected Value in Algorithms, in depth: linearity, indicator variables, tail bounds and simulations that check the maths
Expected value for analysing randomized algorithms: randomized versus average-case analysis, linearity of expectation and indicator variables, the exa…
Read article →Expectimax, in depth: chance nodes, why evaluation scale suddenly matters, Star1 pruning and a measured 2048 player
Expectimax from first principles: when to average instead of minimise, the recursion and expectiminimax, why only affine rescaling of the evaluation i…
Read article →Fenwick tree architecture
Deep-dive on the Fenwick tree (binary indexed tree): the range each cell owns via lowbit(i) = i & -i, upward-walking updates and downward-walking …
Read article →Fast Fourier Transform, in depth: roots of unity, the butterfly, iterative in-place code, fast convolution, precision limits and where FFTs run in ML
The Fast Fourier Transform from first principles: the DFT as polynomial evaluation at roots of unity, the even/odd split and butterfly, recursive and …
Read article →Fibonacci Heap, in depth: lazy forests, the degree lemma, why cascading cuts matter, an invariant checker and measured costs
How a Fibonacci heap works as a mergeable priority queue: insert, merge, extract-min with consolidation, decrease-key with cascading cuts and delete, …
Read article →Finger Search, in depth: galloping, O(log d) searches, near-optimal intersections, level-linked trees and skip-list fingers
Finger search from first principles: galloping search with measured comparison counts, the sqrt(n) break-even, intersecting 1,000 keys with 1,000,000 …
Read article →Fixed-Point Arithmetic, in depth: Q formats, double-width products, rounding traps, saturation and int8 requantization
Fixed-point arithmetic from first principles: Qm.n formats, conversion error, Q15 and Q16.16 multiplication, rounding and the Python versus C negative…
Read article →Advanced Flow Networks, in depth: vertex capacities, circulations with demands, lower bounds and min flow
Reductions that turn real flow problems into plain max flow: super sources and sinks, undirected edges, vertex splitting and disjoint paths, circulati…
Read article →Floyd-Warshall, in depth: the all-pairs recurrence, path reconstruction, negative cycles, semirings, blocked versions and incremental updates
Floyd-Warshall from first principles: why k must be the outer loop and in-place updates are safe, tested Python with path reconstruction, a stage-by-s…
Read article →Ford-Fulkerson Deep Dive: the augmenting-path method, why path choice decides running time, non-termination and measured augmentation counts
Ford-Fulkerson as a method with pluggable path selection: residual graph invariants, a paired-edge Python implementation, a worked example with its mi…
Read article →Futexes, in depth: the compare-and-sleep contract, kernel wait queues, requeue, PI and robust futexes, futex2 and a futex semaphore
How Linux futexes work beneath every mutex and condition variable: the compare-and-sleep rule that prevents lost wakeups, hashed kernel wait queues an…
Read article →Gale-Shapley Deep Dive, in depth: proposal counts, the tight n(n-1)+1 worst case, parallel rounds and incremental re-matching
The cost side of Gale-Shapley deferred acceptance: order-independent proposal counts, a construction that hits n(n-1)+1, measured averages near n ln n…
Read article →Game Theory, in depth: computing winning moves and equilibria, from Grundy numbers to linear programs and regret matching
Algorithms for solving games: classifying a game, Sprague-Grundy numbers and the XOR rule with a worked Nim and subtraction-game sum, minimax for part…
Read article →Gaussian Elimination, in depth: row operations, partial pivoting, PA = LU, growth factors and exact elimination mod p and over GF(2)
Gaussian elimination from first principles: a worked 3 by 3 example with partial pivoting, code for floating point, modular and GF(2) arithmetic, grow…
Read article →Genetic Algorithms, in depth: encoding, selection, crossover, mutation and constraint repair, measured against an exact optimum
Genetic algorithms from first principles: when to use one, the generational loop, representation and order crossover, tournament selection and elitism…
Read article →GPU-Specific Algorithms, in depth: SIMT constraints, work and span, and the reduce, histogram, compaction and radix-sort toolkit
How GPU hardware reshapes algorithm design: warps, divergence, coalescing and latency hiding; work-span cost; CUDA warp-shuffle reduction and privatiz…
Read article →Gradient Descent Convergence, in depth: the descent lemma, O(1/k) and linear rates, acceleration, backtracking and the SGD noise floor
Convergence analysis of gradient descent from first principles: L-smoothness and the descent lemma, nonconvex, convex, strongly convex and PL rates, N…
Read article →Gradient Descent Theory, in depth: steepest descent under a norm, the eigenvalue view of step size, preconditioning, momentum, PL and implicit bias
Gradient descent theory from first principles: steps as minimisers of a local model under a norm, the linear-system view with per-eigenvalue contracti…
Read article →Grammar-Based Compression, in depth: straight-line programs, Re-Pair and Sequitur, random access without decompression and honest measurements
Grammar-based compression explained: straight-line programs, the smallest-grammar problem and its link to LZ77, a tested Re-Pair implementation traced…
Read article →Graph Coloring, in depth: bounds, greedy orderings, DSATUR, exact backtracking, and how compilers and schedulers use it
A practical guide to graph colouring: proper colourings and the chromatic number, the bounds that tell you when you are done, why greedy colouring dep…
Read article →Gray Code, in depth: the reflected construction, conversions, the ruler sequence, async FIFO pointers and O(1) subset enumeration
Gray code from first principles: why one-bit changes make sampling safe, the reflected construction and n XOR n shifted right by one, Gray to binary b…
Read article →Greedy Algorithms, in depth: when the locally best choice is globally right, and how to prove it
Greedy algorithms from first principles: the greedy-choice property and optimal substructure, exchange and stays-ahead proofs, activity selection and …
Read article →Dijkstra as a Greedy Algorithm, in depth: the exchange proof, the one-line difference from Prim, and monotone bucket queues
Dijkstra seen through the greedy lens: the greedy-choice proof and where non-negativity enters, label-setting versus label-correcting, a shared Dijkst…
Read article →Gas Station Circular Problem, in depth: finite tanks, every valid start, minimum capacity and live updates
The circular gas station problem with a tank limit: why monotonicity keeps the skip lemma alive, a proven O(n) algorithm, binary search for the smalle…
Read article →Interval Scheduling, in depth: optimality certificates, sweep by start, weighted machines as min-cost flow and the variants that turn NP-hard
Beyond earliest finish first: the stabbing-point certificate that proves a schedule optimal, the sweep-by-start greedy, a map of which variants are ea…
Read article →Job Sequencing with Deadlines, in depth: the slack test, online admission with eviction, release windows, m machines and weighted lengths
Beyond the textbook greedy for job sequencing with deadlines: the counting feasibility test, a deadline-order heap for m machines, online admission wi…
Read article →Meeting Rooms, in depth: numbered rooms with delays, online booking, k-overlap limits and why capacity breaks the greedy
Meeting rooms beyond the room count: the two-heap simulation for numbered rooms with delayed meetings, online single-room booking, a k-overlap booking…
Read article →Hall's Marriage Theorem, in depth: the alternating-tree proof, violator certificates, the deficiency formula and the corollaries that use it
Hall's marriage theorem from first principles: statement, the augmenting-path proof, a tested function that returns a matching or a verified viol…
Read article →The Halting Problem, in depth: the diagonal proof in code, semi-decidability, reductions, Rice's theorem and engineering with budgets
Why no algorithm can decide whether every program halts: Turing's diagonal proof as Python, recognisers versus deciders, reductions to everyday q…
Read article →Hamiltonian Path NP-Hard Reduction, in depth: the 3-SAT row gadget, both proof directions, undirected and cycle variants, and a brute-force check
Why Hamiltonian path is NP-complete: the 3-SAT to directed Hamiltonian path construction, size formulas, the forward proof and the detour lemma for th…
Read article →Hash Tables
What the O(1) in a hash table really promises: index reduction, probe-count arithmetic, chaining vs open addressing vs SwissTable, deletion, and resiz…
Read article →Hazard Pointers, in depth: publish and validate, slot counts per structure, hand-over-hand traversal, the scan bound and the C++26 API
Implementing hazard pointers for lock-free structures: the publish and validate loop and its store-load fence, a minimal C++ domain with retire and sc…
Read article →Heap Implementation: Binary Heap Priority Queue Operations
Binary heap implementation for a priority queue: the array layout, sift-up and sift-down, O(n) heapify, heapsort, d-ary heaps, decrease-key, and its l…
Read article →Heavy-Light Decomposition, in depth: heavy-first layout, path and subtree queries, edge weights and an iterative build
Heavy-light decomposition from first principles: why light edges halve subtree size, a heavy-first DFS that makes chains and subtrees contiguous, an i…
Read article →Heavy Path Decomposition Deep Dive: the light-edge proof, LCA without tables, order-aware path folds, O(log n) static queries and dynamic DP with (max,+) matrices
Heavy path decomposition beyond the template: the correct heavy-child definition and the log n proof, an iterative build, LCA by chain jumping, direct…
Read article →Hirschberg's Algorithm, in depth: optimal sequence alignment in linear space, the midpoint split and a tested implementation
Hirschberg's linear-space alignment for scored global alignment: why the traceback table is the memory wall, how forward and reverse score rows f…
Read article →HKDF, in depth: extract-then-expand key derivation, salt and info, TLS 1.3 labels and the mistakes that break it
HKDF (RFC 5869) from first principles: why extraction and expansion are separate, tested Python that reproduces the RFC vectors, salt versus info, the…
Read article →HyperLogLog, in depth: why the estimator works, choosing precision, validating an implementation and querying stored sketches
HyperLogLog from first principles: rank and stochastic averaging, the harmonic-mean estimator and its corrections, precision versus error, a tested re…
Read article →HyperLogLog Streaming Applications, in depth: windowed distinct counts, keyed sketch state, late data and fan-out detection
Running HyperLogLog inside a stream processor: why max-merge makes sketches replay-safe, tumbling rings versus a sliding HyperLogLog, keyed state sizi…
Read article →HNSW architecture
Deep-dive on HNSW: layered proximity graphs, greedy descent and efSearch beam search, geometric level assignment, the diversity neighbor heuristic, fi…
Read article →Hopscotch Hashing, in depth: bounded neighbourhoods, hop bitmaps, backward displacement and concurrent tables
Hopscotch hashing from first principles: the H-slot neighbourhood invariant, bitmap lookups, backward-hop insertion with a worked example, tested Pyth…
Read article →Hungarian Algorithm, in depth: the LP dual, reduced costs, two hand traces, O(n^3) shortest augmenting paths and production use
The Hungarian algorithm for the assignment problem from first principles: the linear program and its dual, potentials as an optimality certificate, tw…
Read article →HyperLogLog architecture, in depth: registers, sparse encoding, estimators and merge in production
How a production HyperLogLog is built: hash choice and canonicalisation, precision and memory, dense 6-bit register packing, sparse encodings in HLL++…
Read article →IEEE 754 Floating Point, in depth: the encoding, correct rounding, special values, ulp comparison, compensated summation and float32 to bfloat16 conversion
IEEE 754 binary floating point from first principles: bit layouts, decoding values exactly in Python, round to nearest even, signed zero, subnormals, …
Read article →Interior Point Methods, in depth: the central path, primal-dual Newton steps, Mehrotra's predictor-corrector and real LP solvers
Primal-dual interior-point methods for linear programming from first principles: perturbed KKT conditions, the central path, normal equations, a teste…
Read article →Integer Programming Hardness, in depth: the 3-SAT reduction, why IP is in NP, strong NP-hardness and the structures that make it easy
Why integer programming is hard and when it is not: a tested reduction from 3-SAT to 0-1 feasibility, the bounded-solution argument for NP membership,…
Read article →Integer Programming and LP, in depth: LP relaxations, branch and bound, cutting planes and models a solver can finish
Integer programming from linear programming: polyhedra and vertices, duality as a bound, LP relaxation and integrality gap, total unimodularity, branc…
Read article →Iterative Deepening Search, in depth: IDA* thresholds, the real-valued-cost iteration explosion, (1+eps) bound growth and iterative-deepening alpha-beta
Iterative deepening as a control loop beyond depth bounds: tested IDA* code, why real-valued costs drive iterations from 5 to 260, a (1+eps) threshold…
Read article →IVF-PQ Index Explained: Inverted Lists and Product Quantization
How the IVF-PQ index used in vector search works: nlist and nprobe coarse search, product quantization codebooks, ADC lookup tables, recall vs memory …
Read article →Johnson's Algorithm, in depth: all-pairs shortest paths with negative edges through reweighting
Johnson's algorithm explained from first principles: why vertex potentials preserve shortest paths, the Bellman-Ford plus Dijkstra pipeline, a fu…
Read article →Jump Point Search, in depth: path symmetry, forced neighbours without corner cutting, a tested implementation and when it beats A*
Jump point search from first principles: why A* wastes work on grid symmetry, the movement model, pruning and forced-neighbour rules without corner cu…
Read article →Karatsuba Multiplication, in depth: limb arrays, the subtractive middle term, cutoffs, lopsided operands and testing
Implement Karatsuba multiplication on limb arrays: the polynomial view, why the subtractive middle term avoids carry growth, a worked example, real cu…
Read article →Karmarkar's Algorithm, in depth: the canonical form, projective scaling, the potential function and a tested implementation
Karmarkar's 1984 projective method for linear programming from first principles: the canonical form and how to reach it, the projective transform…
Read article →Karp Reductions, in depth: many-one versus Cook reductions, Karp's 21 problems, and a tested 3-SAT to 3-colouring reduction
Karp reductions from first principles: the three obligations of a polynomial-time many-one reduction, how they differ from Cook reductions, Karp'…
Read article →KD-Tree Range Queries, in depth: box classification, counting with subtree sizes, the square-root bound, ball queries and updates
How k-d trees answer orthogonal range and radius queries: disjoint, contained and partial nodes, a tested implementation with tight boxes and counts, …
Read article →KD-Tree, in depth: bounding-box pruning, best-first search, range counting and when it stops paying
Engineering a k-d tree that is fast and correct: tight bounding boxes as lower bounds, best-first nearest-neighbour search with early termination, ran…
Read article →KMP Algorithm
How the Knuth-Morris-Pratt algorithm finds a pattern in text in O(n+m) by precomputing a failure function.
Read article →Knapsack Problem, in depth: 0/1, unbounded and bounded DP, reconstruction, meet-in-the-middle, branch and bound and approximation
A first-principles guide to the knapsack family: why greedy fails, the 0/1 recurrence with a worked table, one-dimensional loop direction, reconstruct…
Read article →König's Theorem, in depth: three proofs, Δ-colouring bipartite multigraphs, switch scheduling and Dilworth
Kőnig's theorems for bipartite graphs: matching equals vertex cover proved via augmenting paths, max-flow and LP duality, Hall as a corollary, a …
Read article →Kruskal's MST Deep Dive, in depth: the matroid reason greedy works, where the time goes, float keys and deterministic ties, incremental updates, Euclidean MST and verification
Kruskal's algorithm beyond the textbook: the graphic matroid and the Rado-Edmonds theorem, when greedy fails, sort-dominated cost, IEEE 754 sort …
Read article →Kth Order Statistics, in depth: quickselect with three-way partition, the expected-cost argument, heaps for streams, Floyd-Rivest, multiselect and the library calls
How to find the kth smallest value without sorting: definitions that prevent bugs, iterative three-way quickselect, why expected work is linear, the s…
Read article →Lagrangian Duality, in depth: the dual function, weak and strong duality, Slater and KKT, duality gaps and Lagrangian relaxation
General Lagrangian duality from first principles: why the dual function is always concave, weak duality, Slater's condition and strong duality, K…
Read article →Las Vegas Algorithms, in depth: runtime distributions, heavy tails, Luby restarts and engineering always-correct randomness
Las Vegas algorithms are always correct, with random running time. Three ways to build them, measured runtime distributions for quickselect, non-resid…
Read article →Lowest Common Ancestor, in depth: ancestor tests, path queries, rerooting, virtual trees and merge bases in DAGs
What to build once you have LCA: an O(1) ancestor test from entry and exit times, binary lifting driven by that test, weighted distance and path maxim…
Read article →LCA via Binary Lifting, in depth: the jump table, k-th ancestors, ancestor binary search, growing trees and when a sparse table wins
Binary lifting from first principles: the doubling identity, sizing LOG, row-major layout, an iterative BFS build, k-th ancestor queries, equalise-the…
Read article →Longest Common Subsequence, in depth: the recurrence, traceback, linear-space Hirschberg and how diff uses it
Longest common subsequence from first principles: why brute force fails, deriving the recurrence, a filled table for ABCBDAB and BDCABA, tested Python…
Read article →Leftist Heap, in depth: the rank invariant, a logarithmic right spine, merge-based operations, a traced example and persistent variants
How leftist heaps merge in O(log n): the null-path rank and leftist property, the proof that the right spine has at most log2(n+1) nodes, Python for m…
Read article →Lifelong Planning A* (LPA*), in depth: local consistency, the key and stop rule, a traced replan, tested code and measured costs against repeated A*
Lifelong Planning A* from first principles: g and rhs, why local consistency gives exact distances, overconsistent and underconsistent expansions, a c…
Read article →Line Sweep Algorithms, in depth: events, status structures, tie-break order as correctness, skyline, sweep-and-prune and production pitfalls
The line sweep as a design method: events, status structure and invariant, why the order of ties is part of correctness, tested sweeps for maximum ove…
Read article →Linear Sieve, in depth: the exactly-once proof, lowest-prime-factor tables, multiplicative functions and measured speed against Eratosthenes
The linear sieve from first principles: why every composite is marked exactly once, a hand trace to 30, lowest-prime-factor tables for fast factorisat…
Read article →Lock-Free Queues, in depth: what FIFO means under concurrency, the SPSC-to-MPMC ladder, Vyukov's MPSC queue, fetch-and-add designs and a stress harness
Choosing and verifying lock-free queues: linearizability and per-producer FIFO, progress guarantees, the SPSC to MPMC ladder, Vyukov's intrusive …
Read article →Lock-Free Stack, in depth: linearization points, ABA under garbage collection, tagged indices, elimination backoff and jcstress
Beyond the first Treiber stack: linearizability and lock-freedom defined, linearization points for every path, why garbage collection prevents ABA onl…
Read article →LP Duality, in depth: deriving the dual, weak and strong duality, complementary slackness, shadow prices and the dual simplex method
Linear programming duality from first principles: the dual as the best upper bound, rules for dualising any LP, Farkas and strong duality, a complemen…
Read article →LP Rounding for Approximation, in depth: integrality gaps, threshold rounding, extreme points, unrelated-machine scheduling and iterative rounding
Deterministic LP rounding from first principles: the relax-solve-round pipeline, integrality gaps, threshold rounding for set cover, extreme-point rou…
Read article →LRU cache architecture
Deep-dive on LRU cache: hash map + linked list, admission policies (TinyLFU), concurrency, TTL, weighted entries, variants.
Read article →LSM Tree Compaction Architecture in Depth
LSM tree compaction in depth: the k-way merge and tombstone rules, write, read and space amplification math, leveled, tiered, time-window and unified …
Read article →LSM-Tree, in depth: invariants, a working implementation, the k-way merge and the amplification cost model
The log-structured merge tree as a data structure: why batching sorted runs makes writes cheap, the four invariants, a runnable mini-LSM in Python wit…
Read article →LSM Tree vs B-Tree: Write, Read and Space Amplification
LSM tree vs B-tree for write-heavy vs read-heavy workloads: in-place vs append-and-merge, write, read and space amplification, compaction and bloom fi…
Read article →LZ4 Compression, in depth: tokens and length bytes, a verified block decoder and encoder, overlapping copies, hostile input and the frame format
LZ4 at the byte level: the token, 255-continuation lengths and 2-byte offsets, end-of-block rules, a safe decoder and greedy encoder matched byte-for-…
Read article →LZ78 Compression, in depth: incremental parsing, the phrase trie, LZW and its KwKwK case, dictionary-full policies and measured ratios
LZ78 from first principles: the distinct-phrase parse, a tested encoder and decoder, the trie that makes it linear, LZW and the KwKwK decoder case, va…
Read article →Matrix Exponentiation, in depth
Matrix exponentiation beyond the basics: augmented state for constant, polynomial and exponential terms, prefix sums and matrix geometric series, Kita…
Read article →Matroid Theory + Greedy, in depth: testing whether your greedy is safe, laminar caps, crossing constraints and sensitivity ranges
The matroid greedy theorem as an engineering contract: a brute-force axiom checker, a traced laminar-cap ranking example, measured losses when cap fam…
Read article →Matroid Intersection, in depth: exchange graphs, shortest augmenting paths, the rank certificate and weighted versions
Matroid intersection from first principles: common independent sets, the exchange graph, why augmenting paths must be shortest, a Python implementatio…
Read article →Matroids, in depth: independence oracles, rank and circuits, duality and minors, and greedy algorithms you can prove
Matroids from first principles for working engineers: equivalent definitions, a catalogue of matroids with their oracles and costs, a generic greedy w…
Read article →Maximum Clique Problem, in depth: colouring bounds, bitset branch and bound, k-core pruning and when to stop
Solving maximum clique exactly in practice: maximal versus maximum, branch and bound with greedy-colouring bounds, a tested bitset implementation, a w…
Read article →Maximum Independent Set, in depth: vertex cover and clique duality, easy graph classes, branch-and-reduce measured, greedy bounds and weighted trees
Maximum independent set from first principles: its identities with vertex cover and clique, the graph classes where it is polynomial, a tested branch-…
Read article →General Graph Matching, in Depth
Maximum matching in general (non-bipartite) graphs: Berge's lemma, why odd cycles defeat the bipartite search, Edmonds' blossom contraction,…
Read article →Median of Medians, in depth: the 30 percent guarantee, the recurrence with constants, why groups of five, and introselect in real libraries
Deterministic linear-time selection from first principles: the BFPRT algorithm, the counting argument behind its pivot guarantee, the recurrence solve…
Read article →Meet in the Middle, in depth: splitting 2^n into two 2^(n/2) searches, joins, bidirectional search and the double-DES attack
Meet in the middle as a general technique: when a problem decomposes, the time and memory cost model, sorted sum generation by merging, exact-count, c…
Read article →Mergesort
Mergesort in depth: the merge step and where stability comes from, top-down versus bottom-up, TimSort's runs and galloping, and external k-way me…
Read article →Merkle trees -- efficient verification of large data
Deep-dive on Merkle trees: hashing data blocks into leaves and up to a single root, tamper evidence (any change alters the root), O(1) root comparison…
Read article →Miller-Rabin Primality Test, in depth: from Fermat to strong pseudoprimes, deterministic 64-bit bases, C and Python code, and adversarial composites
A first-principles guide to the Miller-Rabin primality test: why the Fermat test fails on Carmichael numbers, square roots of one, the 4^-k error boun…
Read article →Min Cost Max Flow, in depth: residual costs, the negative cycle condition, successive shortest paths with potentials and modelling
Minimum cost flow from first principles: residual graphs with negated reverse costs, the no negative cycle optimality theorem, successive shortest pat…
Read article →Minimum Spanning Arborescence, in depth: Chu-Liu/Edmonds from first principles with a tested implementation
The directed MST explained: why Kruskal and Prim fail on directed graphs, cheapest incoming edges, cycle contraction with reduced costs, a step-by-ste…
Read article →Minimax Deep Dive, in depth: game values, exact solving with memoization, depth-aware scores, retrograde analysis and where minimax stops applying
A deep dive into minimax as exact game solving: Zermelo and backward induction, a memoized tic-tac-toe solver (549,946 tree nodes vs 5,478 positions),…
Read article →Möbius Function + Inversion, in depth: the divisor-sum identity, linear sieve, coprime and squarefree counting, and Mertens via Du's sieve
The Möbius function from first principles: definition, the divisor-sum identity and proof, Möbius inversion with a worked lattice, a linear sieve, O(√…
Read article →Monte Carlo Algorithms, in depth: one- and two-sided error, amplification, Freivalds' check, Schwartz-Zippel and estimation with confidence intervals
How Monte Carlo algorithms trade bounded error for speed: one-sided versus two-sided error, amplification by repetition and majority vote, Freivalds&#…
Read article →Moving Percentile and Median, in depth: rank definitions, sorted windows, two heaps with lazy deletion, Fenwick ranks and when to approximate
Exact sliding-window percentiles from first principles: nearest-rank versus interpolated definitions, why medians resist outliers, a bisect sorted win…
Read article →Multiplicative Weights, in depth: weighted majority, Hedge and its regret proof, measured runs, and solving games and LPs
Multiplicative weights from first principles: experts and regret, the weighted majority mistake bound, Hedge with log-space code and its regret proof,…
Read article →Needleman-Wunsch Global Alignment, in depth: recurrence, traceback, affine gaps, variants and scaling
Global sequence alignment with Needleman-Wunsch: the scoring model, the recurrence and traceback, a worked GATTACA example, tested code for linear and…
Read article →Negamax Framework, in depth: the side-to-move contract, window negation, fail-soft bounds, transposition-table flags, mate scores and PVS measured
Negamax as an engine framework: the side-to-move scoring contract, why children get the (-beta, -alpha) window, fail-hard versus fail-soft measured, t…
Read article →NP-Complete Problems, in depth: the core catalogue, certificates, weak versus strong hardness, choosing a reduction source, the 3-SAT phase transition and a SAT-solved scheduling example
A field guide to the NP-complete problems engineers actually meet: the reduction family tree, a reference card of certificates and approximability, ho…
Read article →NP-Completeness, in depth: decision problems, verifiers, polynomial reductions, a tested 3-SAT to Independent Set proof, and what to do when your problem is hard
NP-completeness from first principles: decision problems, certificates and verifiers, the direction of polynomial reductions, a worked and tested 3-SA…
Read article →NP-Hard Problems, in depth: hardness beyond NP, counting and games, parameterized algorithms with a tested vertex cover kernel, and exact solvers under a deadline
What NP-hard really means and what to do about it: optimisation, #P, PSPACE and undecidable problems, fixed-parameter tractability with a tested Buss …
Read article →Number Theoretic Transform, in depth: roots of unity mod p, a hand-traced example, tested code, three-prime CRT and the negacyclic NTT in ML-KEM
The NTT from first principles: why roots of unity exist mod p, NTT-friendly primes, a full multiplication traced by hand, iterative code, Garner CRT f…
Read article →Number Theory Algorithms, in depth: gcd, extended Euclid, modular inverses, fast exponentiation, sieves, Euler's phi and the Chinese remainder theorem
The core number theory toolkit for programmers, built from first principles: Euclid and extended Euclid, modular inverses, square-and-multiply exponen…
Read article →Advanced Number Theory, in depth: group order, primitive roots, baby-step giant-step and Pohlig-Hellman discrete logs, built on a factoring pipeline
How the structure of the multiplicative group mod p controls discrete logarithms: element order, primitive roots, factoring p - 1, baby-step giant-ste…
Read article →Offline LCA, in depth: the Tarjan algorithm with union-find, its invariant, a hand trace, an iterative implementation, the representative-label bug and measured cost
Answer a whole batch of lowest common ancestor queries in one DFS: the invariant behind the Tarjan offline algorithm, a traced example, a tested itera…
Read article →Offline Query Processing, in depth: reorder the queries, sweep once, and turn hard online problems into Fenwick and union-find exercises
Offline query processing explained from the contract up: sort by right endpoint with a Fenwick tree, threshold queries with union-find, reversed time …
Read article →Online Algorithms, in depth: competitive ratios, ski rental, paging, randomisation and learning-augmented decisions
How to design and analyse algorithms that decide before seeing the future: competitive ratio, break-even ski rental, LRU versus Belady with tested cod…
Read article →Online LCA, in depth: streaming queries, growing trees, jump pointers with O(1) insertion and when to use a sparse table
Online lowest common ancestor: the two meanings of online, binary lifting, Euler tour + sparse table and the ±1 correction, a tested jump-pointer stru…
Read article →Optimization Landscape, in depth: curvature, conditioning, saddles, sharpness and what they mean for training
The geometry of loss functions from first principles: gradients and Hessians, convexity and the condition number, saddle points in high dimensions, sh…
Read article →Pairing Heap, in depth: one link operation, the two-pass delete-min, an iterative implementation and what is still unproven
Pairing heaps from first principles: child/next-sibling layout, link, insert, two-pass delete-min, decrease-key and delete, a complete iterative imple…
Read article →Pairwise Independence, in depth: strongly universal hashing, XOR bits, Chebyshev, and derandomised MAX-CUT
Pairwise independence from first principles: universal versus strongly universal families, the (ax+b) mod p construction and the a != 0 trap, measured…
Read article →Parallel BFS, in depth: level-synchronous frontiers, direction-optimizing search and what limits speedup
How to make breadth-first search fast in parallel: CSR storage, level-synchronous frontiers, atomic parent claims, the bottom-up step, the alpha/beta …
Read article →How a Matrix Multiply Runs on a GPU: Tiling, Shared Memory, and Tensor Cores, with Pseudocode
A step-by-step walk from a naive CUDA matrix multiply to shared-memory tiling, register blocking and tensor-core WMMA kernels, with the arithmetic-int…
Read article →Parallel Prefix Sum (Scan), in depth: work and span, Hillis-Steele and Blelloch, a CUDA warp and block scan, decoupled look-back, and what scan builds
Parallel prefix sum from first principles: inclusive and exclusive scan, work and span, Hillis-Steele and Blelloch with real traces, a CUDA warp and b…
Read article →Parallel Sorting, in depth: work and span, merge-path partitioning, sample sort with measured oversampling, scan-based radix sort and the library calls to use
How parallel sorts split work evenly and stitch results together: the work-span model, merge-path co-ranking for parallel merge, sample sort with meas…
Read article →Parameterized Complexity, in depth: FPT versus XP, kernels, bounded search trees, colour coding, treewidth and W[1]-hardness
How to solve NP-hard problems exactly when a parameter is small: FPT and XP, Buss and LP kernels, branching with a working vertex cover solver, colour…
Read article →Partial Sort, in depth: bounded heaps, select-then-sort, partial quicksort, library calls and sharded top-N
How to get the k smallest items in order without sorting all n: the bounded max-heap, quickselect followed by a prefix sort, partial quicksort, C++/Nu…
Read article →PBKDF2, in depth: the block function, HMAC key caching, test vectors, WPA2, WebCrypto and JCA, iteration calibration and the long-password denial of service
PBKDF2 as an engineering artefact: what the block function computes, why caching the keyed HMAC state matters, RFC 6070 and WPA2 vectors, WPA2 as a ca…
Read article →The PCP Theorem, in depth: probabilistically checkable proofs, the gap-3SAT form, a runnable linearity test, how the proof works and the hardness-of-approximation map
The PCP theorem from first principles: verifiers with logarithmic randomness and constant queries, its equivalence with gap-3SAT, a runnable BLR linea…
Read article →Perfect Hashing, in depth: FKS two-level tables, hash-and-displace MPHFs, the 1.44-bit bound and the unknown-key trap
Perfect hashing from first principles: perfect, minimal and order-preserving functions, the 1.44 bits per key lower bound, the FKS two-level scheme wi…
Read article →Persistent Data Structures, in depth: path copying, fat nodes, persistent segment trees, wide tries and the amortization trap
How persistent data structures keep every version cheaply: partial, full and confluent persistence, path copying versus fat nodes and node copying, a …
Read article →Persistent Union-Find, in depth: path-copied arrays, union by rank without compression, timestamped partial persistence and the Conchon-Filliatre design
Keeping every version of a disjoint-set forest: why path compression and amortisation break under persistence, a tested fully persistent union-find on…
Read article →Persistent Treap, in depth: path-copying split and merge, the shared-priority trap, size-weighted merges and versioned sequences
Build a persistent treap: immutable nodes, path-copying split and merge, implicit-key versioned sequences, why stored priorities degenerate when versi…
Read article →Planar Graph Algorithms, in depth: embeddings, faces, duality, min cut via dual shortest paths, separators and Baker's technique
How to exploit planarity after testing for it: Euler's formula consequences, rotation systems and face tracing, the dual graph, a tested min s-t …
Read article →Pollard's Rho Factorization, in depth: the birthday bound, Floyd and Brent cycle finding, batched gcds, a complete factoring driver and its failure modes
Pollard's rho from first principles: why a walk modulo a hidden prime collides after about the square root of p steps, a hand trace on 8051, Floy…
Read article →Polygon Algorithms, in depth: validation, winding, convexity, centroids, ear-clipping triangulation and clipping
A working polygon toolkit with tested Python: normalising and validating rings, convexity and area centroids, ear-clipping triangulation with holes, S…
Read article →Polygon Area, in depth: the shoelace derivation, exact integers and Pick's theorem, cancellation at map coordinates, holes, self-intersection and area on the Earth
Polygon area for production code: the shoelace formula derived, an exact integer worked example checked with Pick's theorem, measured float cance…
Read article →Polynomial Hashing, in depth: evaluation at a random point, the n/p bound, length pitfalls, multiset and tree fingerprints, and Poly1305
Polynomial hashing as a general fingerprinting tool: why evaluation at a random point mod a prime gives an n/p collision bound, the variable-length tr…
Read article →Population Count, in depth: hardware instructions, compiler flags, bulk SIMD counting, Hamming distance for binary embeddings, GPU warp compaction and rank
Popcount as an engineering tool: portable algorithms, what compilers emit with and without POPCNT, language APIs, AVX-512 and Harley-Seal bulk countin…
Read article →Potential Method for Amortized Analysis, in depth: defining the potential, binary counters, growth factors, shrinking without thrashing and testing a potential in code
The potential method for amortized analysis from first principles: the telescoping identity, a binary counter, dynamic arrays with any growth factor, …
Read article →PRAM Model, in depth: EREW, CREW and CRCW, work and span, Brent's bound, pointer jumping and what survives on GPUs
The PRAM from first principles: the synchronous shared-memory machine, the EREW, CREW and CRCW conflict rules, work, span and Brent's bound, a te…
Read article →Sieve of Eratosthenes, in depth: a hand trace, the n log log n argument, odd-only and segmented sieves, memory layouts and cache-aware production use
The Sieve of Eratosthenes from first principles: a worked trace to 30, why crossing off starts at p squared, why the cost is n log log n, tested Pytho…
Read article →PRM, in depth: the roadmap as a reusable asset, with Halton sampling, component-aware queries and local repair when obstacles appear
Probabilistic roadmaps as long-lived infrastructure: a tested 2D PRM with a k-d tree, component checks that reject impossible queries without a search…
Read article →Probabilistic Counting, in depth: Morris counters, Flajolet-Martin and PCSA, linear counting and KMV, and how to choose
Counting events and distinct items in log or log log memory: the Morris approximate counter and its base-(1+a) variant, Flajolet-Martin and PCSA with …
Read article →Probability in Algorithms, in depth: Las Vegas and Monte Carlo contracts, amplification, Freivalds, fingerprinting and Karger's min cut
Designing with randomness: the Las Vegas and Monte Carlo contracts, one- and two-sided error, amplification by repetition and majority vote, Freivalds…
Read article →Probability DP, in depth: forward distributions, backward expectations, cycles and exact answers
Probability and expectation dynamic programming from first principles: Markov state design, forward versus backward recurrences, self-loops, cyclic ch…
Read article →PTAS and FPTAS, in depth: approximation schemes, a trimming FPTAS, Graham's scheduling PTAS and the strong NP-hardness barrier
Approximation schemes from first principles: PTAS, EPTAS and FPTAS running-time shapes, the three design techniques, a subset-sum FPTAS by trimming, G…
Read article →PTAS and FPTAS Approximation Schemes, in depth: turning an exact DP into an FPTAS by state trimming, the bin packing asymptotic scheme, and testing the guarantee
Build approximation schemes yourself: the state-trimming recipe that turns a pseudo-polynomial DP into an FPTAS, measured on fixed-machine makespan, a…
Read article →Push-Relabel Algorithm, in depth: building a highest-label solver with gap and global relabelling, then proving its answer
An engineering guide to push-relabel max flow: edge-array layout, a complete highest-label Python solver with gap and global relabelling, a traced exa…
Read article →Quicksort
Quicksort in depth: the partition invariant, Lomuto vs Hoare, pivot choice, three-way partitioning, stack bounding, and what introsort and pdqsort rea…
Read article →The quotient filter
Deep-dive on the quotient filter: splitting a key's hash into a quotient (home slot) and a stored remainder, the three metadata bits that encode …
Read article →R-Tree, in depth: bounding rectangles, Guttman splits, R-star reinsertion, best-first kNN and bulk loading
How R-trees index objects with extent: invariants, window search, ChooseSubtree and quadratic splits, R* overlap rules and forced reinsertion, best-fi…
Read article →Random Permutation, in depth: Lehmer-code ranking and unranking, keyed permutations you never store, exact bucket shuffles and the statistics that test them
Random permutations beyond the in-memory shuffle: the factorial number system with tested rank and unrank, Feistel permutations with cycle-walking for…
Read article →Random Selection, in depth: k of n without replacement with sparse Fisher-Yates, Floyd's algorithm, Algorithm S, unbiased integers and hash-based samples
Uniformly sampling k distinct items from a known n: sparse partial Fisher-Yates for huge ID spaces, Floyd's set-based algorithm with its proof, K…
Read article →Random Walks, in depth: gambler's ruin, the square-root law, walks on graphs, hitting and mixing times, sampling and randomized 2-SAT
Random walks from first principles: gambler's ruin probabilities and durations, sqrt(n) spread and Polya recurrence, stationary distributions on …
Read article →Randomized Rounding, in depth: LP relaxations, set cover, Chernoff bounds, MAX-SAT and derandomization
Randomized rounding from first principles: why rounding fractional LP solutions by probability preserves cost in expectation, the O(log n) set cover a…
Read article →Range Coder, in depth: byte-wise renormalization, carries with a cache and 0xFF run, LZMA's adaptive bit model and the frequency path
How a range coder works from first principles: the 32-bit low and range registers, three ways to handle carries, LZMA's 11-bit adaptive probabili…
Read article →Range Updates + Point Queries, in depth: difference arrays, Fenwick trees and range sums
Range updates with point and range queries from first principles: difference arrays for offline batches, a Fenwick tree over differences for online us…
Read article →Rank + Select Structures, in depth: conventions, constant-time select, select-in-word with PDEP, cache-aware layouts and an oracle test harness
Engineering a production rank/select bitvector: one set of conventions, a hand-checked 16-bit example, sampled select with sparse-interval handling, P…
Read article →Red-Black Tree, in depth: invariants, the height proof, insertion and deletion case by case, and how to test them
How red-black trees guarantee O(log n) worst-case operations: the five invariants and the 2 log(n+1) height proof, rotations, insert and delete fix-up…
Read article →Regular Expressions, in depth: from pattern to Thompson NFA, lockstep simulation, why backtracking explodes, and patterns that cannot hang
How regular expressions really execute: a recursive-descent parser, Thompson's NFA construction, lockstep simulation in O(m*n), a measured trace,…
Read article →Rendezvous Hashing Architecture, in depth: score functions, weighted HRW, failure-domain-aware replicas and precomputed tables
A first-principles guide to rendezvous (highest random weight) hashing: why only K/n keys move, building a score function that really mixes key and no…
Read article →Reservoir sampling architecture, in depth: skip-based sampling, mergeable bottom-k keys, weighted variants and windows
Reservoir sampling as a production system: Algorithm L to skip most random draws, the bottom-k random-key form that merges across shards, correct merg…
Read article →Reservoir sampling
Deep-dive on reservoir sampling (Algorithm R): drawing k items uniformly at random from a stream of unknown length in a single forward pass with O(k) …
Read article →Reverse-Delete Algorithm, in depth: the delete-while-feasible template, matroid duality, and the pruning step of primal-dual algorithms
Reverse-delete beyond spanning trees: a generic pruning loop over any monotone predicate, why it is optimal on matroids (tested via planar duality on …
Read article →Ribbon filter architecture
Deep-dive on the ribbon filter: a static approximate-membership structure that encodes the key set as a solved banded linear system over GF(2), reachi…
Read article →Roaring bitmaps -- compressed bitmaps that stay fast
Deep-dive on roaring bitmaps: the bitmap dilemma (fast but big, or small but slow), chunking the integer space by the high 16 bits, the three adaptive…
Read article →RRT, in depth: rapidly-exploring random trees from first principles, Voronoi bias, a measured 2D planner, RRT-Connect, RRT* rewiring and kinodynamic planning
Rapidly-exploring random trees explained: configuration space, the sample-nearest-steer loop, Voronoi bias, a tested Python planner with shortcutting …
Read article →Run-Length Encoding, in depth: byte formats from pairs to PackBits, worst-case expansion, hostile input, RLE inside real formats and run-aware queries
Run-length encoding from first principles: when runs pay, count-value pairs versus escapes versus PackBits with tested Python and measured sizes, deco…
Read article →SAT Reduction Technique, in depth: reducing your problem to SAT, with model, encode, solve, decode and verify, worked end to end on bounded model checking
Reducing a problem to SAT in order to solve it: choosing variables, writing constraints as implications, decoding models and verifying them independen…
Read article →SAT Solving, in depth: CNF and Tseitin encodings, DPLL to CDCL, 1-UIP clause learning with a traced example, and driving real solvers
Boolean satisfiability from first principles: CNF and DIMACS, Tseitin and cardinality encodings, DPLL and unit propagation, a tested CDCL solver in Py…
Read article →Saturating Arithmetic, in depth: clamp-on-overflow semantics, branchless code, C++26 and Rust APIs, SIMD instructions and the associativity trap
How saturating integer arithmetic works and when to use it: exact semantics for add, sub, neg, abs, mul and narrowing, portable and branchless C, C++2…
Read article →Kosaraju’s SCC Algorithm, in depth: CSR arrays, a counting-sort transpose, memory budgets and the parallel forward-backward variant
Running Kosaraju’s strongly connected components algorithm at scale: CSR graphs, building the transpose by counting sort, iterative array-based passes…
Read article →Segment Intersection, in depth: Shamos-Hoey detection, Bentley-Ottmann reporting, degeneracies and exact arithmetic
Finding intersections among many line segments: the exact pairwise test, the sweep-line adjacency lemma, a tested Shamos-Hoey implementation, Bentley-…
Read article →Segment Tree: Range Queries, Updates, Lazy Propagation
Segment tree explained: why a range sum, min or max query touches O(log n) nodes, the 4n array, O(n) build, point updates, lazy propagation, Fenwick.
Read article →Segment Tree with Lazy Propagation, in depth: the tag algebra, a node-by-node trace, tested affine updates and the composition-order bug
Lazy propagation as algebra: monoid node values, composable tags, the two laws they must obey, a traced example with range multiply and add, tested Py…
Read article →Selection Algorithms, in depth: comparison lower bounds, sorted inputs, weighted medians, radix select and distributed selection
A map of the selection problem family: comparison bounds for min, second smallest, min-max and median, k-th of two sorted arrays and sorted matrices, …
Read article →Selection and Medians, in depth: L1 optimality, the breakdown point, MAD outlier rules, median filters, median-of-means and the geometric median
The median as an engineering tool: why it minimises absolute error, its 50 percent breakdown point, MAD rules that catch outliers three-sigma misses, …
Read article →Seqlock, in depth: proving the retry protocol, the ordering it needs, and a version legal under the C++ memory model
Seqlock correctness from first principles: the counter protocol, an exhaustive interleaving check showing why the odd check and the early increment ar…
Read article →Set Cover Greedy, in depth: the H(n) pricing proof, a tight instance, weighted and lazy greedy, and the variants you will meet
Greedy set cover from first principles: the algorithm and a worked run, the pricing proof of the H(n) and H(d) bounds, a tight instance, Feige and Din…
Read article →SHA-3 (Keccak), in depth: the 1600-bit state, θ ρ π χ ι, rate and capacity, padding and domain bits, SHAKE and KMAC, and a tested implementation
Inside SHA-3: the 5x5 lane state of Keccak-f[1600], the five step mappings, how rate and capacity set security, pad10*1 and the domain bytes that sepa…
Read article →Fisher-Yates Shuffle, in depth: the proof, three classic biased shuffles, PRNG limits, Sattolo and inside-out variants, and shuffling training data
How the Fisher-Yates shuffle produces every permutation with equal probability in O(n): the counting proof, the naive-swap, random-comparator and modu…
Read article →Simplex Algorithm, in depth: vertices, pivots, duals, degeneracy and what real LP solvers do
The simplex method for linear programming from first principles: standard form and slack variables, why optima sit at vertices, a pivot-by-pivot worke…
Read article →Simulated Annealing, in depth: the Metropolis rule, cooling schedules, an O(1)-delta TSP annealer and measured results
Simulated annealing from first principles: the Metropolis acceptance rule and Boltzmann distribution, why logarithmic schedules are proven but unused,…
Read article →Skip Lists Explained: Search, Insert, Lock-Free, Redis, LevelDB
How skip lists work: coin-flip levels, expected O(log n) search, insert and delete with an update vector, lock-free CAS variants, and use in Redis and…
Read article →Sliding Window Minimum, in depth: the monotonic deque invariant, an amortised O(n) proof, time-based windows and DP acceleration
How the monotonic deque computes every sliding window minimum in O(n): the domination argument, the invariant and amortised proof, a traced example, t…
Read article →Snappy Compression, in depth: the varint preamble and four tag types, the reference compressor's skip heuristic, the framing format with masked CRC-32C, and a hardened decoder
How Snappy works byte by byte: the varint length preamble, literal and 1-, 2- and 4-byte-offset copy elements, the reference compressor's 64 KiB …
Read article →Sorting Networks, in depth: comparators, depth and size, the 0-1 principle, Batcher's constructions, SIMD and GPU use
Data-oblivious sorting with comparator networks: depth versus size, a proof and exhaustive checker for the 0-1 principle, odd-even merge and bitonic g…
Read article →Space-Saving architecture
Deep-dive on the Space-Saving algorithm for approximate top-k heavy hitters: a fixed table of k counters, the increment-or-evict-the-minimum rule that…
Read article →Splay Trees, in depth: zig-zig and zig-zag, top-down splaying, the access lemma, adaptive bounds and when not to use them
Splay trees from first principles: why zig-zig folds paths, iterative top-down splay with insert and delete in Python, a worked example on a degenerat…
Read article →Square Root Decomposition, in depth: blocks, lazy tags, sorted blocks and rebuilding on a schedule
Square root decomposition from first principles: why blocks of size sqrt(n) balance the cost, a worked range-add and range-sum example, tested Python,…
Read article →Stable Marriage, in depth: Gale-Shapley deferred acceptance, proposer optimality, incentives, variants and implementation at scale
The stable marriage problem from first principles: blocking pairs, the Gale-Shapley algorithm with a proof sketch and a traced example, the stable lat…
Read article →Stable Matching, in depth: the lattice of all stable matchings, rotations, enumeration, and choosing the egalitarian or minimum-regret answer
Beyond Gale-Shapley: the distributive lattice of stable matchings, rotations and the rotation poset traced on a 4 by 4 example, tested code that enume…
Read article →Stoer-Wagner Min-Cut in practice: preparing real graphs, safe contraction rules, recovering the partition, testing against brute force and HCS clustering
Practical Stoer-Wagner global minimum cut: graph preparation pitfalls, a dense implementation that returns the partition, Padberg-Rinaldi safe contrac…
Read article →Streaming Algorithms, in depth: the one-pass model, Misra-Gries heavy hitters, the AMS sketch, DGIM windows and mergeable summaries
Streaming algorithms from first principles: insert-only, turnstile and sliding-window models, why exact and deterministic answers need linear space, M…
Read article →String Matching, in depth: choosing between naive, Horspool, Rabin-Karp and Two-Way, worst cases and Unicode traps
How to choose and implement an exact string-matching algorithm: the naive baseline and vector scans, Horspool with a worked trace, randomised Rabin-Ka…
Read article →Succinct Bitvectors, in depth: RRR classes and offsets, Elias-Fano as a sparse bitvector, measured space and choosing by density
Compressed succinct bitvectors from first principles: the log C(n, m) bound, RRR class and offset encoding with tested Python rank, Elias-Fano as a sp…
Read article →Tabu Search, in depth: short-term memory, aspiration, tenure, a hand-traced knapsack run and Python for bit-flip and 2-opt neighbourhoods
Tabu search from first principles: neighbourhoods, tabu attributes and tenure, aspiration, intensification and diversification, robust and reactive va…
Read article →t-digest architecture
Deep-dive on the t-digest quantile sketch: (mean, count) centroids, the scale function that warps cluster sizes to keep the tails sharp, the compressi…
Read article →Ternary Search, in depth: the unimodal invariant, integer and floating-point versions, golden-section search, and where it breaks
Ternary search from first principles: why two probes discard a third, a worked example, correct integer and floating-point code, the log base 1.5 step…
Read article →Theta*, in depth: any-angle paths on grids, an exact line-of-sight test, Lazy Theta* and measured distance to optimal
Theta* from first principles: the parent shortcut that turns A* into an any-angle planner, an exact corner-grid line-of-sight test with explicit rules…
Read article →Tonelli-Shanks Algorithm, in depth: the cost model in S, one shared exponentiation, the constant-time RFC 9380 loop and table-driven roots for high-2-adicity fields
Tonelli-Shanks as field libraries implement it: 2-adicity of real fields from secp256k1 to P-224, measured multiplication counts, the constant-time lo…
Read article →Top-K / heavy hitters -- finding the most frequent in a stream
Deep-dive on top-K / heavy-hitter algorithms: the most-frequent-items problem, why exact counting is memory-prohibitive, Space-Saving (bounded counter…
Read article →Top Trees, in depth: clusters, rake and compress, expose, and a static top tree for dynamic tree DP
Top trees explained from first principles: clusters with at most two boundary vertices, rake and compress merges, link, cut and expose with user summa…
Read article →Topological Sort, in depth: Kahn and DFS, cycle reporting, deterministic orders, parallel levels and build systems
Topological sort from first principles: what a dependency order is, Kahn's in-degree algorithm and the DFS postorder algorithm traced on one exam…
Read article →Transactional Memory, in depth: opacity, the TL2 algorithm with a tested STM, hardware TM with lock-elision fallback, platform status and operational rules
Transactional memory from first principles: atomicity, isolation and opacity, the versioning and conflict-detection design space, TL2 step by step wit…
Read article →Transposition Tables, in depth: the depth and bound probe contract, measured replacement policies, false matches, mate scores and sizing
How a transposition table speeds up alpha-beta search: the depth and bound-flag rules for a cutoff, choosing the stored flag, measured replacement pol…
Read article →Treap, in depth: join-based set operations, canonical shapes from keyed priorities, and augmented queries
Treaps beyond the basics: three-way split and join, union, intersection and difference (union and intersection in expected O(m log(n/m + 1))), a trace…
Read article →Tree DP, in depth: designing subtree states, iterative evaluation, O(nK) knapsack merges, rerooting and brute-force testing
Dynamic programming on trees from first principles: how to choose states, a three-state minimum dominating set, recursion-free evaluation with BFS ord…
Read article →Trie in Depth: Prefix Trees From First Principles to Radix Trees, Autocomplete and Longest-Prefix Match
How a trie works and when to use one: node representations and their memory cost, insert, search, prefix counting, deletion with pruning, cached top-k…
Read article →TSP Approximation Algorithms, in depth: the double-tree bound, insertion heuristics, the Held-Karp 1-tree bound and measured gaps
Metric TSP approximation in practice: why the triangle inequality is load-bearing, the MST lower bound and double-tree 2-approximation, the proven rat…
Read article →TSP via Dynamic Programming, in depth: implementing Held-Karp with tour recovery, memory sizing, numpy layers and constraints
An implementer's guide to the Held-Karp TSP algorithm: exact recurrence with a fixed start, a worked four-city table, Python code with parent rec…
Read article →Two's Complement, in depth: modular arithmetic, negation, carry versus overflow, sign extension and the INT_MIN traps
Two's complement from first principles: integers modulo 2^n, why negation is invert-plus-one, the asymmetric range, carry and overflow flags, sig…
Read article →UCT, in depth: Upper Confidence bounds applied to Trees, from UCB1 to a runnable Monte Carlo Tree Search, a hand-traced selection step, tuning, enhancements and PUCT
UCT from first principles: the UCB1 bandit rule, the four phases of Monte Carlo Tree Search, a complete Python implementation verified on a solved gam…
Read article →Undecidable Problems, in depth: a field guide from Post correspondence to type checking, the decidable islands, and tools that ship anyway
A practical guide to undecidable problems beyond halting: reductions, the Post correspondence problem with a working searcher, grammar ambiguity and e…
Read article →Union-Find, in depth: disjoint sets, union by size, path compression and the inverse Ackermann bound
Union-Find (disjoint set union) explained from first principles: the parent-pointer forest, why naive unions degrade to linear chains, union by size o…
Read article →Universal Hashing, in depth: Carter-Wegman, multiply-shift, tabulation, k-independence and what each application needs
Universal hashing from first principles: why fixed hash functions fail, universal, strongly universal and k-independent families, the chaining proof, …
Read article →Vertex Cover Approximation, in depth: one-pass streaming, weighted pricing, parallel rounds, dynamic updates and certificate checking
Running the 2-approximation for vertex cover at scale: a one-pass streaming matching cover, the weighted pricing pass, random-priority parallel rounds…
Read article →Visibility Graph, in depth: exact shortest paths among polygonal obstacles, construction, robust visibility tests, A* search and configuration space
A first-principles guide to visibility graphs: why shortest paths bend only at obstacle vertices, a Python O(n^3) builder with robust visibility tests…
Read article →Weighted Reservoir Sampling, in depth: A-Res and A-ExpJ in one pass, Gumbel-top-k, and priority sampling for unbiased totals
Weighted sampling from first principles: with versus without replacement, Efraimidis-Spirakis A-Res and A-ExpJ with tested code, exact inclusion proba…
Read article →Work Stealing, in depth: work and span, the work-first principle, why thieves take the oldest task, and the Chase-Lev deque
Randomised work stealing as an algorithm: the work-span model and the Blumofe-Leiserson bound, work-first versus help-first spawning, a simulator meas…
Read article →X-Fast Trie, in depth: binary search on prefix length, descendant pointers, a tested implementation and the space it really costs
The x-fast trie from first principles: one hash table per level, why prefix closure makes binary search on length valid, descendant pointers and how i…
Read article →XOR Filter, in depth: three-slot queries, hypergraph peeling, the 1.23 threshold, binary fuse successors and build-time failures
How XOR filters store a static set in 1.23 times the minimum space: the three-slot XOR query, construction by hypergraph peeling, a measured 100,000-k…
Read article →Y-Fast Trie, in depth: predecessor search in O(log log u) with linear space, built from the x-fast trie and measured
Y-fast tries from first principles: the predecessor problem, the x-fast trie with binary search on prefix length, indirection through Θ(w)-sized bucke…
Read article →Zobrist Hashing, in depth: incremental XOR keys, chess state features, collision arithmetic, lockless transposition tables and repetition detection
A first-principles guide to Zobrist hashing: random keys per feature, incremental XOR update and undo in Python, a hand trace, castling and en passant…
Read article →Zstd Compression, in depth: frames and blocks, LZ77 sequences and repeat offsets, Huffman and FSE stages, dictionaries and window limits
How Zstandard works from the bytes up: RFC 8878 frame and block layout, sequence execution with repeat offsets, Huffman literals and FSE-coded sequenc…
Read article →All-Pairs Shortest Paths, in depth: choosing between BFS, repeated Dijkstra, Johnson, Floyd-Warshall, min-plus squaring and Seidel
A selection guide to all-pairs shortest paths: what each method costs, cost arithmetic on a 10,000-vertex graph, repeated Dijkstra with path reconstru…
Read article →Signed Area of Polygon, in depth: orientation and winding, edge functions and barycentrics in rasterizers, backface culling, curved outlines and moments
The signed area of a polygon as a working primitive: what its sign means for simple and self-intersecting rings, triangle edge functions with the top-…
Read article →Art Gallery Theorem, in depth: Chvatal's floor(n/3) bound, Fisk's 3-colouring proof as code, variants and minimum guard placement
The Art Gallery Theorem explained from first principles: the comb lower bound, Fisk's triangulate-and-3-colour proof turned into tested Python, a…
Read article →Attention Mechanism, in depth: scoring functions, the exact algorithm and its cost, stable softmax, online softmax and KV-cache decoding
Attention as an algorithm: additive, multiplicative and scaled dot-product scoring, a numerically safe reference implementation with masking, the onli…
Read article →B+ Tree, in depth: copy-up versus push-up splits, the leaf chain, fanout arithmetic, bulk loading and concurrent access
How B+ trees work and why databases use them: invariants, page fanout arithmetic, search and range scans over the leaf chain, a tested Python insert w…
Read article →B-Tree, in depth: invariants, height bounds, splitting on insert, the deletion cases and a tested implementation
How B-trees stay shallow: the minimum-degree invariants and height bound, search, single-pass insertion with proactive splits, every deletion case wit…
Read article →Balanced Binary Tree Check, in depth: the definition, the O(n) post-order pass, iterative versions and the traps
How to test whether a binary tree is height-balanced: the precise definition, why the top-down approach repeats work, the single post-order pass with …
Read article →Bayesian Optimization, in depth: Gaussian process surrogates, expected improvement and UCB, a NumPy implementation, kernel fitting and failure modes
How Bayesian optimization finds the maximum of an expensive black-box function: the loop, Gaussian process posteriors via Cholesky, Matern kernels, PI…
Read article →Bellman-Ford, in depth: the relaxation invariant, early exit, hop-limited paths, distance-vector routing and difference constraints
Bellman-Ford from first principles: why n - 1 passes suffice, a traced example with two edge orders, early exit and Yen's ordering, at-most-K-edg…
Read article →BERT, in depth: WordPiece inputs, masked language modelling and the 80/10/10 rule, why NSP was dropped, the pretraining recipe and fine-tuning
BERT from first principles: the bidirectional encoder and its two sizes, token, segment and position embeddings, masked language modelling with the 80…
Read article →Betweenness Centrality, in depth: Brandes' dependency accumulation, weighted graphs, normalisation and pivot sampling
Betweenness centrality from first principles: Freeman's definition and its conventions, Brandes' O(nm) dependency recurrence with tested Pyt…
Read article →Breadth-First Search, in depth: the queue invariant, a traced example, CSR graphs and direction-optimising BFS
How breadth-first search finds shortest paths in unweighted graphs: the layer invariant and proof, a step-by-step trace, tested Python with path recon…
Read article →BFS on Grids, in depth: flat indexing, mark-on-enqueue, path reconstruction, multi-source BFS, islands, border floods, (cell, k) states and memory at scale
Grid breadth-first search from first principles: the template with direction tables and parent arrays, a traced worked example, multi-source BFS, comp…
Read article →BFS on Implicit Graphs, in depth: designing states, generating neighbours, visited-set memory, the 8-puzzle, bidirectional search and when the state space is too big
How to run breadth-first search on graphs that are never stored: what a state must contain, encoding and visited-set memory, testing goals at generati…
Read article →BFS with Augmented State, in depth: product graphs, time phases, automata, parity and dominance pruning
BFS over (position, extra state): why BFS stays optimal on the product graph, phase layers for periodic gates with a worked example, DFA-constrained p…
Read article →0-1 BFS, in depth: shortest paths with 0 and 1 weights using a deque, the invariant, stale entries and how to model problems for it
A first-principles guide to 0-1 BFS: why plain BFS fails once some edges are free, the two-value deque invariant that replaces Dijkstra's heap, a…
Read article →Binary Tree In-Order Traversal, in depth: the recursive rule, the explicit-stack loop traced step by step, lazy iterators, successors and deep-tree bugs
In-order traversal of a binary tree from first principles: why it yields sorted order on a BST, recursive and explicit-stack implementations traced by…
Read article →Binary Tree Level-Order Traversal (BFS), in depth: the size-snapshot invariant, four ways to mark levels, the variant family and the real O(W) memory cost
Level-order traversal of a binary tree from first principles: why the queue releases nodes by depth, a proof of the size-snapshot invariant, Python an…
Read article →Binary Tree Post-Order Traversal, in depth: the last-visited stack, bottom-up folds and where children-first matters
Post-order traversal of a binary tree from first principles: recursive and single-stack iterative algorithms with a full trace, computing height, diam…
Read article →Binary Tree Pre-Order Traversal, in depth: the rule, the right-then-left stack traced step by step, null-marker serialization and top-down state
A practical guide to pre-order traversal of binary trees: why visiting parents first matters, recursive and explicit-stack versions with a full stack …
Read article →Bipartite Check, in depth
Bipartite checking in depth: the odd-cycle theorem with proof, BFS two-colouring over every component in Python, recovering an odd-cycle certificate f…
Read article →Bitap Algorithm, in depth: Shift-And state words, a hand trace, k-error matching and where it breaks
Bitap (Shift-And / Shift-Or) from first principles: bit-parallel prefix state, a worked trace, the Wu-Manber k-error recurrence with tested Python and…
Read article →Blossom Algorithm, in depth: weighted matching, odd-set duals, the primal-dual loop and certificates you can check
The weighted Edmonds blossom algorithm: why odd-set constraints are needed, vertex and blossom duals, complementary slackness, the four dual adjustmen…
Read article →Bounded Knapsack, in depth
Bounded knapsack in depth: the per-count recurrence, binary splitting with a proof, the O(nW) monotone-queue method over residue classes, the used-cou…
Read article →Boyer-Moore, in depth: bad character and strong good suffix rules, building the tables, a full trace and the Galil worst-case fix
Boyer-Moore string search from first principles: right-to-left comparison, the bad character and strong good suffix shifts, border-based table constru…
Read article →Online Bridge Detection, in depth: maintaining bridges under edge insertions with a 2-edge-connected forest, two union-finds and small-to-large re-rooting
How to keep the set of bridges current as edges are inserted: the bridge forest of 2-edge-connected components, the three insertion cases, re-rooting …
Read article →Bridges and Articulation Points with Tarjan's Low-Link Algorithm: One DFS, Two Answers, and the Details That Break Real Implementations
Find every bridge and articulation point of an undirected graph in O(V + E) with one depth-first search: discovery times and low-links from first prin…
Read article →BST Insert, Search and Delete, in depth: the invariant, iterative code, all three delete cases traced by hand, height analysis and testing
A first-principles guide to binary search tree operations: the ordering invariant and why every operation costs O(height), iterative search, floor and…
Read article →BST Validation, in depth: bounds recursion, in-order checks, duplicates and validating real ordered structures
How to check that a binary tree is a valid binary search tree: the global invariant, why the local parent-child check is wrong, bounds recursion, iter…
Read article →Build a Binary Tree From Two Traversals, in depth: why preorder or postorder plus inorder is unique, O(n) recursive and stack builds, validation, and why preorder plus postorder is not enough
Reconstructing a binary tree from two traversal sequences: the uniqueness argument, a traced worked example, O(n) builders for preorder+inorder and po…
Read article →Burrows-Wheeler Transform, in depth: rotations, suffix arrays, LF-mapping inversion, bzip2 and FM-index search
The Burrows-Wheeler transform from first principles: sorted rotations, computing it from a suffix array, why LF mapping inverts it, a traced banana ex…
Read article →Cactus Graphs, in depth: edge versus vertex cacti, linear-time recognition, spanning-tree counts and independent set DP
Cactus graphs from first principles: edge and vertex cactus definitions, block structure, the 3(n-1)/2 edge bound, spanning trees as a product of cycl…
Read article →Cartesian Tree, in depth: linear-time construction, range minimum via LCA, ties, treaps and when to use one
A first-principles guide to Cartesian trees: the heap-plus-in-order definition, the O(n) stack construction traced by hand, why range minimum equals l…
Read article →Catalan Numbers, in depth: the first-return recurrence, the reflection proof, bijections, exact and modular computation, ranking and uniform random trees
Catalan numbers from first principles: the first-return recurrence, the closed form by reflection, why brackets, binary trees, triangulations and matr…
Read article →Katz Centrality, in depth: discounted walk counts, the alpha convergence bound, a worked example and scalable code
Katz centrality from first principles: counting discounted walks, the closed form and the alpha below 1/rho rule, how it relates to degree, eigenvecto…
Read article →Centroid Decomposition, in depth: finding centroids, the log-depth argument, pair counting and nearest-marked queries
Centroid decomposition from first principles: why centroids exist, an iterative builder, a hand-traced example, tested Python for counting pairs withi…
Read article →ChaCha20-Poly1305, in depth: the ARX stream cipher, the Poly1305 one-time MAC, a verified RFC 8439 implementation, nonce rules and when to choose it over AES-GCM
ChaCha20-Poly1305 from first principles: the quarter round and state layout, Poly1305 polynomial evaluation mod 2^130 - 5, the RFC 8439 AEAD construct…
Read article →Chinese Postman Problem, in depth: covering every edge with Euler circuits, odd-vertex matching, directed min-cost flow and NP-hard variants
How to solve the Chinese postman problem exactly: the Euler even-degree condition, why duplicated edges form shortest paths between odd vertices, mini…
Read article →Batched CRT, in depth: precomputed Garner for millions of values, product and remainder trees, and multi-modular algorithms
Reconstructing many values with the Chinese remainder theorem: bounds and prime counts, signed answers, a vectorised precomputed Garner with overflow …
Read article →Personalized PageRank, in depth: random walks with restart, local forward push with its error bound, Monte Carlo and bidirectional estimation, sweep cuts and PPR in ML systems
Personalized PageRank from first principles: the restart walk and its linear equation, a six-node worked example, power iteration versus forward push …
Read article →SCC Condensation, in depth: the component DAG, dynamic programming on it, bitset reachability and making a graph strongly connected
What to do with strongly connected components once you have them: build the deduplicated condensation DAG, why it is acyclic, Tarjan versus Kosaraju o…
Read article →Chordal Graphs, in depth: perfect elimination orderings, linear-time recognition, clique trees, and fill-in from sparse Cholesky to junction trees
Chordal graphs from first principles: simplicial vertices and perfect elimination orderings, maximum cardinality search with a linear-time Tarjan-Yann…
Read article →Chromatic Polynomial, in depth: why colourings are counted by a polynomial, deletion-contraction by hand, two tested exact algorithms and their limits
The chromatic polynomial P(G, k): the partition argument that makes it a polynomial, deletion-contraction worked on the diamond graph, coefficient pro…
Read article →Chu-Liu-Edmonds, in depth: decoding dependency trees from a score matrix, the single-root constraint, and testing against brute force
Chu-Liu-Edmonds as a dependency-parsing decoder: greedy heads, cycle contraction with displacement-priced arcs, a tested dense-matrix Python implement…
Read article →Circular Linked List, in depth: tail pointers, sentinel rings, the Josephus problem, round-robin and when a ring buffer is better
How circular linked lists work and where they belong: the tail-pointer representation, a tested Python implementation, the Linux-style sentinel ring, …
Read article →Circulation Problem, in depth: Hoffman's theorem, infeasibility certificates, minimum cost circulation and fleet sizing
Circulations with lower bounds beyond the basic reduction: Hoffman's theorem and certificates extracted from the residual graph, minimum cost cir…
Read article →Closest Pair of Points, in depth: the O(n log n) divide-and-conquer algorithm, why the strip check is linear, and how to implement it correctly
The closest pair of points problem from first principles: the brute-force baseline, the divide-and-conquer algorithm and the packing argument behind t…
Read article →Convolutional Neural Networks, in depth: the convolution operation, shape and compute arithmetic, receptive fields, im2col on GPUs, a PyTorch training loop and CNNs versus transformers
How convolutional neural networks work from first principles: locality and weight sharing, the output-size and parameter formulas, a worked CIFAR-10 n…
Read article →CGAL + GEOS + Boost.Geometry, in depth: numeric models, validity, overlay and choosing a production geometry library
How CGAL, GEOS and Boost.Geometry keep geometry correct under floating point: kernels and snap-rounding, the same polygon overlay in all three, a work…
Read article →Connected Components, in depth: DFS and BFS labelling, iterative traversal, union-find for streaming edges, weak components and parallel algorithms
How to find connected components in practice: iterative DFS and BFS labelling in O(V + E), a worked example, union-find for streaming edges, weak vers…
Read article →Constrained Shortest Path, in depth: why one budget makes it NP-hard, resource DP, label setting with dominance and LARAC
The resource-constrained shortest path problem from first principles: the knapsack reduction, why Dijkstra fails, a pseudo-polynomial DP, exact label …
Read article →Continued Fractions, in depth: Euclid's algorithm in disguise, convergents, best rational approximations, Pell equations and Wiener's attack
Continued fractions from first principles: the expansion as Euclid's algorithm, the convergent recurrence, why convergents and semiconvergents ar…
Read article →Contraction Hierarchies, in depth: shortcuts, witness searches, node ordering and the upward bidirectional query
Contraction Hierarchies from first principles: contraction and shortcuts, capped witness searches, edge-difference ordering with lazy updates, why the…
Read article →Andrew's Monotone Chain, in depth: two sorted chains, streaming hulls, the convex hull trick and ROC hulls
Andrew's monotone chain viewed as a data structure: the two x-monotone chains, a traced example, binary-search queries, an online hull for sorted…
Read article →Convex Hull, in depth: Graham scan, exact orientation tests and degenerate inputs
Graham scan from first principles: the cross-product orientation test and its 64-bit overflow headroom, sorting by angle without atan2, the stack inva…
Read article →QuickHull, in depth: farthest-point recursion, exact orientation, measured cost from linear to quadratic and the path to Qhull
A correct 2D QuickHull with exact integer orientation tests, why the farthest point is a hull vertex, an eleven-point worked example, measured candida…
Read article →Convex Layers, in depth: onion peeling, the collinear rule, layer counts, halfplane queries and robust centres
Convex layers from first principles: tested peeling code on Andrew's monotone chain, why the collinear-point rule changes the layer count fourfol…
Read article →Convex Polygon Intersection, in depth: the half-plane view, a linear-time exact algorithm and the degenerate cases
Intersecting two convex polygons in O(n + m): the output contract, the half-plane view with a merge and deque sweep in exact arithmetic, tested Python…
Read article →Deep Copy List with Random Pointer, in depth: the identity map, the O(1)-space interleaving trick, a copy verifier and graph cloning
How to deep-copy a linked list whose nodes also carry a random pointer: why a naive copy fails, the two-pass hash map, a one-pass memoised version, th…
Read article →Cycle Detection in Directed Graph, in depth: three-colour DFS that returns the cycle, an explicit-stack version for deep graphs, Kahn leftovers, all cycles via SCCs and where it runs in production
How to detect and report cycles in directed graphs: why undirected tricks fail, three-colour DFS with a cycle witness, a worked example, an iterative …
Read article →Cycle Detection, in depth: Floyd's tortoise and hare, Brent's algorithm, the rho shape, proofs, linked lists, Pollard's rho and production pitfalls
A first-principles guide to cycle detection on iterated functions: the rho shape and its tail length mu and cycle length lambda, Floyd's tortoise…
Read article →Cycle Detection in Undirected Graph, in depth: the E = V - C test, parent-edge DFS that returns the cycle, union-find for edge streams and the multigraph traps
How to detect cycles in undirected graphs correctly: simple graphs versus multigraphs, the forest identity E = V - C and the cyclomatic number, an ite…
Read article →DBSCAN, in depth: core, border and noise points, a verified worked example, choosing eps and minPts, and the real complexity
DBSCAN density clustering from first principles: core, border and noise points, density-reachability, a Python implementation, an eleven-point worked …
Read article →Decision Trees, in depth: CART impurity, split search, cost-complexity pruning and a worked example
Decision trees from first principles: Gini, entropy and squared error, the sorted sweep split search and its cost, a worked 12-row example checked aga…
Read article →DeepWalk, in depth: truncated random walks, skip-gram with hierarchical softmax, the matrix it implicitly factorises, and evaluation that does not leak
DeepWalk node embeddings from first principles: why random-walk corpora look like text, walk generation and skip-gram with hierarchical softmax in cod…
Read article →Delaunay Triangulation, in depth: the empty-circle rule, robust predicates, Bowyer-Watson and edge flips, SciPy in practice and the super-triangle trap
Delaunay triangulation from first principles: the empty circumcircle rule and max-min angle property, the Voronoi dual and paraboloid lifting, orienta…
Read article →Depth-First Search, in depth: a frame-by-frame trace, the parenthesis and white-path theorems, and DFS as a hook framework
Depth-first search traced step by step with discovery and finish times, edge classification, proofs of the parenthesis and white-path theorems, topolo…
Read article →DFS Tree, in depth: edge classification by colour and timestamps, the proofs behind it, and the low-links it powers
The DFS forest as a data structure: discovery and finish times, the parenthesis and white-path theorems, tree, back, forward and cross edges in direct…
Read article →Dial's Algorithm, in depth: bucket queues for small integer weights, the circular array, lazy deletion and when it beats a heap
Dial's algorithm explained from first principles: a monotone bucket queue for integer edge weights in [0, C], why C + 1 circular buckets suffice,…
Read article →Diffie-Hellman, in depth: key exchange from modular arithmetic to X25519, authentication and real attacks
Diffie-Hellman key exchange from first principles: the math, a hand-worked p = 23 example, X25519 with HKDF in Python, man-in-the-middle and authentic…
Read article →Digital Signatures, in depth: what a signature proves, EUF-CMA, hash-then-sign, choosing a scheme and the protocol mistakes that break them
Digital signatures from first principles: integrity, authenticity and public verifiability, the EUF-CMA and SUF-CMA games, hash-then-sign, a toy Schno…
Read article →Bidirectional Dijkstra, in depth: the mu stop rule, a counterexample to the first-meeting rule, tested Python and path recovery
Bidirectional Dijkstra explained correctly: forward and reverse searches, updating mu on every relaxation, the top_f + top_b stop rule, a five-node tr…
Read article →Dijkstra's Algorithm, in depth: a reusable engine for state graphs, custom path costs, time-dependent edges and certified answers
Dijkstra's algorithm as a reusable engine: one loop with a pluggable expansion function, the monotone and isotone conditions any path cost must m…
Read article →Dijkstra with Fibonacci Heap, in depth: decrease-key in O(1), the potential-function proof, and when it actually wins
How a Fibonacci heap gives Dijkstra O(E + V log V): what Dijkstra needs from a priority queue, root lists, consolidation, cuts and marks, a tested Pyt…
Read article →Dijkstra's Shortest Path, in depth: the algorithm as an event stream, a frame-by-frame trace, and rendering the wavefront
Dijkstra's algorithm rebuilt as a stream of observable events so you can animate it: an instrumented generator that yields every push, settle, st…
Read article →Dijkstra with Potentials, in depth: feasible potentials, measured landmark choice, averaged bidirectional search and reuse after weight changes
Dijkstra with potentials as an engineering tool: the reduced-weight identity and sign conventions, ALT landmark potentials measured on a 22,500-node g…
Read article →Dominator Tree, in depth: semidominators, Lengauer-Tarjan with path compression, dominance frontiers and SSA
How the Lengauer-Tarjan dominator algorithm works: dominance and immediate dominators, semidominators from a DFS, the eval/link forest with path compr…
Read article →Doubly Linked List, in depth: the sentinel ring, constant-time unlink by handle, invariant tests and the real hardware cost
Doubly linked lists from first principles: the back-link invariant, sentinel versus null-ended designs, a tested Java implementation with node handles…
Read article →0/1 Knapsack Problem, in depth: the table as a picture, rows as staircases, Pareto lists, choosing between tied optima and an event trace for animation and debugging
The 0/1 knapsack DP seen as a picture: a computed worked table with its backtrack path, why every row is a non-decreasing staircase, the Pareto list t…
Read article →Burst Balloons, in depth: the last-burst reframe, interval DP with reconstruction, and why greedy and Knuth fail
Burst Balloons solved from first principles: why choosing the first balloon breaks independence, the last-burst open-interval recurrence, bottom-up Py…
Read article →Coin Change, in depth: minimum coins and counting ways, loop order, reconstruction, greedy checks and the bugs that break each variant
Coin change from first principles: the minimum-coins and number-of-ways variants worked by hand, why loop order counts combinations or ordered sequenc…
Read article →Egg Drop Problem, in depth: the min-max recurrence, binary-search speed-up, the moves reformulation, strategy reconstruction and failure-budget probing
The egg drop problem from first principles: the O(kn²) recurrence, a binary-search speed-up, the moves DP and its binomial closed form, the 2-egg 100-…
Read article →Fibonacci, in depth: from exponential recursion to memoization, tabulation and constant-space DP
Fibonacci as the smallest complete dynamic programming example: the exact call count of naive recursion, overlapping subproblems, memoization and recu…
Read article →House Robber Problem, in depth: the two-state machine, reconstruction, circular, gap, tree and max-plus segment tree variants
House Robber explained as a two-state DP machine: the O(1)-space loop, reconstructing the chosen houses, a worked trace, circular rows, minimum gaps, …
Read article →Dynamic Programming, in depth: filling the table cell by cell, legal fill orders and reconstructing the answer
Dynamic programming from the table outward: state space, dependency stencil, boundary and fill order, a minimum-cost grid path filled frame by frame, …
Read article →Matrix Chain Multiplication, in depth: the interval DP, reconstructing the order, and where ML code depends on it
Matrix chain multiplication from first principles: the p*q*r cost model, Catalan blow-up, the interval DP recurrence, Python code with reconstruction,…
Read article →Maximum Subarray Sum, in depth: Kadane's algorithm, prefix sums, a correctness proof, divide and conquer, and circular, product and 2D variants
The maximum subarray problem from brute force to O(n): prefix sums, Kadane's recurrence with index tracking and the all-negative case, a proof, a…
Read article →Optimal Binary Search Tree, in depth: the interval DP, Knuth's root window and a fully worked example
Optimal binary search trees from first principles: hit and miss weights, why greedy and balanced trees lose, the O(n^3) interval DP, Knuth's O(n^…
Read article →Paint House Problem, in depth: choosing the state, the three-color DP, k colors in O(nk), reconstruction and variants
The paint house problem as a lesson in state design: why greedy fails, dp over house and last color, a traced worked example, reconstruction of the co…
Read article →Palindrome Partitioning, in depth: minimum cuts from the recurrence to O(n) memory, reconstruction, enumeration and testing
Palindrome partitioning explained from first principles: why greedy fails, the cut and palindrome-table recurrences, an O(n²) solution, an O(n)-memory…
Read article →Partition Equal Subset Sum, in depth: the S/2 reduction, the one-row DP, recovering the split, minimum difference and k-way partition
Partition Equal Subset Sum from first principles: reducing to a subset sum of S/2, parity and max-element exits, the one-row table and why it loops do…
Read article →Regular Expression Matching, in depth: the dot-star recurrence, a worked table, three verified implementations and the link to automata
Regular expression matching with dot and star by dynamic programming: exact semantics, why naive recursion explodes, the dp[i][j] recurrence, a worked…
Read article →Best Time to Buy and Sell Stock, in depth: one state machine for all six variants, a correctness argument, trade reconstruction and the k-transaction shortcut
The stock buy-and-sell problems as one hold/free state machine: the general k-transaction recurrence and its loop order, a worked trace, cooldown and …
Read article →Unique Paths in Grid, in depth: the recurrence, one-row DP, the binomial closed form and its overflow trap, obstacles and huge grids
Counting right-and-down grid paths from first principles: the addition-rule recurrence, a rolling-array DP, C(m+n-2, m-1) and where fixed-width intege…
Read article →Word Break Problem, in depth: reachability DP, measured recursion blow-up, trie matching, counting, listing and Viterbi segmentation
The word break problem from first principles: positions as a reachability graph, why naive recursion explodes (measured), the length-bounded DP, trie …
Read article →ECDSA, in depth: the signing equations, a worked toy-curve example, nonce-reuse key recovery and safe verification
ECDSA from the group up: scalar multiplication, signing and verification with proof, a fully worked example on a 19-point curve, nonce reuse and bias …
Read article →Ed25519, in depth: the curve, clamping, deterministic Schnorr signing, verification edge cases and the mistakes that leak keys
Ed25519 from RFC 8032: twisted Edwards arithmetic, key expansion and clamping, signing and verification equations, a reference implementation that rep…
Read article →Edmonds-Karp in Depth: Why Shortest Augmenting Paths Bound Max Flow at O(VE²), With a Traced Proof and an Implementation You Can Trust
Edmonds-Karp from first principles: why augmenting along BFS shortest paths guarantees polynomial time, the monotone-distance and critical-edge proof …
Read article →Eigenvector Centrality, in depth: the Perron-Frobenius conditions, shifted power iteration, a worked six-node example and where the measure breaks
Eigenvector centrality from first principles: the eigenvector equation and Perron-Frobenius, a hand-worked six-node example, power iteration with the …
Read article →Elliptic Curve Cryptography (ECC), in depth: the group law on a toy curve, constant-time scalar multiplication, ECDH, curve choice and the attacks that skip validation
Elliptic curve cryptography from first principles: the chord-and-tangent group law worked by hand on a 101-point curve, the Montgomery ladder and cons…
Read article →Epidemic Models on Networks, in depth: SIR and SIS on graphs, the excess-degree threshold, percolation and event-driven simulation
How epidemics spread on contact networks: SIR and SIS with per-edge rates, transmissibility, why R0 depends on the second degree moment, the percolati…
Read article →Euclidean Algorithm, in depth: why gcd(a, b) = gcd(b, a mod b), a traced example, safe code for negatives, binary GCD and real uses
The Euclidean algorithm from first principles: the invariant and its proof, a traced and drawn example, Python and C code that handles zero, negatives…
Read article →Euclidean MST, in depth: why the tree hides inside the Delaunay triangulation, dense Prim and dual-tree Borůvka in higher dimensions, single-linkage clustering and real-data failure modes
How to compute the Euclidean minimum spanning tree: the Gabriel and Delaunay containment proof, choosing an algorithm by size and dimension, tested Nu…
Read article →Euler's Totient Function, in depth: the product formula, single-value and sieve computation, exponent reduction and why RSA uses λ(n)
Euler's totient φ(n) from first principles: multiplicativity via the Chinese remainder theorem, the product formula, O(sqrt n) and sieve implemen…
Read article →Euler Tour Technique, in depth
The Euler tour technique in depth: the three tour shapes, entry and exit times that turn subtrees into array slices, an O(1) ancestor test, an iterati…
Read article →Eulerian Path, in depth: the degree conditions, the Hierholzer algorithm with an explicit stack, multigraphs, itineraries and de Bruijn sequences
How to find a path or circuit that uses every edge exactly once: the degree and connectivity conditions for undirected and directed graphs, why Hierho…
Read article →Expander Graphs, in depth: edge and spectral expansion, Cheeger and the mixing lemma checked in code, Ramanujan bounds, constructions and where expanders run
Expander graphs from first principles: edge, vertex and spectral expansion, the Cheeger inequality and expander mixing lemma verified by brute force, …
Read article →Extended Euclidean Algorithm, in depth: the invariant behind Bezout coefficients, a full trace, sign handling, overflow bounds, modular and batch inverses, and CRT
How the extended Euclidean algorithm finds gcd(a, b) and integers x, y with a*x + b*y = gcd: the row invariant and proof, a full hand trace, iterative…
Read article →Fast Polynomial Multiplication, in depth: choosing between schoolbook, Karatsuba, FFT and NTT, measured float precision, and Newton inversion and division
A practical guide to fast polynomial multiplication: the cost and exactness of each method, tested Karatsuba, FFT and NTT code, a worked evaluation-in…
Read article →Fenwick Tree (BIT), in depth: deriving lowbit, linear-time build, binary-lifting search, inversion counting and the bugs that bite
A guide for implementers of the Fenwick tree: why i and -i isolates the lowest set bit, responsibility ranges and the log bounds, tested Python code, …
Read article →2D Fenwick Tree, in depth: rectangle sums with point and range updates in O(log n · log m)
How a 2D Fenwick (binary indexed) tree answers rectangle sums with point updates in O(log n log m): the rectangle each cell covers, nested loops in Py…
Read article →Fibonacci Computation, in depth: fast doubling, big-integer cost and modular answers
Computing Fibonacci numbers properly: why naive recursion makes 2F(n+1)-1 calls, the true big-integer cost of the loop, fast doubling derived from the…
Read article →Find Middle of Linked List, in depth: slow and fast pointers, the two even-length middles and safe splits
How to find the middle of a singly linked list: the first and second middle on even lengths, the slow and fast pointer invariant and which loop return…
Read article →Finger Tree, in depth: 2-3 finger trees, monoid measures, split and concatenation, a tested Python implementation and measured costs
The Hinze-Paterson 2-3 finger tree from first principles: nested digits and nodes, amortised O(1) ends and the strict-persistence trap, monoid measure…
Read article →Flood Fill, in depth: connectivity, stack-safe fills, scanline spans, tolerance and region labeling
Flood fill as an image and region operation: 4- versus 8-connectivity and diagonal leaks, why recursive fills crash, explicit-stack and scanline (span…
Read article →Fractional Cascading, in depth: searching k sorted lists in O(log n + k), the one-step proof, a tested implementation and layered range trees
How fractional cascading answers the same search in many sorted lists with one binary search and constant work per list: augmented catalogs, bridges, …
Read article →Fractional Knapsack, in depth: the greedy proof, a linear-time algorithm and the LP bound
Fractional knapsack from first principles: greedy by value density, a worked five-item example, the exchange-argument proof, the LP and critical-ratio…
Read article →Gabow's SCC Algorithm, in depth: path-based DFS with two stacks, a correctness argument and an iterative implementation
How Gabow's path-based strongly connected components algorithm works: the S and P stacks, why contracting cycles by popping boundaries is correct…
Read article →Game Tree Search, in depth: minimax, negamax and alpha-beta traced by hand, with move ordering, transposition tables and iterative deepening measured
Game tree search from first principles: minimax and negamax, alpha-beta pruning traced on a drawn tree, a complete Python tic-tac-toe engine with a tr…
Read article →Gas Station Circular Route, in depth: the skip lemma, the minimum-prefix-sum proof and when the greedy breaks
Solving the circular gas station problem in one pass: the feasibility and skip lemmas, the prefix-sum proof, a traced example, a validity-based random…
Read article →Girvan-Newman, in depth: edge betweenness by Brandes accumulation, the divisive loop, the dendrogram and choosing the cut by modularity
Girvan-Newman community detection from first principles: edge betweenness via Brandes' backward accumulation, recomputing after every removal, a …
Read article →Gomory-Hu Tree, in depth: all-pairs minimum cuts from n-1 max-flows with Gusfield's algorithm
Gomory-Hu trees from first principles: why all-pairs min cuts fit in a tree, Gusfield's algorithm in Python, a fully traced six-vertex example, q…
Read article →GPT, in depth: the decoder-only transformer from forward pass and training loop to KV cache, sampling and hardware limits
GPT explained as an algorithm: token and position embeddings, pre-norm causal transformer blocks, tied unembedding, next-token training with a one-pos…
Read article →Gradient Boosting, in depth: functional gradient descent, the second-order split gain, histograms, and XGBoost vs LightGBM vs CatBoost
Gradient-boosted trees from first principles: boosting as gradient descent in function space, the XGBoost second-order leaf weight and gain formula, a…
Read article →Graph Attention Networks (GAT), in depth: edge scores, segment softmax, multi-head layers and GATv2
Graph attention networks from first principles: the edge score and its per-node decomposition, segment softmax on an edge list in NumPy, a hand-checke…
Read article →Graph Diameter, in depth: eccentricity bounds, the double sweep, iFUB and BoundingDiameters measured, the SETH barrier and the traps on real graphs
Computing the diameter of a general graph: eccentricity bounds, why the double sweep is only a lower bound, the iFUB and BoundingDiameters exact algor…
Read article →Graph Isomorphism, in depth: colour refinement, individualisation and backtracking, canonical forms, and the WL limit of GNNs
Graph isomorphism from first principles: complexity status and Babai's quasi-polynomial result, invariants as filters, colour refinement (1-WL) a…
Read article →Graph Kernels, in depth: Weisfeiler-Lehman subtree features in code, the 1-WL ceiling shared with GNNs, shortest-path, random-walk and graphlet kernels, and kernel SVMs on graph data
Graph kernels from first principles: why complete kernels are intractable, the Weisfeiler-Lehman subtree kernel in Python, a worked C6 versus two-tria…
Read article →Graph Neural Networks, in depth: message passing from first principles, GCN and GraphSAGE in plain PyTorch, neighbour sampling, expressivity limits and the failures that bite in practice
A practical introduction to graph neural networks: why permutation equivariance leads to message passing, GCN normalisation worked by hand, GCN and Gr…
Read article →Group Knapsack, in Depth
Group (multiple-choice) knapsack from first principles: the recurrence, 2-D DP with reconstruction, the 1-D loop-order trap, at-most-one versus exactl…
Read article →Half-Plane Intersection, in depth: sort by angle and sweep a deque in O(n log n), bounding boxes, parallel and empty cases, tested code and kernels
Half-plane intersection from first principles: the sort-by-angle deque algorithm, a hand trace, Python code tested against a brute-force oracle, kerne…
Read article →Hamiltonian Path, in depth
Finding a path that visits every vertex once: why it is NP-complete, backtracking with reachability and dead-end pruning, a measured worked example, t…
Read article →HITS Algorithm, in depth: hubs and authorities, the singular vector view, a sparse implementation and why ties break it
The HITS algorithm of Kleinberg from first principles: mutual reinforcement of hub and authority scores, the root and base set, the link to the SVD, a…
Read article →HMAC, in depth: the ipad and opad construction from scratch, RFC 4231 test vectors, key rules, constant-time verification, webhook signing and key rotation
How HMAC authenticates messages: why H(key || message) fails, the two-pass construction implemented and checked against RFC 4231, key length and equiv…
Read article →HNSW, in depth: a from-scratch implementation, the neighbour heuristic, recall tuning, memory math, deletes and filtered search
A practitioner's guide to HNSW: a compact Python implementation of layer search and insertion, why the neighbour-selection heuristic matters, a r…
Read article →Homomorphic Encryption, in depth: Paillier, LWE noise budgets, BFV, BGV, CKKS, TFHE and bootstrapping
How homomorphic encryption works: a hand-checked Paillier example, a runnable toy LWE scheme showing silent noise overflow, the BFV, BGV, CKKS and TFH…
Read article →Hopcroft-Karp, in depth: layered BFS, disjoint shortest augmenting paths, the square-root phase bound, and an iterative implementation
Hopcroft-Karp maximum bipartite matching from first principles: BFS layering with a shortest-length cutoff, DFS with dead-end pruning, iterative Pytho…
Read article →Huffman Coding, in depth: optimal prefix codes, canonical codes, length limits and table-driven decoding
Huffman coding from first principles to a working codec: prefix codes, the Kraft inequality and the entropy bound, a worked six-symbol example, canoni…
Read article →Influence Maximization, in depth: IC and LT diffusion, submodularity, greedy with CELF, reverse influence sampling and IMM
Influence maximization from first principles: Independent Cascade and Linear Threshold models, live-edge graphs, NP-hardness and #P-hard spread, why s…
Read article →Integer Partitions, in depth: Ferrers diagrams, the O(n^2) DP, Euler's pentagonal recurrence and generating partitions
Counting and generating integer partitions: Ferrers diagrams and conjugation, the part-size DP, P(n, k), Euler's pentagonal recurrence in O(n^1.5…
Read article →Interval Graphs, in depth: three characterisations, certifying recognition, linear sweeps and the endpoint convention trap
Interval graphs from first principles: models, closed versus half-open endpoints, the Lekkerkerker-Boland, Gilmore-Hoffman and Fulkerson-Gross theorem…
Read article →Interval Merging + Meeting Rooms, in depth: half-open intervals, merge, the room count three ways, room assignment and production traps
Interval merging and the meeting rooms problem from first principles: half-open conventions, why sort-by-start merging is correct, minimum rooms by mi…
Read article →Interval Tree, in depth: the max-end augmented BST, tested code, query pruning and when to use something else
How interval trees answer overlap and stabbing queries: half-open intervals, the max-end augmentation on a balanced BST, tested treap code for insert,…
Read article →ISAP, in depth: distance labels, advance and retreat, the gap heuristic and a tested max-flow implementation
Learn ISAP (Improved Shortest Augmenting Path) max flow from first principles: residual graphs, distance labels, admissible arcs, current-arc and gap …
Read article →Iterative Deepening DFS, in depth: depth-limited search with a cutoff signal, the b/(b-1) overhead measured, an 8-puzzle, and the transposition blow-up on graphs
Iterative deepening DFS from first principles: why repeated depth-limited search costs only b/(b-1) times BFS, a tested Python implementation that sep…
Read article →Iterative DFS, in depth: explicit stack frames, finish times, the two shortcuts that break, and an iterative Tarjan SCC
How to write depth-first search without recursion and keep it correct: stack frames with cursors, Python and Java code, a step-by-step trace, why mark…
Read article →Job Scheduling with Deadlines, in depth: the profit-maximising greedy, union-find slots, Moore-Hodgson, EDF and where greedy stops working
Job sequencing with deadlines from first principles: the unit-time profit problem, the latest-free-slot greedy with a worked example and proof sketch,…
Read article →Karger Min Cut, in depth: random edge contraction, the 1/C(n,2) bound, a union-find implementation, Karger-Stein and cut counting
The Karger contraction algorithm for global minimum cut: multigraph contraction rules, the telescoping success proof, how many runs you need, a tested…
Read article →Karp's Minimum Mean Cycle Algorithm, in depth: the formula, why it works, cycle extraction and faster alternatives
Karp's minimum mean cycle algorithm from first principles: the walk-length dynamic programming table, the min-max formula and its proof idea, an …
Read article →K-d Tree, in depth: median construction, nearest-neighbour pruning, range search, the curse of dimensionality and production layouts
How a k-d tree partitions k-dimensional space and answers nearest-neighbour, k-NN and range queries: median construction, the plane-pruning rule trace…
Read article →Electrical Networks and Graph Theory, in depth: Kirchhoff's laws as a Laplacian system, effective resistance, Thomson, Rayleigh and Foster, harmonic functions and solving at scale
Resistor networks as graph algorithms: Kirchhoff's laws become L phi = b, a worked five-resistor example solved by hand and in Python, effective …
Read article →k-means Clustering, in depth: the Lloyd algorithm, a hand trace, k-means++ seeding, choosing k and scaling up
k-means clustering from first principles: the SSE objective, why Lloyd iterations converge, a seven-point hand trace, k-means++ seeding, a NumPy imple…
Read article →k-Nearest Neighbors (kNN), in depth: the voting rule, scaling, choosing k, ties, theory and the curse of dimensionality
k-nearest neighbours as a learner, from first principles: a NumPy implementation, a worked example where tie-breaking flips the answer, feature scalin…
Read article →Kosaraju's Algorithm, in depth: the finish-time lemma, iterative two-pass SCC, output order and real uses
Kosaraju's algorithm for strongly connected components explained from first principles: why two depth-first passes, one on the reversed graph, fi…
Read article →Kruskal's Minimum Spanning Tree, in depth: sort-and-filter greedy, the cycle property, union-find, clustering and the reconstruction tree
Why sorting edges and skipping cycles yields a minimum spanning tree, a hand-traced example, a complete union-find implementation, forests, ties and u…
Read article →Kth Smallest in a BST, in depth: early-exit inorder, Morris traversal without leaving threads behind, and size-augmented order-statistic trees for repeated queries
A complete guide to finding the kth smallest key in a binary search tree: why inorder order is sorted order, recursive and iterative early-exit traver…
Read article →Kuhn's Algorithm, in depth: maximum bipartite matching with augmenting paths, a traced example, recursive and iterative Python, correctness, complexity and when to switch
Kuhn's algorithm for maximum bipartite matching from first principles: matchings, alternating and augmenting paths, Berge's theorem, a trace…
Read article →Label Propagation, in depth: community detection in near-linear time, a hand trace, an implementation, oscillation and flooding, variants and evaluation
How label propagation finds communities: the Raghavan, Albert and Kumara algorithm with asynchronous random-order updates and its stopping rule, a ste…
Read article →Fast Laplacian Solvers, in depth: condition numbers, preconditioned CG, spanning-tree preconditioners measured, the near-linear-time lineage and what to run in practice
Solving graph Laplacian systems quickly: the null space and grounding, why condition numbers make plain CG slow, preconditioned CG with Jacobi and spa…
Read article →LCP Array, in depth: Kasai linear-time construction, the proof, a full banana trace, the PLCP variant and the string problems it solves
What the longest-common-prefix array is and how Kasai's algorithm builds it from a suffix array in O(n): the key lemma and the amortised argument…
Read article →Legendre and Jacobi Symbols, in depth: quadratic residues, reciprocity, a gcd-speed algorithm and where primality tests use them
A first-principles guide to the Legendre and Jacobi symbols: what quadratic residues are, Euler's criterion, quadratic reciprocity and its supple…
Read article →LFU Cache, in depth: the O(1) frequency-bucket design, tie-breaking, aging, Redis's approximated LFU and when frequency beats recency
Build a Least Frequently Used cache from first principles: why frequency, the naive scan and heap designs, the O(1) structure of a key map plus per-co…
Read article →Line Segment Intersection, in depth: classifying every outcome, exact intersection points, polygon validation and a measured grid broad phase
Line segment intersection beyond yes or no: the five outcomes, solving for the parameters with cross products, a tested exact classifier, float failur…
Read article →Linear Diophantine Equations, in depth: existence, every solution from one, counting in a range, non-negative solutions and overflow
How to solve ax + by = c over the integers: the gcd existence test, extended Euclid, the general solution, a worked crate-packing example, counting so…
Read article →Linear Regression, in depth: least squares from first principles, a worked example, QR versus normal equations, ridge, lasso and diagnostics
Ordinary least squares derived and worked by hand on five points, why QR and SVD beat the normal equations numerically, gradient descent, ridge and la…
Read article →Link-Cut Tree, in depth: preferred paths, access, make_root and a tested implementation
Link-cut trees from first principles: preferred paths stored as depth-keyed splay trees, path-parent pointers, the access operation, make_root by lazy…
Read article →Singly Linked List, in depth
Singly linked lists in depth: node layout and the head/tail/size invariants, push and pop at both ends with complexity, sentinel and pointer-to-pointe…
Read article →Locality-Sensitive Hashing (LSH), in depth: MinHash banding, random hyperplanes, p-stable projections and when to choose it over HNSW
A first-principles guide to locality-sensitive hashing: sensitive families and rho, AND/OR amplification and the banding S-curve, MinHash for Jaccard …
Read article →Logistic Regression, in depth: log-odds, log loss, Newton and gradient solvers, separation, regularisation and calibration
Logistic regression from first principles: why the sigmoid follows from linear log-odds, the log loss and its gradient, NumPy gradient-descent and New…
Read article →Longest Common Substring, in depth: the DP recurrence, suffix automaton, suffix array with LCP and binary search with rolling hashes
Four tested ways to find the longest common substring: the O(nm) rolling-row DP, a linear suffix automaton walk, a suffix array with LCP over a separa…
Read article →Longest Palindromic Subsequence
Find the longest subsequence (not contiguous) that reads the same forwards and backwards. O(N²) DP via LCS reduction or direct recurrence; examples, c…
Read article →Longest Path in DAG, in depth
Longest path in a directed acyclic graph in depth: why it is NP-hard in general and linear on DAGs, the topological DP with reconstruction and cycle d…
Read article →Longest Repeated Substring, in depth: suffix arrays and LCP, rolling-hash binary search, non-overlapping and k-times variants, and corpus-scale dedup
Solve the longest repeated substring problem properly: why the answer is the maximum adjacent LCP, tested suffix array and Kasai code, a rolling-hash …
Read article →Louvain Algorithm, in depth: modularity from first principles, the move gain, a hand trace, an implementation, the resolution limit and the Leiden fix
The Louvain community detection algorithm from first principles: modularity and its bounds, deriving the gain of a node move, local moves and aggregat…
Read article →Lowest Common Ancestor (LCA), in depth: naive climbing, binary lifting, Euler tour with sparse tables, Tarjan's offline algorithm, and how to choose
A practical guide to lowest common ancestor queries on trees: the definition, the naive climb, binary lifting, Euler tour plus sparse-table RMQ, Tarja…
Read article →Lucas' Theorem, in depth: binomial coefficients modulo a prime when n is larger than p, with proof, worked examples, code and the CRT extension
Lucas' theorem from first principles: why the factorial-inverse method for C(n, k) mod p breaks once n reaches p, the base-p digit statement and …
Read article →Manacher's Algorithm, in depth: all longest palindromes by centre in linear time, the mirror argument, a full trace, and O(1) palindrome queries
Manacher's algorithm from first principles: why expand-around-centre is quadratic, the separator transform and why separators never meet real cha…
Read article →Matrix Exponentiation, in depth: building transition matrices, a worked example by hand, overflow-safe code, walks, min-plus shortest paths and automata
Matrix exponentiation from first principles: writing a step as a matrix, constructing transition matrices for recurrences, constants, polynomial terms…
Read article →Matrix-Tree Theorem, in depth: counting spanning trees with an exact determinant, weighted and directed forms, edge marginals and dependency parsing
Kirchhoff's matrix-tree theorem as a working tool: the Laplacian, a Cauchy-Binet proof sketch, exact Bareiss and mod-p determinants in Python, a …
Read article →Max Flow in Depth: Ford-Fulkerson, Residual Graphs, Edmonds-Karp and the Minimum Cut, with Working Code
A from-first-principles guide to maximum flow: flow networks, residual graphs and reverse edges, the Ford-Fulkerson method, Edmonds-Karp's O(VE^2…
Read article →Maximum Flow, in depth: modelling, solver libraries, reading the minimum cut and re-solving when capacity changes
A practical overview of maximum flow: residual graphs and cuts from first principles, an algorithm landscape, a GPU-job placement worked example solve…
Read article →Max-Flow Min-Cut Theorem, in depth: weak and strong duality, the LP view, minimum cut structure, certificates and modelling with cuts
The max-flow min-cut theorem from first principles: proofs of weak and strong duality, LP duality and integrality, Menger, the lattice of minimum cuts…
Read article →Max Flow via Electrical Flows, in depth: multiplicative weights over Laplacian solves, the energy certificate and a numpy implementation
Approximate undirected maximum flow with electrical flows: why one electrical flow is not enough, the multiplicative-weights loop of Christiano, Kelne…
Read article →Min-Cost Flow via Cost Scaling, in depth: epsilon-optimality, the refine phase, a tested implementation and the heuristics that make it fast
Goldberg-Tarjan cost scaling for min-cost flow: prices and reduced costs, epsilon-optimality and the n + 1 multiplier, refine as push-relabel, a teste…
Read article →Merge K Sorted Lists, in depth: the min-heap merge, divide and conquer, and k-way merging in real systems
How to merge k sorted lists into one sorted output: why naive approaches cost O(N log N) or O(kN), the min-heap algorithm with its O(N log k) proof, c…
Read article →Merge Sort Tree, in depth: range counting, k-th smallest by value search, fractional cascading and the index-sorted variant
Build a merge sort tree from first principles: sorted lists per segment tree node, counting values at most x in O(log² n), k-th smallest in O(log³ n) …
Read article →Merge Two Sorted Lists, in Depth
Merging two sorted linked lists properly: the loop invariant, dummy head and pointer-to-pointer splicing, stability and the tie-break, recursion depth…
Read article →Miller-Rabin, in depth: strong probable primes, witnesses, deterministic base sets and the bugs that break primality tests
How the Miller-Rabin primality test works from first principles: the n-1 = 2^s d decomposition, square roots of one, worked traces, error bounds, dete…
Read article →Min-Cost Bipartite Matching, in depth: epsilon-complementary slackness, the auction algorithm, cost scaling and price wars
Cost-scaling algorithms for the assignment problem: epsilon-complementary slackness and why scaling costs by n+1 makes it exact, a tested auction with…
Read article →Layered Graph Techniques, in depth: counter layers, hop-limited sweeps, min-plus powers, time-expanded flows and level graphs
Layered graphs explained from first principles: copying a graph per counter value, Dijkstra with free edges, K-round hop-limited sweeps, min-plus matr…
Read article →Minimum Bottleneck Paths: Why the MST Path Minimises the Maximum Edge
Why every path in a minimum spanning tree is a minimum bottleneck path: the cut proof, the threshold and ultrametric view, why an MBST is not enough, …
Read article →Mo's Algorithm, in depth: answering offline range queries in O((n + q) sqrt n) by reordering them
A first-principles guide to Mo's algorithm: the cost model behind sqrt decomposition of queries, choosing the block size, the sort order and its …
Read article →Dirichlet Convolution + Multiplicative Functions, in depth: the convolution ring, inverses, prime-by-prime transforms and the hyperbola method
Dirichlet convolution as an algebra: identity, inverses and when they exist, closure of multiplicative functions, Dirichlet series, O(N log N) and O(N…
Read article →Modular Exponentiation, in depth: square-and-multiply traced by hand, overflow, exponent reduction, windows, Montgomery multiplication, constant time and RSA-CRT
Modular exponentiation from first principles: why reducing after each step works, left-to-right and right-to-left square-and-multiply with a hand trac…
Read article →Modularity, in depth: the configuration null model, a worked score, the modularity matrix, tested code, resolution limits and how to use Q honestly
What graph modularity measures and how to use it: derivation from the configuration model, per-community form and range, a hand-worked example, the mo…
Read article →Monte Carlo Tree Search (MCTS), in depth: one generic loop, chance nodes, open-loop search, parallel search, learned models and search over LLM reasoning
Monte Carlo Tree Search as a framework: a generic implementation with correct multi-player backup, a hand-worked UCT step, chance nodes and open-loop …
Read article →Morris Traversal, in depth: threading a binary tree for O(1)-space inorder, preorder and postorder walks
How Morris traversal walks a binary tree with no stack and no recursion by temporarily threading null right pointers: the invariant, a full worked tra…
Read article →Motion Planning, in depth: configuration space, probabilistic roadmaps, narrow passages, PRM* and lazy PRM, with tested code and measured success rates
Probabilistic roadmaps from first principles: C-space and collision oracles, learn and query phases, a tested Python PRM, success rates on a narrow-pa…
Read article →Multi-Party Computation (MPC), in depth: secret-shared arithmetic, Beaver triples, garbled circuits and security models
Secure multi-party computation from first principles: the ideal-world definition, semi-honest and malicious models, additive sharing, Beaver triple mu…
Read article →Multi-Commodity Flow, in depth: LP formulations, integrality, the flow-cut gap and Garg-Konemann
Multi-commodity flow from first principles: joint capacities and the total, concurrent and min-cost objectives, a worked two-commodity example, tested…
Read article →Multi-Source BFS, in depth: seeding the queue, nearest-source labels, closest pairs of sources and reversed graphs
Multi-source BFS on general graphs: the virtual super-source argument, a Python template with labels and parents, a worked road-network trace, tie-bre…
Read article →Multi-Dimensional Knapsack, in depth: d-constraint DP, LP bounds, dual-price greedy and MILP solvers on a GPU packing example
The multi-dimensional knapsack problem from first principles: why the DP explodes, the LP relaxation and its fractional structure, greedy scores built…
Read article →Naive Bayes, in depth: from Bayes' rule to a calibrated text classifier, with a worked spam example
Naive Bayes from first principles: the conditional-independence factorisation, multinomial, Bernoulli, Gaussian and Complement event models, Laplace s…
Read article →Network Reliability, in depth: two-terminal reliability, exact factoring, path and cut bounds, and Monte Carlo with importance sampling
How to compute the probability that two nodes stay connected when links fail: why the problem is #P-complete, exact factoring by contraction and delet…
Read article →Backpropagation, in depth: reverse-mode autodiff from scratch, a hand-traced example, the MLP backward pass and gradient checking
Backpropagation as reverse-mode automatic differentiation: why one backward pass gives every gradient, a 60-line scalar engine, a hand-checked worked …
Read article →node2vec, in depth: second-order biased walks, the p and q parameters, alias tables versus rejection sampling, and a measured skip-gram pipeline
node2vec from first principles: the 1/p, 1, 1/q transition rule with a worked example, per-edge alias tables and their sum-of-squared-degree memory, r…
Read article →Number of Islands, in depth: one labelling pass for count, area, perimeter, shapes, closed islands, online union-find and bridges
The number of islands family solved from one iterative labelling pass: count, max area, perimeter, distinct shapes under translation or rotation, clos…
Read article →OAuth 2.0 + OpenID Connect, in depth: the relying party's login algorithm, ID token validation, discovery and logout
OpenID Connect from the relying party's side: state, PKCE, nonce and issuer values and what each protects, the code flow as a state machine, the …
Read article →Odd Cycle Transversal, in depth: bipartization by vertex deletion, iterative compression with min vertex cuts, kernels, ILP and applications
Odd cycle transversal from first principles: why it is NP-hard, the iterative compression FPT algorithm with a tested Python implementation, a worked …
Read article →Offline Dynamic Connectivity, in depth: edge lifetimes, a segment tree over time with rollback union-find, and the deletion-time spanning forest
Offline dynamic connectivity from first principles: turning adds and removes into lifetime intervals, a tested segment-tree-over-time solver with roll…
Read article →Robust Orientation Predicate, in depth: exact signs from floating-point inputs with error-free transformations and an adaptive filter
Making orient2d exact for double inputs: why the naive determinant fails on 53% of a near-collinear grid, two_sum and FMA two_product, expansions, the…
Read article →PageRank, in depth: the random surfer, dangling nodes, a sparse implementation, personalised PageRank and running it in production
PageRank from first principles: the random-surfer update with damping and dangling nodes, a hand-checked five-page example, a NumPy and SciPy power it…
Read article →Eertree, in depth: the palindromic tree, two roots, suffix-link walks, linear-time construction and counting palindromes
The eertree (palindromic tree) from first principles: why a string has at most n distinct palindromes, the two roots, insertion with two suffix-link w…
Read article →Password Hashing, in depth: bcrypt internals, the 72-byte limit, choosing parameters, Argon2id upgrade-on-login, legacy migration and operating the login path
A first-principles guide to password hashing centred on bcrypt: the offline attack model, EksBlowfish and the 60-character format, the 72-byte limit a…
Read article →Key Derivation Functions, in depth: PBKDF2 from scratch, memory-hard scrypt and Argon2id, HKDF extract-and-expand and choosing between them
Password-based and extract-and-expand key derivation explained from first principles: guess-cost arithmetic, PBKDF2 implemented and verified, its long…
Read article →Path Sum Problems Family, in depth: root-to-leaf checks, all paths, prefix-sum counting, maximum path sum and grid paths
One mental model for the path sum family of tree and grid problems: carrying state down a DFS, returning gains up, counting any downward path with pre…
Read article →PCA, in depth: variance maximisation and reconstruction error, a worked ten-point example, SVD done right, choosing k, scaling to big data and the failure modes
Principal component analysis from first principles: why the top eigenvectors maximise variance and minimise reconstruction error, a hand-worked exampl…
Read article →Percolation Theory, in depth: site and bond thresholds, critical scaling, and the Newman-Ziff union-find algorithm
Percolation from first principles for programmers: site and bond models, exact and numerical thresholds, critical exponents and finite-size scaling, t…
Read article →Perfect Graphs, in depth: χ = ω on every induced subgraph, the strong perfect graph theorem and polynomial coloring
Perfect graphs from first principles: clique and chromatic numbers, the weak and strong perfect graph theorems, the classical perfect families, an odd…
Read article →Perfect Squares, in depth: the minimum-squares DP, BFS over remainders and the Lagrange-Legendre O(sqrt n) shortcut
Minimum number of perfect squares summing to n, built from first principles: why greedy fails, the recurrence and bottom-up DP in Python and Java, a h…
Read article →Permutations and Combinations by Backtracking, in depth: decision trees, duplicates, combination sum, next permutation, the Heap algorithm and ranking
Generating permutations, combinations and subsets correctly: the decision tree and its output-size cost, used-array and swap permutations, start-index…
Read article →Persistent Segment Tree, in depth: path copying, prefix versions, k-th smallest in a range and range updates on old versions
Persistent segment trees from first principles: path copying and immutability, a node pool with a shared empty sentinel, prefix versions that subtract…
Read article →Piece Table, in depth: immutable buffers, a tested implementation, cheap undo and the piece tree inside VS Code
How the piece table text-editor data structure works: original and add buffers, piece splits on insert and delete, a fuzz-tested Python implementation…
Read article →Planar Max Flow, in depth: dual shortest paths, recovering the flow from potentials, and beyond st-planar graphs
Maximum flow in planar graphs: why the min cut is a shortest dual path when s and t share a face, how dual distances become a feasible maximum flow, a…
Read article →Planarity Testing
Determine if a graph can be drawn on a plane without edge crossings in linear time O(V+E). Kuratowski and Wagner characterizations, Hopcroft-Tarjan pa…
Read article →Point in Polygon, in depth: crossing number, winding number and the boundary cases that break them
Point-in-polygon from first principles: ray crossing versus winding number, the half-open rule for vertices and horizontal edges, exact integer code w…
Read article →Point-to-Line and Point-to-Segment Distance, in depth: projection, cross products, clamping and robust code
Point-to-line and point-to-segment distance derived from vectors: the projection parameter t, the cross-product and implicit-line formulas, 3D, clampi…
Read article →Populate Next Right Pointers in a Binary Tree, in depth: queue BFS, O(1)-space level walking, the dummy-head trick and the traps in each
A complete guide to populating next right pointers in perfect and arbitrary binary trees: the level-order linked list model, queue BFS, the constant-s…
Read article →Post-Quantum Hash-Based Signatures, in depth: Lamport, Winternitz, Merkle trees, stateful LMS and XMSS, and stateless SLH-DSA
How hash-based post-quantum signatures work from first principles: Lamport and Winternitz one-time keys with code, Merkle trees, stateful LMS and XMSS…
Read article →Post-Quantum Crypto, in depth: learning with errors, Module-LWE and how ML-KEM is built
Lattice-based post-quantum cryptography from first principles: LWE, Module-LWE, the K-PKE core of ML-KEM in tested Python with a measured noise budget…
Read article →Post-Quantum Migration Strategy, in depth: Mosca's inequality, a cryptographic inventory, hybrid key exchange, the signature problem and crypto-agility
How to plan a post-quantum cryptography migration: what Shor and Grover break, ML-KEM, ML-DSA and SLH-DSA with real sizes, Mosca's inequality as …
Read article →Prim's Minimum Spanning Tree, in depth: the cut property, lazy and eager heaps, the dense-graph version and the bugs that break it
Prim's algorithm from first principles: what a minimum spanning tree is, why growing one tree greedily is correct (the cut property), a worked ex…
Read article →Prime Counting Function π(x), in depth: Legendre, Meissel-Lehmer and Lucy's O(x^3/4) algorithm, with tested code
Counting primes without listing them: x / ln x and li(x) as sanity checks, Legendre's phi traced by hand for x = 100, Meissel-Lehmer and its P2 t…
Read article →Prime Factorization, in depth: a tiered pipeline for every 64-bit integer, from trial division and deterministic Miller-Rabin to Montgomery arithmetic and the hand-off to ECM
Factor any unsigned 64-bit integer correctly: trial division, a smallest-prime-factor table, the 12-base deterministic Miller-Rabin and its exact boun…
Read article →Primitive Roots and Discrete Logarithms, in depth: orders, the generator test, baby-step giant-step, Pohlig-Hellman, Pollard rho and safe parameters
Primitive roots and the discrete logarithm problem from first principles: element orders, the factor-based generator test, a hand trace modulo 23, bab…
Read article →Priority Queue via Binary Heap, in depth: an indexed heap with update and remove, stable ties, a scheduler and the tests that keep it honest
Build a production priority queue on a binary heap: the abstract contract, a complete indexed min-heap with push, pop, update and remove, why removal …
Read article →Prüfer Sequence, in depth: the smallest-leaf encoding, linear-time encode and decode, Cayley's formula, degree-constrained counting and uniform random labelled trees
The Prüfer bijection between labelled trees and sequences: a hand-worked encoding and decoding, O(n) encode and decode in Python with edge cases, why …
Read article →Push-Relabel Max Flow, in depth: preflows, height labels, a traced worked example, gap and global relabel heuristics
Push-relabel maximum flow from first principles: preflows and excess, why valid height labels rule out augmenting paths, push and relabel with current…
Read article →Quadratic Residues and Tonelli-Shanks, in depth: square roots modulo p, Cipolla, Hensel lifting, CRT and point decompression
How to compute square roots modulo a prime and beyond: the Euler test, the p = 3 mod 4 shortcut, Tonelli-Shanks with a full worked trace, Cipolla, Hen…
Read article →Quadtree and Octree, in depth: PR quadtrees, depth versus point spacing, Morton keys, Barnes-Hut and GPU builds
Quadtrees and octrees from first principles: point versus PR quadtrees, why depth depends on the closest pair rather than n, tested Python with a dept…
Read article →Rabin-Karp, in depth: the rolling hash, overflow-safe arithmetic, collision bounds, multi-pattern search and substring hashing
How Rabin-Karp and the rolling hash work from first principles: the polynomial and its O(1) roll, a worked example by hand, Mersenne-prime arithmetic …
Read article →Radix (Patricia) Tree, in depth: path compression, edge splits and merges, prefix search, longest-prefix match and where radix trees run
A first-principles guide to radix trees and PATRICIA: the compression invariant, fuzz-tested Python for insert with edge splitting, delete with mergin…
Read article →Random Forest, in depth: correlated averaging, out-of-bag estimates, MDI versus permutation importance, and tuning
How random forests work and how to use them: the ρσ² variance bound, bootstrap rows plus per-split feature sampling, a from-scratch implementation, ou…
Read article →Erdős-Rényi Random Graphs, in depth: G(n, p) and G(n, m), the giant component, the connectivity threshold and O(n + m) generation
Erdős-Rényi random graphs from first principles: G(n, p) versus G(n, m), Poisson degrees, the branching-process derivation of the giant component, the…
Read article →Random Spanning Tree, in depth: why MST and DFS are biased, Aldous-Broder, the Wilson loop-erased walk, effective resistance and testing a sampler
How to sample a uniformly random spanning tree: matrix-tree counting, an exact demonstration that random-weight MST and randomised DFS are biased, the…
Read article →Range Tree, in depth: multi-dimensional orthogonal range queries, canonical nodes, fractional cascading and rank-space ties
How a range tree answers multi-dimensional orthogonal range queries: the tree of trees, a tested Python 2-D implementation, a traced query on eight po…
Read article →Red-Black Tree, in depth: the five properties, the height proof and an invariant checker
Red-black tree properties from first principles: which rules carry the 2 log(n+1) height bound, what breaks when each is dropped, the 2-3-4 tree corre…
Read article →Regex Engines, in depth: backtracking versus Thompson-style matching, a working Pike VM with captures, how RE2 and Rust regex compose strategies, and leaving ReDoS behind
How regex engines really work: backtracking versus Thompson-style simulation, a tested Pike VM with capture groups, leftmost-first versus POSIX semant…
Read article →Q-Learning, in depth: the Bellman target, off-policy updates, a hand-worked example, convergence conditions, SARSA, Double Q-learning and DQN
Q-learning from first principles: the Bellman optimality equation, the temporal-difference update and why it is off-policy, a corridor example worked …
Read article →Reverse-Delete MST, in depth: the cycle property, a tested Python implementation, a traced example and why Kruskal wins
Reverse-delete computes a minimum spanning tree by deleting the heaviest non-bridge edges: the cycle property proof, tie-breaking, a BFS implementatio…
Read article →Reverse a Linked List, in depth: the three-pointer loop, its invariant, recursion and the stack limit, sublist and k-group reversal
How to reverse a singly linked list in place from first principles: the iterative three-pointer loop and why it is correct, a worked trace, the recurs…
Read article →RNN, LSTM and GRU, in depth: exact gate equations, a gradient-checked NumPy LSTM, parameter counts, truncated BPTT, packing, and when recurrence still wins
Recurrent networks from first principles: plain RNN, LSTM and GRU equations in PyTorch's convention, the additive cell-state path, forget-gate bi…
Read article →Rod Cutting, in depth: the DP as the pricing engine of cutting stock column generation
Rod cutting beyond the textbook: the unbounded-knapsack DP as the pricing step of Gilmore-Gomory column generation for cutting stock, dual prices, Sci…
Read article →Rope, in depth: weighted trees for big mutable text, split and concat, Fibonacci balancing, B-tree ropes with line and UTF-16 metrics, and structural sharing for undo
How the rope data structure works: the weight invariant, index, split and concat with a tested Python implementation, the Boehm-Atkinson-Plass balance…
Read article →Rotating Calipers, in depth: antipodal pairs, diameter, width and the minimum-area bounding rectangle in linear time
Rotating calipers from first principles: supporting lines and antipodal pairs, why one monotone pointer suffices, exact-integer Python for diameter, w…
Read article →OSPF Routing, in depth: adjacencies, LSAs and flooding, SPF with the two-way check and ECMP, areas and convergence
How OSPF turns Dijkstra into a distributed routing protocol: neighbour states, LSA types, sequence numbers and reliable flooding, SPF with the two-way…
Read article →RSA, in depth: key generation with lambda(n), a correct proof, OAEP and PSS, real attacks, key sizes and the post-quantum deadline
How RSA works and how to use it safely: FIPS-style key generation with code, a complete proof that decryption works, a hand-checkable worked example, …
Read article →Scale-Free Networks, in depth: preferential attachment in linear time, the exact Barabási-Albert degree law, fitting and testing power laws properly, the rarity debate, and robustness to random versus targeted failure
Scale-free networks with working code: an O(nm) Barabási-Albert generator, the exact degree distribution 2m(m+1)/(k(k+1)(k+2)), maximum-likelihood pow…
Read article →ScaNN: Anisotropic Vector Quantization for Maximum Inner Product Search
ScaNN in practice: train an anisotropic codebook in NumPy with the closed-form update, see what the threshold does to the parallel weight, configure t…
Read article →Second-Best MST, in depth: the one-swap theorem, strict versus non-strict, path-maximum queries with binary lifting and a brute-force test
Second-best minimum spanning tree from first principles: why one edge swap suffices, a traced six-vertex example, the strict-mode trap with tied weigh…
Read article →Shamir's Secret Sharing, in depth: polynomials over finite fields, Lagrange at zero, a worked example, GF(256) byte shares and verifiable sharing
How Shamir's threshold secret sharing works: the secrecy proof, why arithmetic must be in a finite field, tested Python for prime fields and GF(2…
Read article →Segment Tree Beats, in depth: range chmin with sums, the strict second maximum, tag order and the amortised bound
How segment tree beats (Ji's segment tree) supports range chmin, chmax and add with range sums: the max, strict second max and count fields, the …
Read article →Segment Trees for Geometry, in depth: coordinate compression, cover counts, rectangle union area, perimeter and deepest overlap
How segment trees combine with a sweep line to solve geometric problems: elementary intervals, the cover-count tree without lazy propagation, union ar…
Read article →The SHA Family, in depth: SHA-256 from scratch, Merkle-Damgard and length extension, the fall of SHA-1, the SHA-3 sponge and choosing a hash
SHA-1, SHA-2 and SHA-3 explained from first principles: security properties and the birthday bound, Merkle-Damgard padding worked for 'abc',…
Read article →Grid Shortest Path Variants, in depth: 4 vs 8 connectivity, corner cutting, octile A*, weighted cells, portals and k-jump BFS with skip pointers
How the move model and cost model choose the algorithm for grid shortest paths: BFS, 0-1 BFS, Dial, Dijkstra and A* with the octile heuristic, corner-…
Read article →Detecting Negative Cycles, in depth: the Bellman-Ford proof, extracting the cycle, finding every affected vertex, and currency arbitrage
How to detect negative cycles in a weighted directed graph and act on the result: why the n-th Bellman-Ford pass is a proof, the virtual-source trick,…
Read article →Shortest Path with Waypoints, in depth: ordered legs, Held-Karp over a distance matrix, state-space Dijkstra and the walk versus simple path trap
How to find the cheapest route from s to t through required waypoints: stitched Dijkstra legs for a fixed order, a fixed-endpoint Held-Karp DP for a f…
Read article →SSSP with Negative Edges, in depth: why Dijkstra breaks, a tested Dijkstra-Bellman-Ford hybrid, potentials, scaling and the post-2022 algorithms
Single-source shortest paths when some edges are negative: why Dijkstra fails, negative cycles and termination, Bellman-Ford and SPFA, a Dijkstra-Bell…
Read article →Side-Channel Attacks, in depth: timing, cache, power and speculation, constant-time code and testing for leaks
Side-channel attacks from first principles for engineers: timing, cache, power and speculative channels, why early-exit comparison leaks with a worked…
Read article →Small-to-Large Merging, in depth: the doubling argument, subtree queries in O(n log n), carrying aggregates, the sack variant, and where it breaks
Small-to-large merging from first principles: why naive merging is quadratic, the proof that each element moves at most log2 n times, measured move co…
Read article →Small-World Networks, in depth: Watts-Strogatz, clustering and path length, measuring small-worldness and Kleinberg navigability
A practical guide to small-world networks: clustering coefficient and average path length, the Watts-Strogatz rewiring model in Python, a reproducible…
Read article →Smallest Enclosing Circle, in depth: Welzl's randomized algorithm, why it runs in expected linear time, and a robust implementation
The smallest enclosing circle from first principles: uniqueness and support sets, Welzl's recursive and iterative algorithms, backwards analysis …
Read article →Sort Linked List, in depth: merge sort on a singly linked list, top-down and bottom-up, with the bugs that break it
Why merge sort is the right sort for singly linked lists, how to split with slow and fast pointers without the two-node infinite loop, an iterative st…
Read article →Spectral Clustering, in depth: graph Laplacians, the Fiedler vector, normalised cuts and k-NN graphs
Spectral clustering from first principles: the graph Laplacian and why its smallest eigenvectors reveal clusters, ratio and normalised cut relaxations…
Read article →SPFA, in depth: queue-based Bellman-Ford, its real worst case, negative-cycle detection and when to choose it
The Shortest Path Faster Algorithm explained from first principles: why only improved vertices need rescanning, a correct implementation with hop-coun…
Read article →Steiner Tree, in depth: the metric-closure 2-approximation, exact Dreyfus-Wagner dynamic programming, a worked example and geometric variants
How to connect a subset of vertices at minimum cost: why the Steiner tree problem is NP-hard, the metric-closure MST 2-approximation with its proof, t…
Read article →Stern-Brocot Tree, in depth: mediants and the determinant invariant, paths as continued fractions, O(log N) oracle search, simplest fractions in an interval, and Farey sequences
The Stern-Brocot tree with tested Python: why every positive rational appears once in lowest terms, L/R paths and the matrix form, run-length paths fr…
Read article →Stoer-Wagner Minimum Cut, in depth: maximum adjacency ordering, the cut-of-the-phase proof, a traced example and tested code
How the Stoer-Wagner global minimum cut algorithm works: maximum adjacency ordering, why the cut of the phase is a minimum s-t cut, a six-vertex hand …
Read article →String Hashing, in depth: prefix hashes, provable collision bounds, the 2^64 trap and the 2^61 - 1 modulus
Polynomial string hashing as a data structure: prefix hashes for constant-time substring equality, the (n-1)/m collision bound and its birthday-scale …
Read article →Wildcard Matching via FFT, in depth: three correlations, measured precision and blocking for O(n log m)
Pattern matching with single-symbol wildcards in text and pattern via FFT: the p t (p - t)^2 identity, tested NumPy code, a hand-checked example, meas…
Read article →Strong Bridges and Strong Articulation Points, in depth: the dominator reduction, a verified implementation and a worked example
Find the single points of failure of a strongly connected directed graph: why undirected low-link fails, how dominators in the graph and its reverse g…
Read article →Subset Sum Backtracking, in depth: the decision tree, sorted break and suffix-sum pruning, duplicate-free enumeration, branch and bound and measured limits
Subset sum when the DP table is too big: backtracking with an ascending-order break and suffix-sum bound, their positivity preconditions, duplicate-fr…
Read article →Subset Sum, in depth: existence and counting tables, bitsets, every target in one pass, size-k counts, undoing an item and the pseudo-polynomial wall
Subset sum from first principles: the boolean and counting dynamic programs, why the inner loop runs backwards, a big-integer bitset, counting under a…
Read article →Succinct Data Structures, in depth: the information-theoretic bound, rank and select, Elias-Fano and trees in two bits per node
Succinct data structures from first principles: the counting bound, rank and select directories and their overheads, Elias-Fano for sorted integers wi…
Read article →Sudoku Solver, in depth: bitmask candidates, MRV, hidden singles, exact cover with Algorithm X, uniqueness and generation
How to build a fast Sudoku solver: bitmask row, column and box state, minimum remaining values, hidden singles, the 324-column exact cover formulation…
Read article →Suffix Array Construction, in depth: prefix doubling with radix passes, SA-IS induced sorting traced step by step, and building at scale
How to build suffix arrays: the sentinel and alphabet contract, O(n log n) prefix doubling with radix passes, linear-time SA-IS with L/S types, LMS su…
Read article →Suffix Arrays, in depth: prefix doubling in code, SA-IS in outline, pattern search, LCP-powered queries and the BWT connection
Suffix arrays from first principles: the banana example, why naive sorting is quadratic, prefix doubling with sort and radix versions in tested Python…
Read article →Substring Search via Suffix Array Binary Search, in depth: lower and upper bound, prefix-aware comparison, min(l, r) skipping and O(m + log n) with LCP
How to find every occurrence of a pattern with a suffix array: the contiguous-range lemma, a correct prefix comparison, lower and upper bound in teste…
Read article →Suffix Automaton, in depth: endpos classes, the clone step, linear-size bounds, occurrence counts, k-th substring and a full abcbc trace
The suffix automaton from first principles: endpos equivalence, suffix links, online construction with the clone step, the 2n-1 and 3n-4 bounds, alpha…
Read article →DAWG, in depth: minimal word graphs, incremental construction from sorted input, perfect hashing and packed dictionaries
The directed acyclic word graph from first principles: right languages and the register, trie minimisation, the Daciuk sorted-input incremental builde…
Read article →Suffix Tree, in depth: from suffix tries to Ukkonen's linear-time construction, tested Python, a banana$ trace and the queries it unlocks
How suffix trees work: compressing a suffix trie to O(n) nodes, Ukkonen's online construction with the global end, active point and suffix links,…
Read article →Sum of Root-to-Leaf Numbers, in depth: Horner's rule on a tree, recursive, stack, BFS and O(1)-space Morris solutions, variants and pitfalls
Solve Sum Root to Leaf Numbers (LeetCode 129) from first principles: prefix values via Horner's rule, recursive, explicit-stack, level-order and …
Read article →Suurballe's Algorithm, in depth: two disjoint shortest paths with two Dijkstra runs, reduced weights, cancellation and network protection
Suurballe's algorithm from first principles: why remove-and-retry fails, reduced weights and residual graphs, a traced example, tested Python cod…
Read article →Support Vector Machines and the Kernel Trick, in depth: maximum margin, the dual, a hand-solved XOR example, a working SMO solver and practical tuning
Support vector machines from first principles: hard and soft margins, hinge loss, the dual and KKT conditions, why kernels work and when they are vali…
Read article →Symmetric Tree Check, in depth: the mirror invariant, recursive and iterative solutions, traps that look correct, and checking every subtree in linear time
How to decide whether a binary tree is a mirror image of itself: the pair-based invariant, recursive and queue-based code in Python and Java, a pair-b…
Read article →t-SNE, in depth: perplexity calibration, the Student-t map, the gradient, Barnes-Hut and what the plot does not show
t-SNE from first principles: per-point sigma by perplexity binary search, the symmetric P and heavy-tailed Q, the KL gradient, a tested numpy implemen…
Read article →Target Sum, in depth: from 2^n sign assignments to a subset-sum count, with the offset table, the parity rule, zeros, reconstruction and meet in the middle
How to count the ways to put + or - in front of each number so the total equals a target: brute force as a reference, memoised recursion, the offset t…
Read article →Tarjan's SCC, in depth: low-links, the on-stack rule, an iterative implementation and what the condensation buys you
Strongly connected components of a directed graph in one depth-first search: discovery indices and low-links from first principles, why the on-stack c…
Read article →Temporal Graphs, in depth: time-respecting paths, earliest arrival, fastest and latest-departure algorithms
Graphs whose edges happen at specific times: contact sequences, strict and non-strict journeys, why reachability stops being transitive, one-pass earl…
Read article →Thorup's Algorithm, in depth: linear-time undirected shortest paths with integer weights, the component hierarchy, bucketed visiting and a tested implementation
Thorup's O(m) single-source shortest paths for undirected graphs with positive integer weights: the model it needs, the bucket lemma, the compone…
Read article →TLS 1.3 Handshake, in depth: the message flow, what each message proves, the client state machine, a runnable toy handshake and the attacks it stops
The TLS 1.3 handshake explained as an algorithm: one-round-trip message flow, what ClientHello, ServerHello, CertificateVerify and Finished each prove…
Read article →Topological Sort, in depth: the Kahn algorithm as a live scheduler, with priorities, retries and failure propagation
The Kahn algorithm run as a DAG executor rather than a sort: the task state machine, event-driven dispatch versus level barriers, critical-path priori…
Read article →Topological Sort, in depth: batch versus online, and keeping an order valid as edges arrive with Pearce-Kelly
The two ways software needs a topological order: once, over a finished graph (Kahn or DFS), or continuously, while edges keep arriving. A compact batc…
Read article →Traveling Salesman Problem
Bitmask DP: O(2^N × N²) beats brute-force O(N!). Subset enumeration, state definition, recurrence, and the exact boundary where approximation takes ov…
Read article →Treap, in depth: a binary search tree balanced by random priorities, with split, merge, order statistics and implicit keys
How a treap works and how to implement one: the BST and heap invariants, why random priorities give expected O(log n) depth, split and merge as the tw…
Read article →Tree Diameter, in depth: the double sweep, the top-two DP, centers and where the shortcut breaks
Tree diameter from first principles: definitions and conventions, the double-sweep algorithm and its proof, the one-pass top-two dynamic program, iter…
Read article →Tree Isomorphism Check, in depth: AHU canonical ids, centres for free trees and subtree hashing
How to decide whether two trees are isomorphic: rooted versus free and ordered versus unordered trees, why canonical strings are quadratic, the AHU al…
Read article →Tree Views, in depth: right, left, top and bottom views with BFS, DFS, tie rules and a worked example
Binary tree right, left, top and bottom views from first principles: depth versus horizontal distance, BFS and iterative DFS code, the preorder top-vi…
Read article →Treewidth, in depth: tree decompositions, min-fill elimination orderings, lower bounds, a tested DP over bags, nice decompositions and exact solvers
A practical guide to treewidth: the three decomposition rules, building bags from a min-fill elimination ordering, degeneracy and minor-min-width boun…
Read article →Trie, in depth: bitwise tries, longest-prefix match for IP routing, multibit strides, HAMT bitmap nodes and the lock-free Ctrie
Tries over bits rather than characters: longest-prefix match with a working binary trie and worked routing example, why one bit per level is slow, mul…
Read article →Trie (Prefix Tree), in depth: building a ranked, typo-tolerant autocomplete with best-first top-k, Levenshtein pruning and snapshot builds
Use a trie as the engine of a real autocomplete service: normalised keys, subtree-maximum scores, best-first top-k search with a heap, a worked trace,…
Read article →2-SAT via SCC, in depth: why component order is the assignment, an iterative solver, contradiction cycles and forced literals
How strongly connected components solve 2-SAT in linear time: the skew-symmetric implication graph, a proof that component order yields a model, Tarja…
Read article →Union-Find with Rollback, in depth: undo logs, why compression breaks it, offline dynamic bipartiteness and backtracking
A first-principles guide to union-find with rollback: why path compression and amortisation break undo, what the undo log stores, tested Python code w…
Read article →Union-Find Variants, in depth: potential DSU, component aggregates, movable elements, next-free slots and offline dynamic connectivity
Five union-find variants built and run: potential (offset) DSU with contradiction detection and the compression-order trap, per-component aggregates a…
Read article →van Emde Boas Tree, in depth: the sqrt(u) recursion, lazy minimum, a tested implementation and when bitmaps win
How van Emde Boas trees reach O(log log u) for successor, insert and delete: high and low bit splits, the stored minimum, a worked u = 16 example, tes…
Read article →Vertex Cover, in depth: the maximal-matching 2-approximation, LP rounding and local ratio for weights, kernels for small k, and the hardness limits
Approximating minimum vertex cover in general graphs: the maximal-matching 2-approximation and its per-instance certificate, pruning, why greedy degre…
Read article →Vertex Cover in Bipartite Graphs, in Depth
Minimum vertex cover in bipartite graphs via Konig's theorem: the proof, the alternating-path construction from a maximum matching, verified Pyth…
Read article →Voronoi Diagram, in depth: bisectors and convex cells, a hand-computed example, Fortune's sweep, working clipping code and robustness traps
Voronoi diagrams from first principles: cells as half-plane intersections, the Delaunay dual and empty-circle property, size bounds, a three-site exam…
Read article →Wavelet Tree, in depth: rank on bit vectors, the wavelet matrix, range k-th and counting queries, select, and real-world engineering
Build a wavelet tree and wavelet matrix from first principles, with tested Python for access, rank, quantile and range counting, a hand-traced example…
Read article →Word2Vec, in depth: skip-gram, negative sampling and its gradients, subsampling, a tested NumPy trainer and the PMI view
Word2Vec from first principles: skip-gram and CBOW, the negative-sampling objective and update, subsampling and the unigram^0.75 noise distribution, a…
Read article →Word Search
Word search on a 2D grid: why the no-revisit constraint kills memoisation, in-place marking vs a visited bitmask, the 3^L bound, frequency and reversa…
Read article →Yen's Algorithm, in depth: K shortest loopless paths, root and spur paths, a traced example with ties, tested Python and Lawler's speedup
Yen's K shortest loopless paths algorithm from first principles: the root and spur path idea, why the candidate heap must persist, a hand-traced …
Read article →Z-Algorithm, in depth: the Z-box invariant, a linear-time proof, pattern search in O(m) memory, periods and the prefix function
How the Z-algorithm computes the Z-array in linear time: the definition, the Z-box and its clamp, the amortised proof, a full hand trace, tested Pytho…
Read article →Zero-Knowledge Proofs, in depth: Schnorr by hand, Fiat-Shamir, circuits, SNARKs versus STARKs and how they break
Zero-knowledge proofs from first principles: completeness, soundness and simulators, a worked Schnorr protocol with small numbers, Fiat-Shamir and the…
Read article →