The Treap
The randomized tree that is both a binary search tree and a heap, formalized by Seidel and Aragon in 1989, and its simple expected balance.
36 posts about computer science
The randomized tree that is both a binary search tree and a heap, formalized by Seidel and Aragon in 1989, and its simple expected balance.
A comprehensive, chronological reference on the history of social media, from early computer networks and bulletin board systems to the rise of modern centralized platforms and the emerging decentralized web.
A comprehensive, chronological history of information theory, from its thermodynamic and telegraphic precursors through Claude Shannon's 1948 revolution, the development of error-correcting codes, and its modern applications in networking, quantum computing, and machine learning.
The character-indexed tree behind autocomplete and routing tables, named by Fredkin in 1960 from the word retrieval, and its space tradeoffs.
From imperative and structured code to object-oriented and functional styles, and why each won and then drew the next backlash.
The ordered tree that makes search, insertion, and deletion logarithmic, its independent discoveries around 1960, and why balance matters.
The 1987 rolling-hash approach to string matching, how it finds multiple patterns efficiently, and its use in plagiarism and duplicate detection.
The moment your software runs on more than one machine, a new set of rules takes over, and most of them are counterintuitive. Here are the core ideas, including what the CAP theorem actually says, stated without the usual oversimplification.
The dynamic-programming method for all-pairs shortest paths, its 1962 formulation, and its connection to Kleene's work on regular expressions.
The array-backed heap that powers heapsort and scheduling, introduced by J. W. J. Williams in 1964, and how it keeps the extremum at the root.
The adaptive hybrid sort Tim Peters wrote for Python in 2002, how it exploits existing runs, and the bug formal verification later found in it.
A comprehensive history of floating-point arithmetic, from Konrad Zuse's first implementation to the proprietary mainframe formats, the landmark IEEE 754 standard, and the new specialized formats driven by artificial intelligence.
How hashing turned lookup into near-constant time, from Hans Peter Luhn's 1953 IBM memo and open addressing to modern collision strategies.
The dynamic-programming measure of string similarity defined by Vladimir Levenshtein in 1965, and its uses in spell check, DNA, and diff tools.
From flat tables to hierarchical directories, journaling, and copy-on-write, and what each design was built to protect against.
For most of history, encryption meant two people sharing one secret key, which raised an awkward question: how do you share the key safely in the first place? A breakthrough in the 1970s solved it, and that solution quietly makes the modern internet possible.
Git feels confusing because most people learn the commands before the model. Underneath the commands is a small, elegant content-addressed database, and once you see it the whole tool clicks into place.
A container is not a tiny virtual machine. It is an ordinary Linux process wearing a disguise built from a few kernel features. Once you see the disguise for what it is, the whole model stops being magic, and its security model stops being mysterious.
The 1977 string-matching algorithm that never backtracks in the text, how its failure function works, and the story of its three independent inventors.
From batch processing and time-sharing to the three families that survived, and the ideas each generation left behind.
Computing the smallest enclosing polygon of a point set, from Graham's 1972 scan to Jarvis's march, and its uses in graphics and collision detection.
Robert Floyd's constant-space method for finding loops in sequences and linked lists, how the two-pointer trick works, and where it is applied.
Peter Fenwick's 1994 structure for cumulative frequency tables, and how a clever use of binary representation yields compact range sums.
Why does 0.1 plus 0.2 come out as 0.30000000000000004? The answer is not a bug. It is a direct, predictable consequence of how computers store numbers, and knowing it will save you from a whole class of quiet mistakes.
The distance between the code you write and the instructions a processor runs is enormous. A compiler crosses it through a pipeline of small translations, each one a little closer to the hardware. Here is what happens at every stage, including the two steps everyone forgets.
The structure that finds all intervals overlapping a point or range, its basis in computational geometry, and its use in scheduling and genomics.
The space-efficient probabilistic set that allows false positives but never false negatives, created by Burton Bloom in 1970, and where it is used.
The ancient method for finding prime numbers attributed to Eratosthenes, its efficiency, and the modern segmented and wheel variants.
A comprehensive, chronological history of the theory of computation, from the foundational mathematical questions of the early 20th century to the development of Alan Turing's formal model of computation and the subsequent rise of complexity theory and its impact on modern computing.
The elementary quadratic sorts taught first everywhere, their tangled early naming, and why simple algorithms still matter for small inputs.
From Grace Hopper's A-0 and FORTRAN to optimizing compilers and LLVM, and the shift from craft to infrastructure.
Finding cycles and clusters in directed graphs, from Tarjan's 1972 single-pass algorithm to Kosaraju's two-pass method, and their applications.
Space-partitioning trees for images and 3D scenes, from Finkel and Bentley's 1974 quadtree to octrees in graphics and collision detection.
Two greedy methods for minimum spanning trees, their rediscovery history back to Boruvka in 1926, and their uses in network design.
From Xerox PARC's desktop metaphor to the Macintosh and Windows and on to touch and voice, and the ideas reinvented along the way.
From vector displays and the first rendered frames through the rasterization and ray-tracing arc to real-time photorealism.