Reference shelf

Glossary

Every load-bearing term from the 25 lessons, crisply defined.

Written by Claude Opus 4.8

Every load-bearing term from the 25 lessons, defined crisply. Filter to find one fast, or skim it end to end to see how the pieces connect.

Adaptive sort: A sort that runs faster on already-ordered or nearly-ordered input. Insertion sort and early-exit bubble sort are adaptive; selection sort is not.
Adjacency list: A graph stored as one list of neighbors per vertex. Compact for sparse graphs and fast to iterate a vertex's edges, which is why traversal uses it.
Adjacency matrix: A graph stored as a V by V grid where cell (i, j) marks whether an edge runs from i to j. Constant-time edge lookup, but O(V squared) space.
Algorithm: A finite, precise sequence of mechanical steps that turns an input into the intended output. It must be unambiguous and terminate.
Amortized analysis: Averaging the cost of an operation over a long run rather than judging its worst single call. A dynamic-array append is O(n) when it grows but O(1) amortized.
Array: A block of equal-size elements laid out contiguously in memory, so element i lives at a fixed offset from the start and is read in O(1).
AVL tree: A self-balancing BST that keeps the heights of a node's two subtrees within one of each other, rotating on insert and delete to hold O(log n) height.
B-tree: A balanced search tree where each node holds many keys and has many children, keeping height tiny. Shallow and block-friendly, so databases and filesystems use it.
Backtracking: Systematic search that builds a candidate one choice at a time and undoes the last choice when it cannot lead to a solution: choose, explore, un-choose.
Base case: The smallest input a recursive function answers directly, without recursing. Without one, the recursion never stops and the call stack overflows.
Bellman-Ford: A shortest-path algorithm that relaxes every edge V minus 1 times. Slower than Dijkstra at O(VE), but it handles negative edge weights and detects negative cycles.
BFS: Breadth-first search. Explore a graph level by level from the start using a queue, so the first time you reach a vertex is by a fewest-edges path.
Big-O notation: An upper bound on how an algorithm's cost grows with input size n, keeping only the dominant term and dropping constants. It names the growth class, not the exact count.
Binary heap: A complete binary tree obeying the heap property, stored implicitly in an array. It gives O(log n) insert and extract-min and backs the priority queue.
Binary search: Finding a target in a sorted sequence by repeatedly halving the range: compare the middle, then discard the half that cannot contain the answer. O(log n).
Binary search tree: A binary tree where every left descendant is smaller than a node and every right descendant is larger, so an ordered search follows one root-to-leaf path.
Binary tree: A tree in which each node has at most two children, conventionally called left and right.
Bit manipulation: Operating on the individual bits of an integer with AND, OR, XOR, NOT, and shifts to test, set, clear, or toggle flags cheaply.
Bitmask: An integer used as a row of on/off flags, one per bit, so a whole set of booleans (or a subset of up to 64 items) fits in a single machine word.
Cache locality: The payoff from touching memory that sits close together: fetching one element drags neighboring bytes into a fast cache line, so a linear array walk mostly hits cache.
Call stack: The stack of frames the runtime keeps for in-progress function calls. Each call pushes a frame; returning pops it. Deep recursion can overflow it.
Certificate: A proposed solution to a decision problem that a verifier can check quickly. The defining feature of NP is that a yes-answer has a certificate checkable in polynomial time.
Chaining: Collision handling that hangs a small linked list off each hash bucket, so colliding keys simply join the chain. Simple and degrades gracefully under load.
Circular buffer: A fixed-size array used as a ring, with head and tail indices that wrap around modulo the length. It implements a queue in O(1) with no shifting.
Collision: When two different keys hash to the same bucket. Survivable as long as no single bucket collects too many keys.
Comparison sort: A sort that orders elements only by comparing pairs of them. No comparison sort can beat O(n log n) in the worst case.
Complete binary tree: A binary tree filled level by level, left to right, with only the last level possibly unfilled. This shape lets a heap live in an array with no gaps.
Computational thinking: Breaking a messy problem into precise, mechanical sub-steps that a machine could follow without judgment.
Connected component: A maximal set of vertices that can all reach one another. One BFS or DFS from an unvisited vertex discovers exactly one component.
Contiguous memory: Storage laid out in one unbroken run of addresses. It is what gives arrays O(1) indexing and strong cache locality.
Cut property: For any way of splitting the vertices into two sides, the cheapest edge crossing the split is safe to add to a minimum spanning tree. It is why Prim's and Kruskal's work.
Cycle: A path in a graph that starts and ends at the same vertex without repeating an edge. Detecting cycles matters for topological sort and union-find.
DAG: A directed acyclic graph: directed edges with no cycles. Its vertices can be linearized by a topological sort, which is what makes dependency ordering possible.
Deque: A double-ended queue that supports push and pop at both the front and the back in O(1).
DFS: Depth-first search. Follow one path in a graph as far as it goes before backtracking, using recursion or an explicit stack. Good for connectivity, cycles, and topological order.
Dijkstra's algorithm: A shortest-path algorithm for non-negative edge weights that repeatedly settles the nearest unsettled vertex and relaxes its edges, driven by a min-heap.
Divide and conquer: Split a problem into independent smaller instances, solve each recursively, then combine the results. Merge sort and binary search are the canonical shapes.
Doubly linked list: A linked list whose nodes carry pointers to both the next and the previous node, so you can walk either direction and delete a node in O(1) given a handle to it.
Dynamic array: A resizable list (Python's list, Java's ArrayList, C++'s vector) that keeps spare capacity and, when it fills, allocates a bigger block and copies everything across.
Dynamic programming: Solving a problem by combining the answers to overlapping subproblems, each computed once and stored. It needs optimal substructure and overlapping subproblems.
Exchange argument: The standard proof that a greedy choice is safe: show any optimal solution can be transformed, one swap at a time, into the greedy one without getting worse.
Failure function: The table KMP precomputes over the pattern, giving for each position the length of the longest proper prefix that is also a suffix, so a mismatch skips ahead instead of re-scanning.
FIFO: First in, first out: the discipline of a queue, where the earliest element added is the first removed.
Frontier: The set of discovered-but-not-yet-explored vertices in a graph traversal. A queue frontier gives BFS; a stack frontier gives DFS.
Greedy algorithm: An algorithm that builds a solution by always taking the choice that looks best right now and never reconsidering. Correct only when the problem has the greedy-choice property.
Greedy-choice property: The condition that a locally optimal choice is part of some globally optimal solution, so committing to it never rules out the best answer.
Hash function: A function that chews on the raw bytes of a key and returns an integer, folded down to an array index. It must be deterministic, fast, and spread keys uniformly.
Hash map: A hash table that stores a value alongside each key and answers 'what is x mapped to?' - Python's dict, Java's HashMap.
Hash set: A hash table that stores only keys and answers 'is x present?' - Python's set, Java's HashSet.
Hash table: A structure that uses a hash function to place each key in an array bucket, giving average O(1) insert, lookup, and delete.
Heap property: The rule that every node is less than or equal to its children (a min-heap) or greater than or equal to them (a max-heap), so the extreme value always sits at the root.
Heapsort: An in-place O(n log n) sort that builds a heap from the array, then repeatedly extracts the max to the end. Not stable, but needs no extra memory.
Height: The number of edges on the longest root-to-leaf path in a tree. Every search-tree operation costs O(height), which is why balancing keeps it near log n.
In-place: An algorithm that uses O(1) extra memory beyond its input (plus the recursion stack), mutating the input rather than allocating a copy.
Insertion sort: A simple O(n squared) sort that grows a sorted prefix by inserting each next element into its place. Stable, in-place, and adaptive, so it is fast on nearly-sorted data.
Invariant: A condition that stays true at every step of an algorithm. Naming the loop invariant (for example, the target always lies within [lo, hi]) is how you reason about correctness.
Inverse Ackermann function: A function, written alpha(n), that grows so slowly it is below 5 for any n you will ever meet. Union-find with both optimizations runs in O(alpha(n)) amortized, effectively constant.
KMP: The Knuth-Morris-Pratt string search. Using a precomputed failure function, it scans the text once without ever backing up, matching a pattern in O(n + m).
LIFO: Last in, first out: the discipline of a stack, where the most recently added element is the first removed.
Linked list: A sequence of scattered nodes, each holding a value and a pointer to the next. Order lives in the pointers, not in memory layout, so there is no O(1) indexing.
Load factor: The ratio of stored keys to buckets in a hash table. As it climbs, collisions rise and operations slow, which is why the table resizes past a threshold.
Master Theorem: A formula that reads off the running time of a divide-and-conquer recurrence T(n) = a T(n/b) + f(n) by comparing the work per level against the number of leaves.
Memoization: Top-down dynamic programming: run the natural recursion but cache each subproblem's answer the first time it is computed, so repeats are free.
Merge sort: A stable divide-and-conquer sort that splits the array in half, sorts each half, and merges them. Always O(n log n), but needs O(n) scratch space.
Minimum spanning tree: A subset of a connected weighted graph's edges that links every vertex with no cycle and the least total weight. Kruskal's and Prim's both build one.
Node: One unit of a linked structure: a value plus one or more pointers to other nodes. In a tree or graph, a node is a vertex.
NP: The class of decision problems whose yes-answers can be verified in polynomial time given a certificate, even if finding the answer may be hard.
NP-complete: The hardest problems in NP: every problem in NP reduces to them in polynomial time, so a fast algorithm for one would solve them all. SAT was the first proven such.
NP-hard: At least as hard as every problem in NP. NP-hard problems need not be in NP themselves and need not even be decision problems.
Open addressing: Collision handling that keeps one key per bucket; on a clash it probes onward to the next empty slot. More cache-friendly than chaining since everything lives in one array.
Optimal substructure: The property that an optimal solution is built from optimal solutions to its subproblems. It is one of the two conditions a problem needs for dynamic programming.
Overlapping subproblems: When the same subproblem is solved again and again by a naive recursion. Caching those repeats is exactly what dynamic programming exploits.
P: The class of decision problems solvable in polynomial time. Informally, the problems we consider efficiently solvable.
Path compression: A union-find optimization that, during a find, re-points every node on the path straight to the root, flattening the tree so future finds are quicker.
Pivot: The element quicksort partitions around: values smaller go left, larger go right. A bad pivot on sorted input causes the O(n squared) worst case.
Pointer: A value that holds the memory address of another node or object. Following a pointer moves you to that location.
Prefix: A leading run of characters of a string. Tries index by shared prefixes, which is what makes prefix queries and autocomplete fast.
Priority queue: An abstract queue that always removes the highest-priority element next rather than the oldest. A binary heap is the usual O(log n) implementation.
Pruning: Cutting off a branch of a backtracking search the moment it cannot lead to a valid or better solution, so the exponential tree of choices shrinks dramatically.
Quicksort: A divide-and-conquer sort that partitions around a pivot and recurses on each side. Averages O(n log n) in-place, but degrades to O(n squared) on a bad pivot.
Rabin-Karp: A string search that compares a rolling hash of the pattern against each text window, verifying only on a hash match. O(n + m) on average, O(nm) worst case.
Random access: Reading any element in constant time from its index, without walking the ones before it. Arrays have it; linked lists do not.
Recurrence relation: An equation that defines a running time in terms of itself on smaller inputs, such as T(n) = 2 T(n/2) + n for merge sort. The Master Theorem solves the common shapes.
Recursion: A function defined in terms of itself on smaller inputs, bottoming out at one or more base cases. Each call gets its own frame on the call stack.
Red-black tree: A self-balancing BST that colors nodes red or black and enforces color rules on insert and delete to keep height within 2 log n. The workhorse behind many library maps.
Reduction: Transforming one problem into another so that a solver for the second solves the first. Polynomial-time reductions are how NP-completeness is proven and spread.
Relaxation: The core update in shortest-path algorithms: if reaching v through u is cheaper than v's current best distance, lower it and record u as the predecessor.
Rolling hash: A hash of a fixed-width window that updates in O(1) as the window slides, subtracting the character that leaves and adding the one that enters. It powers Rabin-Karp.
Rotation: A local, O(1) rearrangement of three tree nodes that shortens one side and lengthens the other while preserving the BST ordering. Balanced trees rotate to restore height.
Selection sort: An O(n squared) sort that repeatedly finds the minimum of the unsorted part and swaps it into place. In-place but not stable and not adaptive.
Self-balancing tree: A search tree that does a small fix-up after each insert and delete so its height can never drift far from log n, guaranteeing O(log n) operations on any input order.
Sentinel: A permanent, value-less dummy node placed before the real head of a list. It gives every real node a predecessor, so one code path handles every position.
Sift down: Restoring the heap property by swapping a too-large node with its smaller child, repeatedly, until it settles. Used by extract-min and to build a heap.
Sift up: Restoring the heap property after an insert by swapping a node with its parent, repeatedly, until the parent is smaller. Also called bubble up.
Sliding window: A two-pointer technique that maintains a contiguous window over an array or string, expanding and contracting it to track a best or valid subrange in one pass.
Space complexity: How the extra memory an algorithm needs grows with input size, expressed in Big-O and measured beyond the input itself.
Stable sort: A sort that keeps equal keys in their original relative order. It matters when you sort by one field after having sorted by another.
Stack: A last-in-first-out collection with push and pop at one end only. It backs the call stack, expression evaluation, and DFS.
Stack frame: The block of memory a single function call owns on the call stack, holding its parameters, locals, and return address. It is pushed on call and popped on return.
Stack overflow: The crash that happens when recursion (or any nesting) pushes more frames than the call stack can hold.
Time complexity: How the number of basic operations an algorithm performs grows with input size, expressed in Big-O.
Topological sort: A linear ordering of a DAG's vertices in which every edge points forward, so no task comes before something it depends on. Found by DFS post-order or Kahn's algorithm.
Traversal: Visiting every node of a tree or graph in a defined order. Binary-tree orders are in-order, pre-order, and post-order; in-order on a BST yields sorted keys.
Trie: A tree keyed by characters, one edge per character, where a word is a root-to-node path marked by an end-of-word flag. Search and insert cost O(key length).
Two pointers: Scanning with two indices that move under a rule (toward each other, or one chasing the other) to solve pair-finding and partition problems in one linear pass.
Union by rank: A union-find optimization that always hangs the shorter tree under the taller one's root, keeping trees flat so finds stay fast.
Union-find: A disjoint-set structure that tracks a partition under two operations, find (which set is x in?) and union (merge two sets), both near-constant with the right optimizations.
Vertex: A node of a graph. Edges connect vertices; the count of vertices is written V and of edges E in complexity bounds.
Weighted graph: A graph whose edges carry numeric costs, so path length means total weight rather than edge count. Shortest-path algorithms like Dijkstra operate on these.
XOR: The exclusive-or bit operation, 1 when its two bits differ. It toggles bits, swaps without a temporary, and cancels duplicates, since x XOR x is 0.