Entscheidungsproblem
Hilbert's decision problem, which asked for an algorithm to decide whether any logical statement is provable; Church and Turing proved in 1936 that none exists.
Concepts
Plain-language explanations of the ideas behind software - compilers, garbage collection, objects, types.
628 entries, all primary-sourced
Modem
A modulator-demodulator carries digital data over analog telephone lines by encoding bits as audio tones; the Bell 103 of the early 1960s ran at 300 bits per second and seeded the dial-up era.
Packet Switching
A method of data communication that breaks messages into small, independently routed packets, conceived independently by Paul Baran at RAND and Donald Davies at the NPL in the early to mid 1960s.
Bresenham's Line Algorithm
Jack Bresenham's integer-only method for drawing straight lines on raster displays and digital plotters, using an incremental error term to choose the nearest pixel without multiplication or division.
Pixel
The pixel, short for picture element, is the smallest addressable sample of a digital image; the word was first published in 1965 by Fred Billingsley of NASA's Jet Propulsion Laboratory.
The Software Crisis
The late-1960s recognition that software projects routinely ran over budget and schedule and shipped buggy, hard-to-maintain code.
Software Engineering
The disciplined application of engineering principles to designing, building, testing, and maintaining software.
Request for Comments (RFC)
The Request for Comments series is the internet's open line of technical documents, running unbroken since 1969, in which protocols are proposed, discussed, and standardized.
A* Search
A 1968 best-first graph search that finds least-cost paths using a heuristic to guide exploration, and is optimal when that heuristic never overestimates.
ACID
Atomicity, Consistency, Isolation, Durability - the four guarantees a reliable transaction provides, with the acronym coined by Haerder and Reuter in 1983.
ACM A.M. Turing Award
The ACM's most prestigious technical award, first given in 1966 and widely called the Nobel Prize of Computing, recognizing major contributions of lasting importance to computer science.
Agile Software Development
An iterative, incremental approach to building software that values working software, customer collaboration, and responding to change over heavy up-front planning.
AJAX
A technique for updating part of a web page by fetching data in the background without a full page reload, the approach behind early dynamic applications like Gmail and Google Maps.
Algebraic Data Type
A composite type built by combining other types, either as a sum (a value is one of several variants) or a product (a record of several fields).
Algorithm
A finite, well-defined sequence of steps that solves a problem or computes a result, and the central object of study in computer science.
Algorithm Analysis
Determining how much time and space an algorithm uses as a function of its input size, so algorithms can be compared independently of hardware.
Amortized Analysis
A way of analyzing the average cost of an operation over a whole sequence, so that occasional expensive operations are paid for by many cheap ones.
API Gateway
A single entry point in front of a set of backend services that routes, authenticates, rate-limits, and aggregates calls on behalf of clients.
API Key
A simple shared secret string that identifies and authenticates the caller of an API, easy to use but with weaker guarantees than delegated authorization such as OAuth.
API Pagination
Returning a large collection in bounded pages rather than all at once; offset/limit is simple but degrades on large datasets, while cursor (keyset) pagination scales by remembering a stable position instead of a page number.
API-First Design
A methodology in which the API's interface contract is designed and agreed before the backing service is built, often expressed in a machine-readable specification such as OpenAPI.
Array
A contiguous block of memory holding fixed-size elements indexed by position, giving constant-time access to any element.
Artifact Repository
An artifact repository is a server that stores and serves built software packages so that build tools can fetch dependencies by name and version.
Automata Theory
The study of abstract machines and the classes of languages and problems each kind of machine can recognize, forming a ladder of computational power from finite automata up to Turing machines.
B-tree
A balanced, disk-friendly tree that keeps keys sorted and supports search, insert, and delete in logarithmic time - the index structure under almost every database and filesystem.
Backend for Frontend
An architectural pattern, named by Sam Newman in 2015, in which each user-facing client type gets its own tailored backend instead of sharing one general-purpose API.
Backend-as-a-Service (BaaS)
Ready-made cloud backends - authentication, databases, storage, push messaging - that let front-end developers ship apps without building and running a server tier, as with Firebase, Supabase, and Parse.
Backtracking
A search technique that builds candidate solutions one piece at a time and abandons a partial candidate as soon as it cannot possibly be completed into a valid solution.
Batch vs Stream Processing
The distinction between processing data in large bounded chunks on a schedule versus continuously as it arrives - a central axis of modern data architecture.
Berkeley RISC Project
David Patterson's early-1980s UC Berkeley project that designed and built the RISC-I and RISC-II VLSI processors, pioneered register windows, and seeded the SPARC architecture.
Big-O Notation
The notation (O, Omega, Theta) for describing how an algorithm's running time or memory grows with input size while ignoring constant factors.
Bikeshedding
The tendency of a group to spend disproportionate time arguing over trivial, easy-to-grasp details while waving through hard, important decisions.
Binary Search
An algorithm that finds a target in a sorted array by repeatedly halving the search range, running in O(log n) time.
Binary Search Tree
A binary tree that keeps every node greater than its left subtree and less than its right subtree, giving fast search when balanced.
Binary Tree
A tree data structure in which every node has at most two children, used as the basis for search trees, heaps, and expression trees.
Blameless Postmortem
A written incident analysis that focuses on the systemic reasons a failure happened rather than on punishing individuals, so that people report problems honestly and the organization fixes systems instead of blaming people.
Bloom Filter
A space-efficient probabilistic data structure (Bloom, 1970) that tests set membership with possible false positives but no false negatives.
Boolean Algebra
The algebra of two values (true/false, 1/0) with AND, OR, and NOT; Boole's 1854 system that Claude Shannon applied to switching circuits, making it the foundation of digital logic.
Branch Prediction
Guessing the outcome of a conditional branch before it is resolved, so a pipelined processor can keep fetching and executing instructions instead of stalling; studied systematically in J.E. Smith's 1981 paper.
Branching and Merging
Creating independent lines of development called branches, then later combining them back together by merging, so that teams can work in parallel without overwriting each other.
Breadth-First Search
A graph traversal that explores level by level using a queue, visiting all neighbors before going deeper, and finding shortest paths in unweighted graphs in O(V+E) time.
Brooks's Law
Fred Brooks's observation that adding people to a late software project tends to make it later, because of training time and the communication overhead that grows with team size.
Bubble Sort
A simple O(n^2) sorting algorithm that repeatedly swaps adjacent out-of-order elements, valued for teaching rather than performance.
Buffer Overflow
Writing more data into a fixed-size memory buffer than it can hold, overwriting adjacent memory and, in C and C++, potentially letting an attacker run arbitrary code.
Build Automation
Automating the steps that turn source code into a runnable artifact, so builds are repeatable instead of done by hand.
Build System
A build system is the tool and rules that orchestrate compiling and assembling software from its sources and dependencies, turning a one-off compile into a repeatable, defined process.
Build vs Runtime Dependency
The distinction between dependencies needed only to compile software and those needed when it runs; package managers track the two separately.
Bytecode
A compact, portable instruction set aimed at a virtual machine rather than a physical CPU, used by systems such as the Java Virtual Machine and Python.