24 algorithms in Programming
- Algorithm
0/1 Knapsack
Greedy density starves at 42 while fractional promises 66: how a lattice DAG captures the true 58-value pack.
Pack a mountaineer's rucksack for a deadly ascent. Greedy heuristics chase density and starve on dead weight; the true optimum is a ghost threading a lattice DAG, leaving an insurmountable integrality gap between continuous relaxations and indivisible cargo.
optimization · graph-theory · complexity
- Algorithm
Bellman–Ford
Dijkstra freezes T at 12; relax all edges across 4 rounds to uncover the -11 siphon.
It is not a slower Dijkstra for broken edges. It is a deflationary gravity: a monotone operator pressing down on every road simultaneously until distances freeze into their least fixed point—or spiral endlessly into a negative abyss.
order-theory · algebra · fixed-point-theory
- Algorithm
Binary Search
Scan 10^18 records for 31.7 years, or split the sorted horizon in 60 comparisons flat.
To search a billion records, a linear scan must traverse the continent of data footprint by footprint. Binary search cuts the entire continent in half thirty times. In thirty questions, a search space larger than humanity collapses to a single atom.
analysis · information-theory · order-theory
- Algorithm
Bipartite Matching
Greedy pairing strands Ben and locks only two bays: how alternating resignation chains achieve the maximum of three.
Tether two disjoint universes through a web of fragile handshakes. Eager pairings leave orphaned nodes in the cold; true optimality surges through alternating paths of swapped commitments, pinned between Hall's suffocating neighborhood trap and König's impenetrable vertex shield.
combinatorics · graph-theory · optimization
- Algorithm
Breadth-First Search
DFS circles the rim in 4 hops; expand in concentric ripples to hit the 3-hop chord.
It is not a graph traversal. It is an unweighted shockwave detonating from a single spark: expanding in concentric spheres of integer distance, carving out the exact geodesic metric of the graph one frontier at a time.
graph-theory · order-theory · combinatorics
- Algorithm
Coin Change
Greedy burns three coins (4+1+1) where two (3+3) settle the debt: how shortest paths solve non-canonical change.
The cashier's reflex to grab the largest coin is an arithmetic trap. Minimum coin change is a shortest path through a discrete lattice of debt, and greedy choices tumble into disaster the instant a currency ceases to be canonical.
graph-theory · number-theory · complexity-theory
- Algorithm
Depth-First Search
Visited flags blur ancestry; log 12 timestamps across 6 vertices to catch the single back edge.
It is not a blind plunge into the dark. It is a dual-clock crystallization: each vertex is entered with a timestamp and exited with an epitaph, freezing the chaos of a graph into a laminar geometry of perfectly nested time intervals.
graph-theory · order-theory · combinatorics
- Featured
Dijkstra's Algorithm
Linear scans probe 58 days across 10^8 towns; pull the least label from a heap with zero regrets.
It is not a search for a path. It is a wave of light radiating through glass of different thicknesses: the moment a town is touched, its distance is carved in stone forever, because light cannot travel backward in time.
order-theory · algebra · optimization
- Algorithm
Edit Distance
A single shifted byte shows 8 false mismatches; tile the prefix grid to find the true distance of 2.
Every word is a coordinate in an infinite space of strings. Insert, delete, and mutate are unit vectors across its grid; edit distance is the exact geodesic, carving the shortest trek through a lattice of prefixes.
graph-theory · metric-geometry · combinatorics
- Algorithm
Fixed-Point Iteration
At q=0.9999 one digit costs 23,025 steps; at q=0.6736 it takes 5.8: how the cobweb spiral converges to a fixed point.
Take any crumpled map and toss it onto the floor: exactly one point rests directly above the coordinate it represents. A contraction mapping folds an entire metric space inward, reeling every starting guess into an inescapable attractor at rate qⁿ.
analysis · numerical-analysis · geometry
- Algorithm
Floyd–Warshall
Four lines and 10^9 updates solve all-pairs distances for 1,000 towns: how three nested loops sweep a network.
It is not a road-trip calculator. It is a universal matrix inversion engine: swap out two algebraic symbols, and the exact same four-line loop morphs from pricing shortest paths into counting quantum walks, proving reachability, or decoding hidden Markov trellises.
algebra · order-theory · combinatorics
- Algorithm
Huffman Coding
An early merge levies 0.20 bits/symbol forever; graft the two lightest to save 125 MB per billion.
Flip the message upside down. Pair the two rarest whispers in an alphabet, fuse them into a single stem, and climb upward until the entire language hangs from one root—its average cost pinioned within a single bit of Shannon's thermodynamic limit.
information-theory · combinatorics · optimization
- Algorithm
Karatsuba Multiplication
At 2^20 digits, 4^20=1.1×10^12 products drops to 3^20=3.49×10^9: how three multiplications beat four.
In 1960, Kolmogorov conjectured that multiplying two n-digit numbers fundamentally requires n² operations. Within a week, a 23-year-old student proved him wrong with three products instead of four: a single algebraic subtraction that cracked open the sub-quadratic universe.
algebra · analysis · information-theory
- Algorithm
Longest Common Subsequence
4,225 cells replace 2^32 brute-force candidates: how git diff extracts identical lines from diverging files.
Lay two strings along the axes of a plane and watch their shared letters ignite into a constellation of points. The longest common subsequence is the maximal chain climbing through this poset—the highest monotone ridge connecting two divergent texts.
order-theory · combinatorics · algorithms
- Algorithm
Longest Increasing Subsequence
1.66M comparisons beat 10^30103 brute-force paths: how patience sorting extracts the longest ascending run.
Deal a shuffled deck into solitaire piles: each card must sit on a strictly larger predecessor, or start a new pile to the right. The moment the deck runs out, the count of piles is no mere card trick—it is the height of a hidden poset, locked in perfect duality with the longest ascending path through the chaos.
order-theory · combinatorics · algorithms
- Algorithm
Maximum Flow
Greedy routing chokes on saturated pipes; push residual flow to close the duality gap from 8 to 0.
Pump fluid through a pipe network until the seams burst. The instant the flow chokes, the network reveals an invisible geometric fault-line: a razor-thin cut across the world where every single pipe is gorged to capacity.
linear-programming · optimization · graph-theory
- Algorithm
Merge Sort
Scanning 10^9 keys takes 15.8 years; von Neumann's two-finger merge does it in 28.9 seconds with n log n passes.
Sorting unordered chaos appears to require combinatorial omniscience. In 1945, John von Neumann proved it requires only a two-finger zipper: split the universe down to isolated atoms, then weave them back together one comparison at a time.
algebra · analysis · information-theory · order-theory
- Algorithm
Minimum Spanning Tree
Cayley counts 10^196 spanning trees for 100 cities; Kruskal finds the cheapest in 60,700 comparisons without regret.
It is not a cautious hoarder picking cheap twigs. It is the geometric miracle of a matroid: short-sighted, local greed is mathematically guaranteed to carve out the globally optimal skeleton without a single step of regret.
combinatorics · optimization · graph-theory
- Algorithm
Newton's Method
Bisection takes 3,322 steps for 1,000 digits; shoot the tangent line to double precision in 11.
Standard algorithms crawl toward truth one digit at a time. Newton's method rides a tangent line straight down to the coordinate axis: once inside the basin of attraction, every single step squares the error, doubling the count of correct decimal digits in a blinding geometric flash.
analysis · numerical-analysis · geometry
- Algorithm
Quicksort
A naive pivot burns 5×10^9 comparisons on sorted input; partition around pivots to sort in 2M steps.
Quicksort is not partitioning numbers on a chalkboard. It is a random binary search tree materialising in memory out of pure probability: every comparison creates an edge, and the execution time is the summed depth of that living tree.
probability · combinatorics · analysis
- Algorithm
Stable Matching
Greedy pairings collapse to rogue defectors; deferred acceptance settles in 4 rounds with 0 blocking pairs.
Pair two warring camps where every individual harbours private desires and fierce rankings. What prevents revolt is not goodwill, but the cold geometry of deferred acceptance: an unshakeable equilibrium where no clandestine pair in the room would rather elope together than stay with their assigned partners.
combinatorics · game-theory · order-theory
- Algorithm
Strassen's Algorithm
At n=2^30, 1.24×10^27 products drops to 2.25×10^25: how seven products broke the cubic wall of linear algebra.
For centuries, multiplying four numbers in a square demanded eight multiplications — treated as an immutable law of arithmetic. Strassen discovered that eight is a lie: seven is enough. That single missing product permanently broke the cubic wall of linear algebra.
algebra · multilinear-algebra · complexity-theory
- Algorithm
Topological Sort
Only 5 of 720 execution orders prevent catastrophic engine stall: how Kahn's queue peels a DAG into a schedule.
Thread an arrow of time through a tangled web of dependencies so that no consequence ever precedes its cause. The instant a circular dependency creeps in, causality fractures—revealing that sorting a DAG is the act of choosing one linear reality among an astronomical sea of valid futures.
order-theory · combinatorics · graph-theory
- Featured
Union–Find
Rewrite every block label in 31.7 years, or climb the partition lattice in 4 seconds with the Ackermann bound.
Begin with a universe of isolated atoms. Every merge is an irreversible climb up a crystal mountain that can never be descended. By the summit, the cost of each step is governed by the slowest-growing function in human mathematics.
order-theory · algebra · analysis