Thomas H. Cormen,
Dartmouth College
Charles E. Leiserson,
Massachusetts Institute of Technology
Ronald L. Rivest,
Massachusetts Institute of Technology
Clifford Stein,
Columbia University
| maximization linear program | the linear program we are to maximize.
(See page 773)
|
 |
|
|
| maximum | The maximum of a set of elements is the nth order statistic (i = n).
(See page 183)
|
|
|
|
| maximum-flow problem | given a flow network G with source s and sink t, and we wish to find a flow of maximum value.
(See page 645)
|
|
|
|
| maximum matching | A maximum matching is a matching of maximum cardinality, that is, a matching M such that for any matching M', we have |M| ≥ |M'|.
(See page 664)
|
|
|
|
| max-priority queue | supports the following operations. INSERT(S, x) inserts the element x into the set S. This operation could be written as S ← S ∪ {x}. MAXIMUM(S) returns the element of S with the largest key. EXTRACT-MAX(S) removes and returns the element of S with the largest key. INCREASE-KEY(S, x, k) increases the value of element x's key to the new value k, which is assumed to be at least as large as x's current key value. One application of max-priority queues is to schedule jobs on a shared computer.
(See page 138)
|
|
|
|
| median | informally it is the "halfway point" of a set.
(See page 183)
|
|
|
|
| median-of-3 | One way to improve the RANDOMIZED-QUICKSORT procedure is to partition around a pivot that is chosen more carefully than by picking a random element from the subarray. One common approach is the median-of-3 method: choose the pivot as the median (middle element) of a set of 3 elements randomly selected from the subarray.
(See page 162)
|
|
|
|
| memoize | A memoized recursive algorithm maintains an entry in a table for the solution to each subproblem. Each table entry initially contains a special value to indicate that the entry has yet to be filled in. When the subproblem is first encountered during the execution of the recursive algorithm, its solution is computed and then stored in the table. Each subsequent time that the subproblem is encountered, the value stored in the table is simply looked up and returned. This approach presupposes that the set of all possible subproblem parameters is known and that the relation between table positions and subproblems is established. Another approach is to memoize by using hashing with the subproblem parameters as keys.
(See page 347)
|
|
|
|
| mergeable max-heap | a mergeable heap which supports MAXIMUM and EXTRACT-MAX.
(See page 431)
|
|
|
|
| mergeable min-heap | a mergeable heap which supports MINIMUM and EXTRACT-MIN. This is the default mergeable heap.
(See page 431)
|
|
|
|
| merging networks | networks that can merge two sorted input sequences into one sorted output sequence.
(See page 716)
|
|
|
|
| min-heap property | A min-heap is organized in the opposite way from the max-heap; the min-heap property is that for every node i other than the root, A[PARENT(i)] ≤ A[i].
(See page 129)
|
|
|
|
| minimization linear program | the linear program we are to minimize.
(See page 773)
|
|
|
|
| minimum | the minimum of a set of elements is the first order statistic (i - 1)
(See page 183)
|
|
|
|
| minimum cut | A minimum cut of a network is a cut whose capacity is minimum over all cuts of the network.
(See page 655)
|
|
|
|
| minimum degree of a B-tree | determined by the lower and upper bounds on the number of keys a node can contain, expressed in terms of a fixed integer t ≥ 2.
(See page 439)
|
|
|
|
| minimum path cover | of G is a path cover containing the fewest possible paths.
(See page 692)
|
|
|
|
| minimum-spanning-tree problem | Given a connected undirected graph G = (V, e) and a length function ω such that ω(e) is the (positive) length of edge e, find a subset of the edges that connects all of the vertices together and has minimum total length. (The term "length" refers to the original edge weights for the graph, reserving the term "weight" to refer to the weights in the associated matroid.) It is the problem of determining the spanning tree, T.
(See pages 395, 561)
|
|
|
|
| minimum-weight vertex-cover problem | given an undirected graph G = (V, E) in which each vertex v ∈ V has an associated positive weight w(v). For any vertex cover V′ ⊆ V, we define the weight of the vertex cover w(V′) = Εv ∈ V′ w(v). The goal is to find a vertex cover of minimum weight.
(See page 1040)
|
|
|
|
| minor | The ijth minor of an n x n matrix A, for n > 1, is the (n - 1) x (n - 1) matrix A[ij] obtained by deleting the ith row and jth column of A.
(See page 732)
|
|
|
|
| min-priority queue | supports the operations INSERT, MINIMUM, EXTRACT-MIN, and DECREASE-KEY. The min-priority queue can be used in an event-driven simulator.
(See page 138)
|
|
|
|
| modifying operations | operations on a dynamic set which change the set
(See page 198)
|
|
|
|
| modular exponentiation | A frequently occurring operation in number-theoretic computations is raising one number to a power modulo another number, also know as modular exponentiation.
(See page 879)
|
|
|
|
| Monge array | An m x n array A of real numbers is a Monge array if for all i, j, k, and l such that 1 ≤ i < k ≤ m and 1 ≤ j < l ≤ n, we have A[i, j] + A[k, l] ≤ A[i, l] + A[k, j].
(See page 88)
|
|
|
|
| monotone | the values returned by successive EXTRACT-MIN operations are monotonically increasing over time.
(See page 144)
|
|
|
|
| monotonically decreasing | A function f(n) is monotonically decreasing if m ≤ n implies
f(m) ≥ f(n).
(See page 51)
|
|
|
|
| monotonically increasing | A function f(n) is monotonically increasing if m ≤ n implies
f(m) ≤ f(n).
(See page 51)
|
|
|
|
| multiple | If d | a, then a is a multiple of d.
(See page 850)
|
|
|
|
| multiplication method | The multiplication method for creating hash functions operates in two steps. First, we multiply the key k by a constant A in the range
0 < A < 1 and extract the fractional par of kA. Then, we multiply this value by m and take the floor of the result.
(See page 231)
|
|
|
|
| mutually exclusive | Two events A and B are mutually exclusive if A ∩ B = ∅. We sometimes treat an elementary event s ∈ S as the event {s}. By definition, all elementary events are mutually exclusive.
(See page 1100)
|
|
|
|
| negative | As a special case, we define the negative of a matrix A = (aij) to be
-1 · A = -A, so that the ijth entry of -A is -aij. ThusA + (-A) = 0 = (-A) + A.
(See page 729)
|
|
|
|
| neighborhood | For any X ⊆ V, define the neighborhood of X as N(X) = {y ∈ V : (x, y) ∈ E for some x ∈ X}, that is, the set of vertices adjacent to some member of X.
(See page 669)
|
|
|
|
| neighbor list | Given a flow network G = (V, E), the neighbor list N[u] for a vertex
u ∈ V is a singly linked list of the neighbors of u in G.
(See page 683)
|
|
|
|
| nests | A d-dimensional box with dimensions (x1, x2, . . . , xd) nests within another box with dimensions (y1, y2, . . . , yd) if there exists a permutation π on {1, 2, . . . , d} such that
xπ(1) < y1, xπ(2) < y2, . . . , xπ(d) < yd.
(See page 615)
|
|
|
|
| net flow | If f is a flow, then the net flow across the cut (S, T) is defined to be
f(S, T).
(See page 655)
|
|
|
|
| nonbasic variables | the variables on the right-hand side of an equality.
(See page 782)
|
|
|
|
| noninstance | of an encoding e is a string x ∈ {0, 1}* such that there is no instance i for which e(i) = x.
(See page 974)
|
|
|
|
| noninvertible, or singular | A matrix without an inverse.
(See page 730)
|
|
|
|
| nontrivial divisors | Nontrivial divisors of a are also called factors of a.
(See page 851)
|
|
|
|
| nontrivial power | n > 1 is a nontrivial power if it is a kth power for some integer k > 1.
(See page 855)
|
|
|
|
| nontrivial square root of 1, modulo n | A number x is a nontrivial square root of 1, modulo n, if it satisifies the equation s2 ≡ 1 (mod n) but x is equivalent to neither of the two "trivial" square roots: 1 or -1, modulo n.
(See page 879)
|
|
|
|
| no-path property | If there is no path from s to v, then we always have d[v] = δ(s, v) = ∞.
(See page 587)
|
|
|
|
| NOT gate | (or inverter) takes a single binary input x, whose value is either 0 or 1, and produces a binary output z whose value is opposite that of the input value.
(See page 987)
|
|
|
|
| NP-complete | Informally, a problem is in the class NPC - and we refer to it as being NP-complete - if it is in NP and is as "hard" as any problem in NP. A language L ⊆ {0,1}* is NP-complete if- L ∈ NP, and
- L′ ≤PL for every L′ ∈ NP.
(See pages 968, 986)
|
|
|
|
| NP-hard | If a language L satisfies property 2 of NP-complete, but not necessarily property 1, we say that L is NP-hard.
(See page 986)
|
|
|
|
| null event | the event ∅
(See page 1100)
|
|
|
|
| null vector | for a matrix A is a nonzero vector x such that Ax = 0.
(See page 731)
|
|
|
|
| numerical stability | Due to the limited precision of floating-point representations in actual computers, round-off errors in numerical computations may become amplified over the course of a computation, leading to incorrect results; such computations are numerically unstable.
(See page 723)
|
|
|
|
| objective function | the function we wish to maximize.
(See page 773)
|
|
|
|
| objective value | the value of the objective function at a particular point.
(See page 774)
|
|
|
|
| objects | typical organization for compound data. Composed of attributes or fields.
(See page 20)
|
|
|
|
| odd-even merging network | If n is an exact power of 2, we wish to merge the sorted sequence of elements on lines ⟨a1, a2, . . . , an⟩ with those lines
⟨an+1, an+2, . . . , a2n⟩.
(See page 721)
|
|
|
|
| odd-even sorting network | An odd-even sorting network on n inputs ⟨a1, a2, . . . , an⟩ is a transposition sorting network with n levels of comparators connected in the "brick-like" pattern.
(See page 721)
|
|
|
|
| off-line least-common-ancestors problem | Given a rooted tree T and an arbitrary set P = {{u, v}} of unordered pairs of nodes in T, determine the least common ancestor of each pair in P.
(See page 521)
|
|
|
|
| off-line minimum problem | to maintain a dynamic set T of elements from the domain {1, 2, . . . , n} under the operations INSERT and EXTRACT-MIN. Given a sequence S of n INSERT and m EXTRACT-MIN calls, where each key in {1, 2, . . . , n} is inserted exactly once, determine which key is returned by each EXTRACT-MIN call. Specifically, fill in an array extracted[1..m], where for
i = 1, 2, . . . , m, extracted[i] is the key returned by the ith EXTRACT-MIN call. The problem is "off-line" in the sense that it processes the entire sequence S before determining any of the returned keys.
(See page 518)
|
|
|
|
| open addressing | In open addressing, all elements are stored in the hash table itself. That is, each table entry contains either an element of the dynamic set or NIL.
(See page 237)
|
|
|
|
| open interval | omits both endpoints from the set.
(See page 311)
|
|
|
|
| optimal binary search tree | A binary search tree organized so as to minimize the number of nodes visited in all searches, given that we know how often each word occurs. A binary search tree whose expected search cost is smallest.
(See page 357)
|
|
|
|
| optimal substructure | for assembly-line scheduling, an optimal solution to a problem (finding the fastest way through station Si, j) contains within it an optimal solution to subproblems (finding the fastest way through either S1, j-1 or S2, j-1). A problem exhibits optimal substructure if an optimal solution to the problem contains within it optimal solutions to subproblems. A problem exhibits optimal substructure if an optimal solution to the problem contains within it optimal solutions to subproblems.
(See pages 327, 381)
|
|
|
|
| optimization problems | each feasible (i.e., "legal") solution has an associated value, and we wish to find the feasible solution with the best value. Those problems in which some value must be minimized or maximized. In such problems there can be many possible solutions. Each solution has a value, and we wish to find a solution with the optimal (minimum or maximum) value.
(See pages 323, 968, 972)
|
|
|
|
| order statistic | The ith order statistic of a set of n elements is the ith smallest element.
(See page 183)
|
2002 McGraw-Hill Higher Education