Introduction to Algorithms¶
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press.
Cited by¶
25 citations across 25 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
- Not `complexity_time_space`. Algorithmic complexity is one application of asymptotic reasoning (growth-class classification of cost in input size)
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)).
- Not `complexity_time_space`. Algorithmic complexity is one application of asymptotic reasoning (growth-class classification of cost in input size)
- 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) — supports markers 214, 216, 222.
- 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
- The method's signature contribution is transforming exponential-time naive recursion into polynomial-time algorithms by caching subproblem solutions.
This sourceDefinitive algorithms textbook: develops the DP workflow (recurrence, base cases, top-down memoization vs bottom-up tabulation, traceback, subproblem graph) and the exponential→polynomial transformation by caching
- The method's signature contribution is transforming exponential-time naive recursion into polynomial-time algorithms by caching subproblem solutions.
- 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.
Mechanisms¶
- 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.
- 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
Verification¶
This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. 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