Computer Science & Algorithms

Abstraction

Edsger Dijkstra

Hide complexity behind simpler interfaces to reason at higher levels.

Explore-exploit Tradeoff

Balance gathering new information against leveraging what you already know.

Metcalfe's Law

Robert Metcalfe / George Gilder

Network value grows proportionally to the square of connected users.

Moore's Law

Gordon Moore / Carver Mead

Transistor counts double every two years, driving exponential computing gains.

Mythical Man Month

Frederick P. Brooks Jr.

Adding people to a late project makes it later.

Technical Debt

Ward Cunningham

Expedient decisions create compounding costs that must be repaid.

Black Box

A black box is a system whose internal workings are hidden or irrelevant: you observe inputs and outputs, not mechanism. The term comes from control theory and systems...

Clarke's Third Law

Arthur C. Clarke

Arthur C. Clarke's third law: "Any sufficiently advanced technology is indistinguishable from magic." The line appears in his 1973 revision of Profiles of the Future. The point is...

Constraint Relaxation

Constraint relaxation is a problem-solving move: temporarily drop or loosen a constraint to make a hard problem tractable, then reintroduce the constraint and adapt the solution....

Design Pattern

Gamma / Helm / Johnson / Vlissides

A design pattern is a reusable solution to a recurring problem in a context. The term was popularised in software by the Gang of Four (Design Patterns: Elements of Reusable...

Divide and Conquer

Divide and conquer is a strategy: break a problem into smaller subproblems of the same kind, solve them (often recursively), then combine the solutions. In algorithms, merge sort...

Exponential Backoff

Exponential backoff is a retry strategy: after a failure, wait before retrying, and increase the wait each time — often doubling it (1s, 2s, 4s, 8s, …) until a cap or success. The...

Filter Bubble

Eli Pariser

A filter bubble is an information environment shaped by algorithms (and choices) so that you see more of what you already prefer or believe and less of what would challenge or...

Information Cascade

Bikhchandani / Hirshleifer / Welch

An information cascade occurs when people abandon their private signal and copy the observed actions of others, so that later actors learn nothing from the choices of those before...

Look-Then-Leap Rule

The look-then-leap rule is an optimal stopping strategy: spend a defined phase gathering information (look), then commit when a threshold is reached (leap). It comes from the...

Mechanism Design

Leonid Hurwicz / Eric Maskin / Roger Myerson

Mechanism design is the reverse of game theory: instead of analysing the outcome of given rules, you choose the rules so that self-interested participants are led to an outcome...

Moravec's Paradox

Hans Moravec / Marvin Minsky

Moravec's paradox is the observation that the hard problems for humans are often easy for machines, and the easy problems for humans are often hard for machines. Reasoning,...

Parallel Processing

Parallel processing is doing multiple units of work at the same time instead of one after the other. In computing, it means executing instructions or tasks concurrently across...

Recursion

Recursion is when a process or structure is defined in terms of itself: a function calls itself, a structure contains a smaller instance of the same structure, or a problem is...

Average Rule

When multiple independent estimates or signals bear on the same quantity, combining them (e.g. by averaging) often beats relying on one. The average rule is a decision heuristic:...

Belady's Algorithm

Belady

Belady's algorithm (MIN or OPT) is the optimal offline page-replacement policy for a cache: evict the page that will be used farthest in the future. It minimizes cache misses when...

Binary Search

Binary search finds a target in a sorted sequence by repeatedly halving the search space: compare to the middle element, then search only the half that can contain the answer....

Godwin's Law

Mike Godwin

Godwin's Law: "As an online discussion grows longer, the probability of a comparison involving Nazis or Hitler approaches 1." It's a meta-observation about discourse decay —...

Interrupt Coalescing

Interrupt coalescing batches multiple interrupt triggers into a single handling event. Instead of the CPU switching context on every interrupt, the system waits briefly or until a...

Lagrangian Relaxation

Lagrangian relaxation turns a hard constrained problem into a sequence of easier ones: move constraints into the objective with penalty multipliers (Lagrange multipliers), then...

Laplace's Law

Pierre-Simon Laplace

Laplace's rule (or rule of succession) estimates the probability of an event that has occurred k times in n trials as (k + 1) / (n + 2). It's a simple Bayesian prior: start from...

Least Recently Used

LRU (Least Recently Used) is a cache eviction policy: when the cache is full, evict the item that was used longest ago. It assumes temporal locality—recently used items are more...

Multiplicative Rule

The multiplicative rule says that for independent events, the probability of all occurring is the product of their individual probabilities. If each step in a chain has 90%...

Optimization Algorithms

Optimization algorithms search for the best solution in a space of possibilities: maximise reward or minimise cost. Greedy methods (e.g. hill climbing) move toward better...

Packet Switching

Packet switching sends data in small, discrete packets that can be routed independently across a shared network. Unlike circuit switching (dedicated path for the whole session),...

Scheduling & Prioritization

Scheduling and prioritisation algorithms determine the order in which tasks are processed when resources are limited. Key heuristics: Earliest Due Date (EDD) minimises maximum...

Sorting Algorithms

Sorting puts a sequence in order (e.g. by value or key). Different algorithms trade off time, space, and stability. Comparison-based sorts (e.g. merge sort, quicksort) use only...

Statistical Learning

Statistical learning is the framework for learning from data: choose a model class, define loss, and fit by minimising empirical risk (e.g. squared error, cross-entropy). Core...

The Copernican Principle

The Copernican principle says: don't assume a privileged position. We're not at a special time or place in the universe—or in a distribution. Applied to duration: if you have no...

The Gittens Index

John Gittins

The Gittins index assigns a single number to each arm in a multi-armed bandit problem (with geometric discounting): it's the value of playing that arm optimally versus a fixed...

Threshold Rule

A threshold rule is a decision rule that triggers an action when a quantity crosses a level: "if x ≥ T, do A; else do B." It turns a continuous or noisy signal into a discrete...

Upper Confidence Bound

UCB (Upper Confidence Bound) is a simple policy for the multi-armed bandit: for each arm, compute an index = estimated mean + confidence bound (e.g. proportional to √(log n /...

Zawinski's Law

Jamie Zawinski

Zawinski's law (Jamie Zawinski, Netscape/Mozilla): "Every program attempts to expand until it can read mail. Those programs which cannot so expand are replaced by ones that can."...