Thomas H. Cormen,
Dartmouth College
Charles E. Leiserson,
Massachusetts Institute of Technology
Ronald L. Rivest,
Massachusetts Institute of Technology
Clifford Stein,
Columbia University
| joining 2-3-4 trees | The join operation takes two dynamic sets S' and S'' and an element x such that for any x' ∈ S' and x'' ∈ S'', we have key[x'] < key[x] < key[x'']. It returns a set S = S' ∪ {x} ∪ S''.
(See page 453)
|
 |
|
|
| joint probability density function | If X and Y are random variables, the function f(x, y) = Pr{X = x and Y = y} is the joint probability density function of X and Y.
(See page 1107)
|
|
|
|
| Josephus problem | Suppose that n people are arranged in a circle and that we are given a positive integer m ≤ n. Beginning with a designated first person, we proceed around the circle, removing every mth person. After each person is removed, counting continues around the circle that remains. This process continues until all n people have been removed.
(See page 318)
|
|
|
|
| k-coloring | of an undirected graph G = (V, E) is a function c : V → {1,2,...,k} such that c(u) ≠ c(v) for every edge u, v) ∈ E. In other words, the numbers 1,2,...,k represent the k colors, and adjacent vertices must have different colors.
(See page 1019)
|
|
|
|
| k-combination | of an n-set S is simply a k-subset of S.
(See page 1096)
|
|
|
|
| k-conjunctive normal form | a boolean formula is in k-conjunctive normal form, or k-CNF, if it is the AND of clauses of ORs of exactly k variables or their negations.
(See page 967)
|
|
|
|
| key | Each record contains a key, which is the value to be sorted, and the remainder of the record consists of satellite data, which are usually carried around with the key. In a typical implementation of a dynamic set, each element is represented by an object whose fields can be examined and manipulated if we have a pointer to the object. Some kinds of dynamic sets assume that one of the object's fields is an identifying key field. If the keys are all different, we can think of the dynamic set as being a set of key values.
(See pages 123, 197)
|
|
|
|
| keys | another name for the numbers that we wish to sort
(See page 15)
|
|
|
|
| k-permutation | of S is an ordered sequence of k elements of S, with no element appearing more than once in the sequence. (Thus, an ordinary permutation is just an n-permutation of an n-set).
(See page 1095)
|
|
|
|
| k-string | a string of length k
(See page 1095)
|
|
|
|
| k-substring | of a string is a substring of length k.
(See page 1095)
|
|
|
|
| kth power | For any integer k > 0, an integer n is a kth power if there exists an integer a such that ak = n.
(See page 855)
|
|
|
|
| language | L over Ε is any set of strings made up of symbols from Ε.
(See page 975)
|
|
|
|
| language verified | The language verified by a verification algorithm A is L = {x ∈ {0,1}* : there exists y ∈ {0,1}* such that A(x, y) = 1}. Intuitively, an algorithm A verifies a language L if for any string x ∈ L, there is a certificate y that A can use to prove that x ∈ L. Moreover, for any string x ∉ L, there must be no certificate proving that x ∈ L.
(See page 981)
|
|
|
|
| late | a property of a task in a schedule if it finishes after its deadline.
(See page 399)
|
|
|
|
| leading submatrix | The kth leading submatrix of A is the matrix Ak consisting of the intersection of the first k rows and first k columns of A.
(See page 760)
|
|
|
|
| least common ancestor | of two nodes u and v in a rooted tree T is the node w that is an ancestor of both u and v and that has the greatest depth in T.
(See page 521)
|
|
|
|
| least common multiple | Define lcm(a1, a2, . . . , an) to be the least common multiple of the n integers a1, a2, . . . , an, that is, the least nonnegative integer that is a multiple of each ai.
(See page 861)
|
|
|
|
| left-child, right-sibling representation | a clever scheme for using binary trees to represent trees with arbitrary numbers of children. It has the advantage of using only O(n) space for any n-node rooted tree. Each node contains a parent pointer p, and root[T] points to the root of the tree T. Each node x has only two pointers: 1. left-child[x] points to the leftmost child of node x, and 2. right-sibling[x] points to the sibling of x immediately to the right. If node x has no children, then left-child[x] = NIL, and if node x is the rightmost child of its parent, then right-sibling[x] = NIL.
(See page 214)
|
|
|
|
| left spine | on a binary search tree T it is the path from the root to the node with the smallest key. In other words, the left spine is the path from the root that consists of only left edges.
(See page 298)
|
|
|
|
| length | The length of a spine is the number of nodes it contains.
(See page 298)
|
|
|
|
| lexicographically less than | Given two strings a = a0a1 . . . ap and b = b0b1 . . . bq, where each ai and each bj is in some ordered set of characters, we say that string a is lexicographically less than string b if either 1. there exists an integer j, where 0 ≤ j ≤ min(p, q), such that ai = bi for all i = 0, 1, . . . , j - 1 and aj < bj, or 2. p < q and ai = bi for all i = 0, 1, . . . , p.
(See page 269)
|
|
|
|
| light edge | An edge is a light edge crossing a cut if its weight is the minimum of any edge crossing the cut. There can be more than one light edge crossing a cut in the case of ties. More generally, an edge is a light edge satisfying a given property if its weight is the minimum of any edge satisfying the property.
(See page 563)
|
|
|
|
| linear constraints | denote either linear equalities or linear inequalities.
(See page 772)
|
|
|
|
| linear equality | If b is a real number and f is a linear function, then the equation f(x1, x2, . . . , xn) = b is a linear equality.
(See page 772)
|
|
|
|
| linear function | running time can be expressed as an + b for constants a and b that depend on the statement costs ci.
(See page 25)
|
|
|
|
| linear inequality | If b is a real number and f is a linear function, then the inequalities f(x1, x2, . . . , xn) ≤ b and f(x1, x2, . . . , xn) ≥ b are linear inequalities
(See page 772)
|
|
|
|
| linear-inequality feasibility problem | Given a set of m linear inequalities on n variables x1, x2, . . . , xn, it asks if there is a setting of the variables that simultaneously satisfies each of the inequalities.
(See page 818)
|
|
|
|
| linearity of expectation | The expectation of the sum of two random variables is the sum of their expectations, that is, E[X + Y] = E[X] + E[Y], whenever E[X] and E[Y] are defined. We call this property linearity of expectation, and it holds even if X and Y are not independent. It also extends to finite and absolutely convergent summations of expectations. Linearity of expectation is the key property that enables us to perform probabilistic analyses by using indicator random variables.
(See page 1108)
|
|
|
|
| linearly dependent | The vectors x1, x2, . . . , xn are linearly dependent if there exist coefficients c1, c2, . . . , cn, not all of which are zero, such that
c1x1 + c2x2 + · · · cnxn = 0.
(See page 731)
|
|
|
|
| linearly independent | vectors which are not linearly dependent. For example, the columns of an identity matrix are linearly independent.
(See page 731)
|
|
|
|
| linear probing | a method which uses the hash function h(k, i) = (h'(k) + i) mod m for i = 0, 1, ... , m - 1.
(See page 239)
|
|
|
|
| linear programming duality | a very important property. In an optimization problem, the identification of a dual problem is almost always coupled with the discovery of a polynomial-time algorithm. Duality is also powerful in its ability to provide a proof that a solution is indeed optimal.
(See page 804)
|
|
|
|
| linear-programming problem | Many problems can be formulated as maximizing or minimizing an objective, given limited resources and competing constraints. If we can specify the objective as a linear function of certain variables, and if we can specify the constraints on resources as equalities or inequalities on those variables, then we have a linear-programming problem. It is the problem of either minimizing or maximizing a linear function subject to a finite set of linear constraints.
(See pages 770, 772)
|
|
|
|
| lines | We draw a comparison network on n inputs as a collection of n horizontal lines with comparators stretched vertically. Note that a line does not represent a single wire, but rather a sequence of distinct wires connecting various comparators.
(See page 705)
|
|
|
|
| link | Link y to x is one step in the process of consolidating the root list of a Fibonacci heap. To link y to x the process removes y from the root list, and makes y a child of x.
(See page 483)
|
|
|
|
| linked list | a data structure in which the objects are arranged in a linear order
(See page 204)
|
|
|
|
| literal | in a boolean formula is an occurence of a variable or its negation.
(See page 999)
|
|
|
|
| load factor | the average number of elements stored in a chain. We define the load factor α for T as n/m. Analysis will be in terms of α, which can be less than, equal to, or greater than 1. The load factor defines α(T) of a nonempty table T to be the number of items stored in the table divided by the size (number of slots) of the table.
(See pages 226, 417)
|
|
|
|
| logic gates | The boolean combinational elements that we use in the circuit-satisfiability problem which compute a simple boolean function.
(See page 987)
|
|
|
|
| longest-common-subsequence problem | We are given two sequences
X = (x1, x2, . . . , xm) and Y = (y1, y2, . . . , yn)
and wish to find a maximum-length common subsequence of X and Y.
(See page 351)
|
|
|
|
| longest-simple-cycle problem | of determining a simple cycle (no repeated vertices) of maximum length in a graph.
(See page 1017)
|
|
|
|
| loop invariant | At the start of each iteration of the for loop, the subarray consists of the elements originally in the subarray but in sorted order.
(See page 17)
|
|
|
|
| low endpoint | if interval [t1, t2] is an object i, then field low[i] = t1 is the low endpoint.
(See page 311)
|
|
|
|
| lower-triangular matrix | one for which lij = 0 if i < j. All entries above the diagonal are zero.
(See page 728)
|
|
|
|
| LU decomposition | If an LUP decomposition can be computed for a non-singular matrix A, forward and back substitution can be used to solve the system Ax = b of linear equations. To show how an LUP decomposition for A can be found efficiently, we start with the case in which A is an n x n nonsingular matrix and P is absent (or, equivalently, P = In). In this case, we must find a factorization A = LU. We call the matrices L and U and LU decomposition of A.
(See page 747)
|
|
|
|
| LUP decomposition | The idea behind LUP decomposition is to find three n x n matrices L, U, and P such that P A = LU, where · L is a unit lower-triangular matrix, · U is an upper-triangular matrix, and · P is a permutation matrix. We call matrices L, U, and P satisfying the equation P A = LU an LUP decomposition of the matrix A.
(See page 743)
|
|
|
|
| Maintenance | If a loop invariant is true before an iteration of the loop, it remains true before the next iteration.
(See page 18)
|
|
|
|
| master method | A method for solving recurrences - that is, for obtaining asymptotic "Θ" or "O" bounds on the solution. The master method provides bounds for recurrences of the form T(n) = aT(n / b) + f(n), where a ≥ 1, b > 1, and f(n) is a given function; it requires memorization of three cases, but once you do that, determining asymptotic bounds for many simple recurrences is easy.
(See page 62)
|
|
|
|
| matched | We say that a vertex v ∈ V is matched by matching M if some edge in M is incident on v; otherwise, v is unmatched.
(See page 664)
|
|
|
|
| matching | Given an undirected graph G = (V, E), a matching is a subset of edges M ⊆ E such that for all vertices v ∈ V, at most one edge of M is incident on v.
(See page 664)
|
|
|
|
| matrix | a rectangular array of numbers
(See page 726)
|
|
|
|
| matrix addition | If A = (aij) and B = (bij) are m x n matrices, then their matrix sum
C = (cij) = A + B is the m x n matrix defined by cij = aij + bij for i = 1, 2, . . . , m and j = 1, 2, . . . , n. That is, matrix addition is performed componentwise.
(See page 728)
|
|
|
|
| matrix-chain multiplication problem | Given a chain (A1, A2, . . . , An) of n matrices, where for i = 1, 2, . . . , n, matrix Ai has dimension pi-1 x pi, fully parenthesize the product
A1A2 . . . An in a way that minimizes the number of scalar multiplications.
(See page 332)
|
|
|
|
| matrix multiplication | We start with two matrices A and B that are compatible in the sense that the number of columns of A equals the number of rows in B. If
A = (aij) is an m x n matrix and B = (bjk) is an n x p matrix, then their matrix product C = AB is the m x p matrix C = (cik).
(See page 729)
|
|
|
|
| matrix subtraction | the addition of the negative of a matrix: A - B = A + (-B).
(See page 729)
|
|
|
|
| MAX-3-CNF satisfiability | In order to be satisfiable, there must be an assignment of the variables so that every clause evaluates to 1. If an instance is not satisfiable, we may want to compute how "close" to satisfiable it is, that is, we may wish to find an assignment of the variables that satisfies as many clauses as possible. We call the resulting maximization problem MAX-3-CNF satisfiability. The input to MAX-3-CNF satisfiability is the same as for 3-CNF satisfiability, and the goal is to return an assignment of the variables that maximizes the number of clauses evaluating to 1.
(See page 1039)
|
|
|
|
| MAX-CNF satisfiability problem | is like the MAX-3-CNF satisfiability problem, except that it does not restrict each clause to have exactly 3 literals.
(See page 1043)
|
|
|
|
| max-heap property | In a max-heap, the max-heap property is that for every node i other than the root, A[PARENT(i)] ≥ A[i], that is, the value of a node is at most the value of its parent.
(See page 128)
|
|
|
|
| maximal | If A is an independent subset in a matroid M, then A is maximal if it has no extensions. That is, A is maximal if it is not contained in any larger independent subset of M.
(See page 394)
|
|
|
|
| maximal matching | a matching that is not a proper subset of any other matching.
(See pages 1026, 1051)
|
2002 McGraw-Hill Higher Education