Thomas H. Cormen,
Dartmouth College
Charles E. Leiserson,
Massachusetts Institute of Technology
Ronald L. Rivest,
Massachusetts Institute of Technology
Clifford Stein,
Columbia University
| boolean combinational element | any circuit element that has a constant number of boolean inputs and outputs and that performs a well-defined function.
(See page 987)
|
 |
|
|
| boolean function | An n-input, m-output boolean function is a function from {TRUE, FALSE}n to {TRUE, FALSE}m.
(See page 1098)
|
|
|
|
| bottleneck traveling-salesman problem | finding the hamiltonian cycle such that the cost of the most costly edge in the cycle is minimized.
(See page 1033)
|
|
|
|
| canonical form | An arbitrary schedule in which the early tasks precede the late tasks and the early tasks are scheduled in order of monotonically increasing deadlines.
(See page 399)
|
|
|
|
| capacity | The capacity of the cut (S, T) is c(S, T).
(See page 655)
|
|
|
|
| Cartesian sum | Consider two sets A and B, each having n integers in the range from 0 to 10n. The Cartesian sum is defined by C = {x + y : x ⊆ A and y ⊆ B}.
(See page 830)
|
|
|
|
| cascading-cut | x might be the second child cut from its parent y since the time that y was linked to another node. Therefore, the FIB-HEAP-DECREASE-KEY algorithm performs a cascading-cut operation on y. If y is a root, then the test in CASCADING-CUT causes the procedure to just return. If y is unmarked, the procedure marks it, since its first child has just been cut, and returns. If y is marked, however, it has just lost its second child; y is cut, and CASCADING-CUT calls itself recursively on y's parent z. The CASCADING-CUT procedure recurses its way up the tree until either a root or an unmarked node is found.
(See page 490)
|
|
|
|
| Catalan numbers | A sequence of numbers which grows as Ω(4n / n3/2).
(See page 333)
|
|
|
|
| certain event | the event S.
(See page 1100)
|
|
|
|
| child list | In a Fibonacci heap, each node x contains a pointer p[x] to its parent and a pointer child[x] to any one of its children. The children of x are linked together in a circular, doubly linked list, which we call the child list of x. Each child y in a child list has pointers left[y] and right[y] that point to y's left and right siblings, respectively. If node y is an only child, then left[y] = right[y] = y. The order in which siblings appear in a child list is arbitrary.
(See page 477)
|
|
|
|
| circuit input | If no element output is connected to a wire, the wire is a circuit input, accepting input values from an external source.
(See page 988)
|
|
|
|
| circuit output | If no element input is connected to a wire, the wire is a circuit output, providing the results of the circuit's computation to the outside world.
(See page 988)
|
|
|
|
| circuit-satisfiability problem | "Given a boolean combinational circuit composed of AND, OR, and NOT gates, is it satisfiable?"
(See page 989)
|
|
|
|
| circular, doubly linked list with a sentinel | the sentinel nil[L] is placed between the head and tail; the field next[nil[L]] points to the head of the list, and prev[nil[L]] points to the tail. Similarly, both the next field of the tail and the prev field of the head point to nil[L]. Since next[nil[L]] points to the head, we can eliminate the attribute head[L] altogether, replacing references to it by references to next[nil[L]]. An empty list consists of just the sentinel, since both next[nil[L]] and prev[nil[L]] can be set to nil[L].
(See page 206)
|
|
|
|
| circular list | In a circular list, the prev pointer of the head of the list points to the tail, and the next pointer of the tail of the list points to the head.
(See page 204)
|
|
|
|
| clean | consisting of either all 0's or all 1's.
(See page 713)
|
|
|
|
| clique | in an undirected graph G = (V, E) is a subset V′ ⊆ V of vertices, each pair of which is connected by an edge in E. In other words, a clique is a complete subgraph of G.
(See page 1003)
|
|
|
|
| clique problem | the optimization problem of finding a clique of maximum size in a graph. As a decision problem, we ask simply whether a clique of given size k exists in the graph.
(See page 1003)
|
|
|
|
| closed interval | an ordered pair of real numbers [t1, t2], with t1 ≤ t2.
(See page 311)
|
|
|
|
| closest-point heuristic | for building an approximate traveling-salesman tour. Begin with a trivial cycle consisting of a single arbitrarily chosen vertex. At each step, identify the vertex u that is not on the cycle but whose distance to any vertex on the cycle is minimum. Suppose that the vertex on the cycle that is nearest u is vertex v. Extend the cycle to include u by inserting u just after v. Repeat until all vertices are on the cycle.
(See page 1033)
|
|
|
|
| closure or Kleene star | of a language L is the language L* = {ε} ∪ L ∪ L2 ∪ L3 ∪ . . . , where Lk is the language obtained by concatenating L to itself k times.
(See page 976)
|
|
|
|
| collision | occurs when two keys hash to the same slot
(See page 224)
|
|
|
|
| column rank | of a nonzero m x n matrix A is the size of the largest set of linearly independent columns of A.
(See page 731)
|
|
|
|
| column vector | The standard form of a vector, equivalent to an n x 1 matrix.
(See page 726)
|
|
|
|
| common divisor | If d is a divisor of a and d is also a divisor of b, then d is a common divisor of a and b.
(See page 852)
|
|
|
|
| common subsequence | Given two sequences X and Y, we say that a sequence Z is a common subsequence of X and Y if Z is a subsequence of both X and Y.
(See page 351)
|
|
|
|
| commutative law | a ⊕ b = b ⊕ a for all a, b ⊆ S.
(See page 862)
|
|
|
|
| comparator | a device with two inputs, x and y, and two outputs, x' and y', that performs the following function: x' = min(x, y), y' = max(x, y).
(See page 705)
|
|
|
|
| comparison network | a set of comparators interconnected by wires.
(See page 705)
|
|
|
|
| compatible | We can multiply two matrices A and B only if they are compatible: the number of columns of A must equal the number of rows of B.
(See page 332)
|
|
|
|
| compatible activities | Activities ai and aj are compatible if the intervals [si, fi) and [sj, fj) do not overlap (i.e., ai and aj are compatible if si ≥ fj or sj ≥ fi).
(See page 371)
|
|
|
|
| complementary slackness | describes a relationship between the values of primal variables and dual constraints and between the values of dual variables and primal constraints.
(See page 818)
|
|
|
|
| complete | A language L is complete for a language class C with respect to polynomial-time reductions if L ∈ C and L′ ≤P L for all L′ ∈ C.
(See page 994)
|
|
|
|
| completion time | the time at which a task completes processing.
(See page 402)
|
|
|
|
| complexity class | Informally defined as a set of languages, membership in which is determined by a complexity measure, such as running time, of an algorithm that determines whether a given string x belongs to language L. The actual definition of a complexity class is somewhat more technical.
(See page 977)
|
|
|
|
| complexity class NP | the class of languages that can be verified by a polynomial-time algorithm. The name "NP" stands for "nondeterministic polynomial time." The class NP was originally studied in the context of nondeterminism, but this book uses the somewhat simpler yet equivalent notion of verification. A language L belongs to NP if and only if there exist a two-input polynomial-time algorithm A and constant c such that L = {x ∈ {0,1}* : there exists a certificate y with |y| = O(|x|c) such that A(x, y) = 1}. We say that algorithm A verifies language L in polynomial time.
(See page 981)
|
|
|
|
| complexity class P | The set of concrete decision problems that are polynomial-time solvable.
(See page 973)
|
|
|
|
| complex nth root of unity | a complex number ω such that ωn = 1. There are exactly n complex nth roots of unity:
e2πkk/n for k = 0, 1, . . . , n - 1.
(See page 830)
|
|
|
|
| composite | An integer a > 1 that is not prime is said to be a composite number (or, more simply, a composite).
(See page 851)
|
|
|
|
| concatenation | of two strings x and y, denoted xy, has length |x| + |y| and consists of the characters from x followed by the characters from y. Concatenation of two languages L1 and L2 is the language L = {x1x2 : x1 ∈ L1 and x2 ∈ L2}.
(See pages 907, 976)
|
|
|
|
| concrete problem | a problem whose instance set is the set of binary strings
(See page 973)
|
|
|
|
| conditionally independent | Two events A and B are conditionally independent, given C, if Pr{A ∩ B | C} = Pr{A | C} · Pr{B | C}.
(See page 1106)
|
|
|
|
| configuration | any particular state of computer memory
(See page 991)
|
|
|
|
| conjunctive normal form (CNF) | A boolean formula in this form is expressed as an AND of clauses, each of which is the OR of one or more literals.
(See page 999)
|
|
|
|
| conjugate transpose | A* - obtained from the transpose of A by replacing every entry with its complex conjugate.
(See page 759)
|
|
|
|
| consolidating | consolidating the root list reduces the number of trees in the Fibonacci heap. Consolidating the root list consists of repeatedly executing the following steps until every root in the root list has a distinct degree value.- Find two roots x and y in the root list with the same degree, where key[x] ≤ key[y].
- Link y to x: remove y from the root list, and make y a child of x. This operation is performed by the FIB-HEAP-LINK procedure. The field degree[x] is incremented, and the mark on y, if any, is cleared.
(See page 483)
|
|
|
|
| contract | Table contraction is analogous to table expansion: when the number of items in the table drops too low, allocate a new, smaller table and then copy the items from the old table into the new one. The storage for the old table can then be freed by returning it to the memory-management system.
(See page 420)
|
|
|
|
| convex | A function f(x) is convex if for all x and y and for all 0 ≤ λ ≤ 1, we have f(λx + (1-λ)y) ≤ λf(x) + (1-λ)f(y).)
(See page 1109)
|
|
|
|
| convolution | The operation of multiplying polynomials in coefficient form seems to be considerably more difficult than that of evaluating a polynomial or adding two polynomials. The resulting coefficient vector c is also called the convolution of the input vectors a and b, denoted c = a ⊗ b.
(See page 825)
|
|
|
|
| correct algorithm | for every input instance it halts with the correct output. A correct algorithm solves the given computational problem.
(See page 6)
|
|
|
|
| corresponding flow network | We define the corresponding flow networkG' = (V', E') for the bipartite graph G as follows. We let the source s and sink t be new vertices not in V, and we let V' = V ∪ {s, t}. If the vertex partition of G is V = L ∪ R, the directed edges of G' are the edges of E, directed from L to R, along with V new edges: E' = {(s, u) : u ∈ L} ∪ {(u, v) : u ∈ L, v ∈ R, and
(u, v) ∈ E} ∪ {(v, t) : v ∈ R}.
To complete the construction, we assign unit capacity to each edge in E'. Since each vertex in V has at least one incident edge,
|E| ≥ |V| / 2.
Thus, |E| ≤ |E'| = |E| + |V| ≤ 3|E|, and so |E'| = Θ(E).
(See page 666)
|
|
|
|
| coupon collector's problem | a person trying to collect each of b different coupons must acquire approximately b ln b randomly obtained coupons in order to succeed.
(See page 110)
|
|
|
|
| credit | When an operation's amortized cost exceeds its actual cost, the difference is assigned to specific objects in the data structure as credit. Credit can be used later on to help pay for operations whose amortized cost is less than their actual cost. Thus, the amortized cost of an operation is split between its actual cost and credit that is either deposited or used up.
(See page 410)
|
|
|
|
| critical | An edge (u, v) in a residual network Gf is critical on an augmenting path p if the residual capacity of p is the residual capacity of (u, v), that is, if cf(p) = cf(u, v).
(See page 662)
|
|
|
|
| critical path | longest path through the dag, corresponding to the longest time to perform an ordered sequence of jobs.
(See page 594)
|
|
|
|
| cut | A cut (S, V - S) of an undirected graph G = (V, E) is a partition of V. A cut (S, T) of flow network G = (V, E) is a partition of V into S and
T = V - S such that s ∈ S and t ∈ T. (This definition is similar to the definition of "cut" that we used for minimum spanning trees in Chapter 23, except that here we are cutting a directed graph rather than an undirected graph, and we insist that s ∈ S and t ∈ T.)
(See pages 563, 655)
|
|
|
|
| cutting | The CUT procedure "cuts" the link between x and its parent y, making x a root.
(See page 490)
|
|
|
|
| cycles | SIMPLEX cycles if the slack forms at two different iterations are identical, in which case, since SIMPLEX is a deterministic algorithm, it will cycle through the same series of slack forms forever.
(See page 802)
|
|
|
|
| data structure | a way to store and organize data in order to facilitate access and modifications.
(See page 8)
|
|
|
|
| deadlines | a set of n integers d1, d2, . . . , dn, such that each di satisfies 1 ≤ di ≤ n and task ai is supposed to finish by time di.
(See page 399)
|
|
|
|
| decided | A language L is decided by an algorithm A if every binary string in L is accepted by A and every binary string not in L is rejected by A.
(See page 976)
|
|
|
|
| breadth-first search | one of the simplest algorithms for searching a graph and the archetype for many important graph algorithms. Given a graph G = (V, E) and a distinguished source vertex s, breadth-first search systematically explores the edges of G to "discover" every vertex that is reachable from s. It computes the distance (smallest number of edges) from s to each reachable vertex. It also produces a "breadth-first tree" with root s that contains all reachable vertices. For any vertex v reachable from s, the path in the breadth-first tree from s to v corresponds to a "shortest path" from s to v in G, that is, a path containing the smallest number of edges. Breadth-first search is so named because it expands the frontier between discovered and undiscovered vertices uniformly across the breadth of the frontier. That is, the algorithm discovers all vertices at distance k from s before discovering any vertices at distance k + 1.
(See page 531)
|
|
|
|
| breadth-first tree | The predecessor subgraph GΠ is a breadth-first tree if VΠ consists of the vertices reachable from s and, for all v ∈ VΠ, there is a unique simple path from s to v in GΠ that is also a shortest path from s to v in G. A breadth-first tree is in fact a tree, since it is connected and
|EΠ| = |VΠ| - 1.
(See page 538)
|
|
|
|
| bridge | G = (V, E) is a connected, undirected graph. A bridge of G is an edge whose removal disconnects G.
(See page 558)
|
2002 McGraw-Hill Higher Education