Thomas H. Cormen,
Dartmouth College
Charles E. Leiserson,
Massachusetts Institute of Technology
Ronald L. Rivest,
Massachusetts Institute of Technology
Clifford Stein,
Columbia University
| full node | a node is full if it contains exactly 2t - 1 keys, where t is the minimum degree of the B-tree.
(See page 439)
|
 |
|
|
| full rank | A square n x n matrix has full rank if its rank is n.
(See page 731)
|
|
|
|
| fully parenthesized | A product of matrices is fully parenthesized if it is either a single matrix or the product of two fully parenthesized matrix products, surrounded by parentheses.
(See page 331)
|
|
|
|
| fully polynomial-time approximation scheme | property of an approximation scheme if its running time is polynomial both in 1/ε and in the size of the input instance.
(See page 1023)
|
|
|
|
| fusion trees | allow faster dictionary operations when the universe is restricted to integers.
(See page 433)
|
|
|
|
| fuzzy sorting of intervals | Consider a sorting problem in which the numbers are not known exactly. Instead, for each number, we know an interval on the real line to which it belongs. That is, we are given n closed intervals of the form [ai, bi], where ai ≤ bi. The goal is to fuzzy-sort these intervals, i.e., produce a permutation (i1, i2,...,in) of the intervals such that there exist cj ∈ [aij, bij] satisfying c1 ≤ c2 ≤ · · · ≤ cn.
(See page 163)
|
|
|
|
| garbage collector | responsible for determining which objects are unused.
(See page 210)
|
|
|
|
| Gaussian elimination | The process which performs LU decomposition.
(See page 747)
|
|
|
|
| geometric distribution | A probability distribution which satisfies the equation Pr{X = k} = qk-1p.
(See page 1112)
|
|
|
|
| gossiping | communicating a unique item from each vertex in a graph to every other vertex
(See page 429)
|
|
|
|
| graph-coloring problem | determine the minimum number of colors needed to color a given graph.
(See page 1019)
|
|
|
|
| greatest common divisor | of two integers a and b, not both zero, is the largest of the common divisors of a and b; it is denoted gcd(a,b).
(See page 852)
|
|
|
|
| greedy algorithm | always makes the choice that looks best at the moment. That is, it makes a locally optimum choice in the hope that this choice will lead to a globally optimal solution.
(See page 370)
|
|
|
|
| greedy-choice property | a globally optimal solution can be arrived at by making a locally optimal (greedy) choice. The greedy choice is the one that looks best in the current problem, without considering results from subproblems.
(See page 380)
|
|
|
|
| grid | An n x n grid is an undirected graph consisting of n rows and n columns of vertices.
(See page 692)
|
|
|
|
| half 3-CNF satisfiability problem | given a 3-CNF formula φ with n variables and m clauses, where m is even. We wish to determine whether there exists a truth assignment to the variables of φ such that exactly half the clauses evaluate to 0 and exactly half the clauses evaluate to 1.
(See page 1018)
|
|
|
|
| half-cleaner | a comparison network of depth 1 in which input line i is compared with line i + n/2 for i = 1, 2, . . . , n/2. (We assume that n is even.)
(See page 712)
|
|
|
|
| half-open interval | omits one of the endpoints from the set
(See page 311)
|
|
|
|
| Hall's theorem | there exists a perfect mathing in G if and only if |A| ≤ |N(A)| for every subset A ⊆ L.
(See page 669)
|
|
|
|
| hamiltonian | A graph that contains a hamiltonian cycle is said to be hamiltonian; otherwise, it is nonhamiltonian.
(See page 979)
|
|
|
|
| hamiltonian cycle | of a directed graph G = (V, E) is a simple cycle that contains each vertex in V.
(See page 967)
|
|
|
|
| hamiltonian-cycle problem | "Does a graph G have a hamiltonian cycle?" can be defined as a formal language: HAM-CYCLE = {⟨G⟩ : G is a hamiltonian graph}.
(See page 979)
|
|
|
|
| hamiltonian path | in a graph is a simple path that visits every vertex exactly once.
(See page 983)
|
|
|
|
| hat-check problem | Each of n customers gives a hat to a hat-check person at a restaurant. The hat-check person gives the hats back to the customers in a random order. What is the expected number of customers that get back their own hat?
(See page 98)
|
|
|
|
| head | In a FIFO queue when an element is dequeued it is always the one at the head of the queue.
(See page 202)
|
|
|
|
| height | Viewing a heap as a tree, we define the height of a node in a heap to be the number of edges on the longest simple downward path from the node to a leaf, and we define the height of the heap to be the height of its root.
(See page 129)
|
|
|
|
| height balanced | for each node x, the heights of the left and right subtrees of x differ by at most 1
(See page 296)
|
|
|
|
| height function | A function h : V → N is a height function if h(s) = |V|, h(t) = 0, and h(u) ≤ h(v) + 1 for every residual edge (u, v ∈ Ef).
(See page 671)
|
|
|
|
| Hermitian | matrices such that A = A*.
(See page 759)
|
|
|
|
| high endpoint | if interval [t1, t2] is an object i, then field high[i] = t2 is the high endpoint.
(See page 311)
|
|
|
|
| Huffman code | optimal prefix codes constructed by a greedy algorithm invented by Huffman
(See page 387)
|
|
|
|
| identity | There is an element e ⊆ S, called the identity of the group, such that
e ⊕ a = a ⊕ e = a for all a ⊆ S.
(See page 862)
|
|
|
|
| identity matrix | a diagonal matrix with 1's along the diagonal
(See page 727)
|
|
|
|
| implicit summation notation | We shall be dealing with several functions (like f) that take as arguments two vertices in a flow network. In this chapter, we shall use an implicit summation notation in which either argument, or both, may be a set of vertices, with the interpretation that the value denoted is the sum of all possible ways of replacing the arguments with their members.
(See page 648)
|
|
|
|
| incremental | The approach used for insertion sort: having sorted the subarray
A[1..j - 1], we insert the single element A[j] into its proper place, yielding the sorted array A[1..j].
(See page 27)
|
|
|
|
| independent | The solution to one subproblem does not affect the solution to another subproblem of the same problem. Two subproblems of the same problem are independent if they do not share resources. Two events are independent if Pr{A ∩ B} = Pr{A}Pr{B} , which is equivalent, if Pr{B} ≠ 0, to the condition Pr{A | B} = Pr{A}. We define two random variables X and Y to be independent if for all x and y, the events X = x and Y = x are independent or, equivalently, of for all x and y, we have Pr{X = x and Y = y} = Pr{X = x}Pr{Y = y}.
(See pages 343, 1103, 1107)
|
|
|
|
| independent set | of a graph G = (V, E) is a subset V′ ⊆ V of vertices such that each edge in E is incident on at most one vertex in V′.
(See page 1018)
|
|
|
|
| independent-set problem | find a maximum-size independent set in G.
(See page 1018)
|
|
|
|
| independent tasks | property of a set of tasks such that no tasks are late in the associated schedule.
(See page 400)
|
|
|
|
| inequality constraints | A linear program which is not in standard form because instead of having a less-than-or-equal-to sign, it has a greater-than-or-equal-to sign.
(See page 778)
|
|
|
|
| infeasible | a linear program which has no feasible solutions.
(See page 778)
|
|
|
|
| infeasible solution | a setting of the variables that fails to satisfy at least one constraint.
(See page 778)
|
|
|
|
| Initialization | A loop invariant is true prior to the first iteration of the loop.
(See page 18)
|
|
|
|
| inorder tree walk | an algorithm so named because the key of the root of a subtree is printed between the values in its left subtree and those in its right subtree.
(See page 254)
|
|
|
|
| Input | A sequence of n numbers (a1, a2,...,an).
(See page 5)
|
|
|
|
| input sequence | ⟨a1, a2, . . . , an⟩ referring to the values on the input wires.
(See page 705)
|
|
|
|
| input wires | a1, a2, . . . , an, through which the values to be sorted enter the network.
(See page 705)
|
|
|
|
| instance | input to a particular problem
(See page 969)
|
|
|
|
| instance of a problem | consists of the input (satisfying whatever constraints are imposed in the problem statement) needed to compute a solution to the problem.
(See page 5)
|
|
|
|
| integer linear program | has an additional requirement that all variables take on integer values.
(See page 777)
|
|
|
|
| integer linear-programming problem | a linear-programming problem with the additional constraint that the variables must take on integer values. It is like the 0-1 integer-programming problem except that the values of the vector x may be any integers rather than just 0 or 1.
(See pages 819, 1017)
|
|
|
|
| integer-valued | We say that a flow f on a flow network G = (V, E) is integer-valued
if f(u, v) is an integer for all (u, v) ∈ V x V.
(See page 666)
|
|
|
|
| interior-point methods | A second class of polynomial-time algorithms.
(See page 776)
|
|
|
|
| intermediate | The Floyd-Warshall algorithm considers the "intermediate" vertices of a shortest-path, where an intermediate vertex of a simple path
p = ⟨v1, v2, . . . , vl⟩ is any vertex of p other than v1 or vl, that is, any vertex in the set {v2, v3, . . . , vl-1}.
(See page 629)
|
|
|
|
| interpolation | the inverse of evaluation, determining the coefficient form of a polynomial from a point-value representation.
(See page 825)
|
|
|
|
| interval tree | a red-black tree that maintains a dynamic set of elements, with each element x containing an interval int[x].
(See page 312)
|
|
|
|
| interval trichotomy | Any two intervals i and i' satisfy the interval trichotomy; that is, exactly one of the following three properties holds: a. i and i' overlap, b. i is to the left of i' (i.e., high[i] < low[i']), c. i is to the right of i' (i.e., high[i'] < low[i]).
(See page 311)
|
|
|
|
| inverse | of an n x n matrix A is the n x n matrix, denoted A-1 (if it exists), such that AA-1 = In = A-1A. Many nonzero n x x matrices do not have inverses. For each a ⊆ S, there exists a unique element of b ⊆ S, called the inverse of a, such that a ⊕ b = b ⊕ a = e.
(See pages 730, 862)
|
|
|
|
| inversion | Let A[1..n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i, j) is called an inversion of A.
(See page 99)
|
|
|
|
| invertible, or nonsingular | A matrix with an inverse.
(See page 730)
|
|
|
|
| Jensen's inequality | When we apply a convex function f(x) to a random variable X, Jensen's inequality gives us E[f(X)] ≥ f(E[X]), provided that the expectations exist and are finite.
(See page 1109)
|
2002 McGraw-Hill Higher Education