Introduction to Algorithms¶
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press.
Cited by¶
32 citations across 32 artifacts.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Algorithm
- Cormen-Leiserson-Rivest-Stein (2009) defined an algorithm as any well-defined computational procedure that takes input and produces output
This sourceDefines an algorithm as 'any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output'
- Cormen-Leiserson-Rivest-Stein (2009) defined an algorithm as any well-defined computational procedure that takes input and produces output
- Asymptotic Behavior
- Take two algorithms: insertion sort, whose worst-case comparison count grows like \(\tfrac{1}{2}n^2 - \tfrac{1}{2}n\), and merge sort, growing like \(n\log_2 n\).
This sourceStandard reference defining asymptotic (big-O/Θ) growth-class analysis and giving the comparison cost of insertion sort (Θ(n²)) versus merge sort (Θ(n log n)).
- Take two algorithms: insertion sort, whose worst-case comparison count grows like \(\tfrac{1}{2}n^2 - \tfrac{1}{2}n\), and merge sort, growing like \(n\log_2 n\).
- Birthday Problem
- Boundedness
- Computer science encounters boundedness in essentially every subfield, as Cormen, Leiserson, Rivest, and Stein (2009) systematise in their canonical treatment of resource-bounded algorithm analysis.
This sourcesystematizes asymptotic resource bounds and resource-bounded computation (time/space complexity classes, NP-completeness).
- Computer science encounters boundedness in essentially every subfield, as Cormen, Leiserson, Rivest, and Stein (2009) systematise in their canonical treatment of resource-bounded algorithm analysis.
- Complexity (Time/Space)
- The resource metric (time, space, communication, parallel work, or hybrid cost function)
This sourceStandard reference (CLRS) for resource metrics, problem-size parameters, growth-rate analysis of sorting/searching/graph algorithms, the comparison-sort Ω(n log n) bound, and data-structure selection — supports D30-138, D30-139, D30-143, D30-145, D30-147. Verified existing and supporting.
- The resource metric (time, space, communication, parallel work, or hybrid cost function)
- Connectedness
- Consider an undirected graph \(G\) on eight vertices with edges \(\{1\text{-}2, 2\text{-}3, 3\text{-}1, 3\text{-}4, 5\text{-}6, 6\text{-}7\}\) and an isolated vertex $8$.
This sourceBreadth-first search and connected-components algorithms computing the reachability partition of a graph in linear time.
- Consider an undirected graph \(G\) on eight vertices with edges \(\{1\text{-}2, 2\text{-}3, 3\text{-}1, 3\text{-}4, 5\text{-}6, 6\text{-}7\}\) and an isolated vertex $8$.
- Data Structure
- The prime travels because the diagnostic question which operations is this arrangement optimized for? is the same across substrates, even though the term and much of its vocabulary are computer-science in origin and carry a mild engineering-and-organizing frame.
This sourceStandard reference establishing the operation-cost profiles of arrays, hash tables, balanced search trees, and heaps, and the space-for-time trade-offs of indexing and composition.
- The prime travels because the diagnostic question which operations is this arrangement optimized for? is the same across substrates, even though the term and much of its vocabulary are computer-science in origin and carry a mild engineering-and-organizing frame.
- Dependency
- A graph of dependencies produces architecture: layered, modular, hierarchical, or cyclic, with topological sort — formalized in Cormen, Leiserson, Rivest, and Stein's (2009) treatment of directed acyclic graphs — providing the canonical algorithm for linearizing the compositional structure.
This sourceChapter 22 develops topological sort, depth-first search, and reachability over directed acyclic graphs as the algorithmic vocabulary for dependency-graph analysis (transitive closure, cycle detection, critical-path computation)
- A graph of dependencies produces architecture: layered, modular, hierarchical, or cyclic, with topological sort — formalized in Cormen, Leiserson, Rivest, and Stein's (2009) treatment of directed acyclic graphs — providing the canonical algorithm for linearizing the compositional structure.
- Directed Acyclic Graph
- It licenses topological sort — a linear ordering consistent with every arrow — well-founded induction — guaranteed base cases from which to build — and terminating dependency resolution — the assurance that leaves can always be evaluated first and the rest in order.
This sourceTopological sort, well-founded reasoning over DAGs, and the tree-versus-DAG distinction.
- It licenses topological sort — a linear ordering consistent with every arrow — well-founded induction — guaranteed base cases from which to build — and terminating dependency resolution — the assurance that leaves can always be evaluated first and the rest in order.
- Dynamic Programming
- Greedy Algorithm
- In computer science it is minimum spanning trees (provably optimal by matroid structure), Huffman codes, Dijkstra's algorithm, interval scheduling, and greedy set cover (a logarithmic-factor approximation, not exact).
This sourceStandard text presenting greedy algorithms — minimum spanning trees (Kruskal/Prim), Huffman coding, Dijkstra's algorithm, interval scheduling, and greedy set cover — with their optimality conditions and approximation bounds.
- In computer science it is minimum spanning trees (provably optimal by matroid structure), Huffman codes, Dijkstra's algorithm, interval scheduling, and greedy set cover (a logarithmic-factor approximation, not exact).
- Injectivity
- In computer science it is primary keys and UNIQUE constraints, bijective and prefix-free encodings, lossless compression as invertible coding, block ciphers as per-key bijections, and URL canonicalization that keeps distinct URLs distinct.
This sourceStandard text covering keys, lossless/invertible coding, and hashing versus collision-free mappings.
- In computer science it is primary keys and UNIQUE constraints, bijective and prefix-free encodings, lossless compression as invertible coding, block ciphers as per-key bijections, and URL canonicalization that keeps distinct URLs distinct.
- Inverted Pyramid
- The structure can be made nearly algorithmic: given a content set and a prefix-length distribution, the optimal prefix is the importance-ranked top-k for the lowest-bandwidth reader, which is why the inverted pyramid is close kin to a priority queue (pop most-important-first) and to importance-weighted summarization (a summary is approximately the prefix of an importance-ordered set).
This sourceStandard reference for the priority queue (extract-max / pop-most-important-first) abstract data structure, the algorithmic analogue of the importance-ordered prefix.
- The structure can be made nearly algorithmic: given a content set and a prefix-length distribution, the optimal prefix is the importance-ranked top-k for the lowest-bandwidth reader, which is why the inverted pyramid is close kin to a priority queue (pop most-important-first) and to importance-weighted summarization (a summary is approximately the prefix of an importance-ordered set).
- Iteration
- Minimax Strategy
- In computer science, worst-case complexity is exactly minimax over inputs, game-tree search uses the minimax algorithm with pruning, and online algorithms are graded by competitive ratio — minimax against an adversarial input sequence.
This sourceTreats worst-case complexity (minimax over inputs), minimax game-tree search with alpha-beta pruning, and competitive ratio of online algorithms.
- In computer science, worst-case complexity is exactly minimax over inputs, game-tree search uses the minimax algorithm with pruning, and online algorithms are graded by competitive ratio — minimax against an adversarial input sequence.
- Neighborhood
- In computing caches and prefetchers exploit temporal and spatial neighborhoods of recently accessed addresses, k-nearest-neighbour classifiers and spatial indexes are neighborhood machinery, convolutional networks process receptive-field neighborhoods, and graph algorithms propagate information through k-hop neighborhoods.
This sourceStandard reference covering nearest-neighbor methods, spatial indexes, and graph algorithms that propagate information through k-hop neighborhoods.
- In computing caches and prefetchers exploit temporal and spatial neighborhoods of recently accessed addresses, k-nearest-neighbour classifiers and spatial indexes are neighborhood machinery, convolutional networks process receptive-field neighborhoods, and graph algorithms propagate information through k-hop neighborhoods.
- Network Flow Models
- (3) The practical pipeline typically involves: problem identification (recognition that a problem has network-flow structure, often with some modeling ingenuity); network construction (nodes, edges, capacities, costs, sources, sinks); algorithm selection (Ford-Fulkerson or Edmonds-Karp for max-flow; network simplex or cycle-canceling for min-cost flow; specialized algorithms for specific variants); solver execution; and solution interpretation (flow values on edges, cut structure, shadow prices/dual variables), as systematized in the Cormen-Leiserson-Rivest-Stein (2009) treatment of network-flow algorithms.
This sourceCanonical algorithms textbook: develops the systematic study of resource-bounded computation including time-bounded complexity classes (P, EXP), space-bounded classes (LOGSPACE, PSPACE), and the structural framework of asymptotic resource bounds.
- (3) The practical pipeline typically involves: problem identification (recognition that a problem has network-flow structure, often with some modeling ingenuity); network construction (nodes, edges, capacities, costs, sources, sinks); algorithm selection (Ford-Fulkerson or Edmonds-Karp for max-flow; network simplex or cycle-canceling for min-cost flow; specialized algorithms for specific variants); solver execution; and solution interpretation (flow values on edges, cut structure, shadow prices/dual variables), as systematized in the Cormen-Leiserson-Rivest-Stein (2009) treatment of network-flow algorithms.
- Partition
- In computing hash and range partitions distribute keys across shards so each row lives on exactly one node, disjoint-set structures maintain a dynamic partition under merges, and basic-block decomposition partitions a program.
This sourceCovers disjoint-set (union-find) structures maintaining a dynamic partition under merges, and hashing/partitioning of keys.
- In computing hash and range partitions distribute keys across shards so each row lives on exactly one node, disjoint-set structures maintain a dynamic partition under merges, and basic-block decomposition partitions a program.
- Path
- In graph theory it is paths, walks, cycles, and trails, with shortest-path algorithms foundational and geodesics on manifolds the continuous analogue.
This sourceStandard reference for paths, walks, cycles, and shortest-path algorithms on graphs.
- In graph theory it is paths, walks, cycles, and trails, with shortest-path algorithms foundational and geodesics on manifolds the continuous analogue.
- Problem Representation
- Mathematics and theoretical CS — change of basis in linear algebra; primal-dual reformulation; integer-versus-linear-programming relaxations; encoding NP-hard problems as SAT; spectral versus time-domain representations.
This sourceEstablishes how data-structure choice (array, hash table, balanced tree) fixes which operations are constant-, logarithmic-, or linear-time and which (e.g., range queries) are unsupported.
- Mathematics and theoretical CS — change of basis in linear algebra; primal-dual reformulation; integer-versus-linear-programming relaxations; encoding NP-hard problems as SAT; spectral versus time-domain representations.
- Recurrence
- A recursive algorithm can exhibit recurrence (the size of a subproblem at each level follows a predictable pattern), but the two are distinct concepts—Cormen, Leiserson, Rivest, and Stein (2009) keep them carefully separated when they use recurrence relations to analyze recursive algorithm runtime.
This sourceCanonical algorithms textbook: develops the systematic study of resource-bounded computation including time-bounded complexity classes (P, EXP), space-bounded classes (LOGSPACE, PSPACE), and the structural framework of asymptotic resource bounds.
- A recursive algorithm can exhibit recurrence (the size of a subproblem at each level follows a predictable pattern), but the two are distinct concepts—Cormen, Leiserson, Rivest, and Stein (2009) keep them carefully separated when they use recurrence relations to analyze recursive algorithm runtime.
- Surjectivity
- Not `coverage_reachability` (graph reachability). Reachability asks whether a target can be arrived at by following edges through a graph — a path-existence, traversal property.
This sourceGraph reachability as a path-existence/traversal property, distinct from the image of a single mapping.
- Not `coverage_reachability` (graph reachability). Reachability asks whether a target can be arrived at by following edges through a graph — a path-existence, traversal property.
- Termination Condition
- In computer science and algorithms they are loop exit conditions, recursion base cases, convergence criteria of iterative solvers, protocol timeouts, and episode stopping rules — the discipline is built on noticing that halting is structurally separate from progress.
This sourceStandard treatment of loop invariants, recursion base cases, and termination/halting arguments as distinct from correctness.
- In computer science and algorithms they are loop exit conditions, recursion base cases, convergence criteria of iterative solvers, protocol timeouts, and episode stopping rules — the discipline is built on noticing that halting is structurally separate from progress.
Domain-specific¶
- Big O Notation
- Yet the notation's deliberate discard of constants is why real libraries do not use merge sort alone: insertion sort has a tiny constant and, on very small subarrays (typically fewer than ~16-64 elements), actually runs faster
This sourceEstablishes insertion sort's small constant factor and the crossover on short subarrays, including the exercise in which insertion sort is used for the small sublists of a merge sort.
- Yet the notation's deliberate discard of constants is why real libraries do not use merge sort alone: insertion sort has a tiny constant and, on very small subarrays (typically fewer than ~16-64 elements), actually runs faster
- Heap
- Both operations complete in O(log n), where n is the heap's size, because a binary heap is a complete binary tree, whose height is ⌊log₂ n⌋
This sourceO(lg n) heap insertion and extraction, derived from the logarithmic height of the complete binary tree a heap is built on. Dijkstra's and Prim's algorithms as min-priority-queue algorithms whose extract-min costs O(lg V) with a binary heap rather than O(V) by array scan. Dijkstra's O((V + E) lg V) running time with a binary min-heap against O(V^2) with a linear-array priority queue.
SupportedVerified against the source
- Both operations complete in O(log n), where n is the heap's size, because a binary heap is a complete binary tree, whose height is ⌊log₂ n⌋
- Topological Sorting
- Depth-first-search post-order reversal processes nodes by DFS and emits each node after all its descendants have been visited, then reverses the resulting list; back edges in the DFS are the cycle witness.
This sourceThe saved CLRS snippets support DFS-based topological sorting by decreasing finishing time, but the statement that a back edge witnesses a cycle is truncated out of the text checked.
Supported in partVerified against a saved copy of the source
“This section shows how we can use depth-first search to perform a topological sort”
- Depth-first-search post-order reversal processes nodes by DFS and emits each node after all its descendants have been visited, then reverses the resulting list; back edges in the DFS are the cycle witness.
Mechanisms¶
- Adjacency List or Matrix
- Its classic failure is a dense V×V matrix for a large sparse graph, where Θ(V²) space is spent storing mostly-absent edges;
This sourceShows that adjacency matrices use Θ(V²) space while adjacency lists represent sparse graphs compactly and expose each vertex's neighbors directly.
- Its classic failure is a dense V×V matrix for a large sparse graph, where Θ(V²) space is spent storing mostly-absent edges;
- Canonical Execution Order Runbook
- - Derive the order from dependencies. Map which operations read state that others write, then linearize that dependency graph into one sequence — a topological ordering.
This sourceLinearizes a directed acyclic dependency graph so every prerequisite precedes the operation that depends on it.
- - Derive the order from dependencies. Map which operations read state that others write, then linearize that dependency graph into one sequence — a topological ordering.
- Cascade Dependency Graph
- Trace reachability on demand. Given any starting node, a forward traversal returns every node the change could eventually reach — the reachable set that bounds the worst-case blast radius.
This sourceA graph traversal from a selected source visits the vertices reachable from that source.
- Trace reachability on demand. Given any starting node, a forward traversal returns every node the change could eventually reach — the reachable set that bounds the worst-case blast radius.
- Connected-Component Scan
- Two nodes get an edge only if they satisfy the rule that matters for the real function — within range, protocol-compatible, mutually routable — and the scan then partitions the graph into maximal connected sets
This sourceUses disjoint-set operations to partition an undirected graph into its connected components.
- Two nodes get an edge only if they satisfy the rule that matters for the real function — within range, protocol-compatible, mutually routable — and the scan then partitions the graph into maximal connected sets
- Dijkstra-Style Frontier Expansion
- A single negative edge — a rebate, a credit, a "cost" that can be recovered downstream — breaks the settled-is-final invariant, and the method can return a confidently wrong answer; the fix is a different tool (Bellman–Ford, which relaxes repeatedly instead of settling greedily), not a parameter tweak.
This sourceShows that Dijkstra’s settled-vertex guarantee requires nonnegative edge weights and presents Bellman–Ford’s repeated relaxation for graphs that may contain negative edges.
- A single negative edge — a rebate, a credit, a "cost" that can be recovered downstream — breaks the settled-is-final invariant, and the method can return a confidently wrong answer; the fix is a different tool (Bellman–Ford, which relaxes repeatedly instead of settling greedily), not a parameter tweak.
- Dynamic Programming Method
- Its central failure is applying it where optimal substructure does not hold — where an optimal whole can require locally sub-optimal parts — in which case the recurrence is simply wrong and the tidy table launders a bug into a plausible number.
This sourceExplains that dynamic programming applies when a globally optimal solution can be built from optimal solutions to overlapping subproblems.
- Its central failure is applying it where optimal substructure does not hold — where an optimal whole can require locally sub-optimal parts — in which case the recurrence is simply wrong and the tidy table launders a bug into a plausible number.
Verification¶
Does it exist? Confirmed. This work's ISBN resolves to a registered record, which fixes its identity. That is all it fixes.
Does it back the claim? Read against the text for 2 of 32 citations: 1 supported, 1 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Links previously used in the corpus¶
Before the registry existed this work was also linked 1 other way.
Registry ID ref:df39008ee4f4 · see in the full table