Thomas H. Cormen,
Dartmouth College
Charles E. Leiserson,
Massachusetts Institute of Technology
Ronald L. Rivest,
Massachusetts Institute of Technology
Clifford Stein,
Columbia University
| order-statistic tree | a red-black tree with additional information stored in each node. Besides the usual red-black tree fields key[x], color[x], p[x], left[x], and right[x] in a node x, we have another field size[x]. This field contains the number of (internal) nodes in the subtree rooted at x (including x itself), that is, the size of the subtree.
(See page 303)
|
 |
|
|
| orthonormal | Two vectors are orthonormal if their inner product is 0 and each vector has a norm of 1.
(See page 769)
|
|
|
|
| Output | A permutation (reordering) (a'1, a'2,...,a'n) of the input sequence such that a'1 ≤ a'2 ≤ · · · ≤ a'n.
(See page 5)
|
|
|
|
| output sequence | ⟨b1, b2, . . . , bn⟩ referring to the values on the output wires.
(See page 705)
|
|
|
|
| output wires | b1, b2, . . . , bn, which produce the results computed by the network.
(See page 705)
|
|
|
|
| overdetermined | If the number of equations exceeds the number n of unknowns. There may not exist any solutions.
(See page 743)
|
|
|
|
| overflowing | We say that a vertex u ∈ V - {s, t} is overflowing if e(u) > 0.
(See page 670)
|
|
|
|
| overflows | If top[S] exceeds n, the stack overflows.
(See page 201)
|
|
|
|
| overlap | Intervals i and i' overlap if i ∩ i' ≠ Ø, that is, if low[i] ≤ high[i'] and
low[i'] ≤ high[i].
(See page 311)
|
|
|
|
| overlapping subproblems | When a recursive algorithm revisits the same problem over and over again, we say that the optimization problem has overlapping subproblems. Two subproblems are overlapping if they are really the same subproblem that occurs as a subproblem of different problems.
(See page 344)
|
|
|
|
| page | on a computer storage device consists of bits that appear consecutively within cylinders. Each disk read or write is of one or more entire pages.
(See page 435)
|
|
|
|
| pairwise independent | A collection A1, A2, . . . , An of events is said to be pairwise independent if Pr{Ai ∩ Aj} = Pr{Ai}Pr{Aj} for all 1 ≤ i < j ≤ n.
(See page 1103)
|
|
|
|
| pairwise relatively prime | integers n1, n2, . . . , nk are pairwise relatively prime if, whenever
i ≠ j, we have gcd(ni, nj = 1.
(See page 854)
|
|
|
|
| parallel-machine-scheduling problem | Given n jobs, J1, J2, . . . , Jn, where each job Jk has an associated nonnegative processing time of pk. Also, given m identical machines, M1, M2, . . . , Mm. A schedule specifies, for each job Jk, the machine on which it runs and the time period during which it runs. Each job Jk must run on some machine Mi for pk consecutive time units, and during that time period no other job may run on Mi. Let Ck denote the completion time of job Jk, that is, the time at which job Jk completes processing. Given a schedule we define Cmax = max1≤j≤nCk to be the makespan of the schedule. The goal is to find a schedule whose makespan is minimum.
(See page 1051)
|
|
|
|
| passed by value | the called procedure receives its own copy of the parameters, and if it assigns a value to a parameter, the change is not seen by the calling procedure.
(See page 20)
|
|
|
|
| path compression | simple and very effective heuristic. Used during FIND-SET operations to make each node on the find path point directly to the root. Path compression does not change any ranks.
(See page 506)
|
|
|
|
| path cover | of a directed graph G = (V, E) is a set P of vertex-disjoint paths such that every vertex in V is included in exactly one path in P.
(See page 692)
|
|
|
|
| path-relaxation property | If p = ⟨v0, v1, . . . , vk⟩ is a shortest path from s = v0 to vk, and the edges of p are relaxed in the order (v0, v1), (v1, v2), . . . , (vk-1, vk), then d[vk] = δ(s, vk). This property holds regardless of any other relaxation steps that occur, even if they are itermixed with relaxations of the edges of p.
(See page 587)
|
|
|
|
| penalties | a set of n nonnegative weights w1, w2, . . . , wn, such that a penalty of wi is incurred if task ai is not finished by time di and no penalty is incurred if a task finishes by its deadline.
(See page 399)
|
|
|
|
| perfect hashing | We call a hashing technique perfect hashing if the worst-case number of memory accesses required to perform a search is O(1).
(See page 245)
|
|
|
|
| perfect matching | A perfect matching is a matching in which every vertex is matched.
(See page 669)
|
|
|
|
| permutation | of a finite set S is an ordered sequence of all the elements of S, with each element appearing exactly once.
(See page 1095)
|
|
|
|
| permutation matrix | has exactly one 1 in each row or column, and 0's elsewhere. Called a permutation matrix because multiplying a vector x by a permutation matrix has the effect of permuting (rearranging) the elements of x.
(See page 728)
|
|
|
|
| permutation network | A permutation network on n inputs and n outputs has switches that allow it to connect its inputs to its outputs according to any of the n! possible permutations.
(See page 722)
|
|
|
|
| persistent | past versions of a dynamic set maintained as it is updated.
(See page 294)
|
|
|
|
| persistent data structures | allow queries, and sometimes updates as well, on past versions of a data structure.
(See page 432)
|
|
|
|
| PERT chart | an acronym for "program evaluation and review technique."
(See page 594)
|
|
|
|
| pivot | chooses a nonbasic variable xe, called the entering variable, and a basic variable xi, called the leaving variable, and exchanges their roles.
(See page 793)
|
|
|
|
| pivoting | using permutations to avoid division by 0 (or by small numbers).
(See page 749)
|
|
|
|
| pivots | The elements by which we divide during LU decomposition. They occupy the diagonal elements of the matrix U.
(See page 749)
|
|
|
|
| point of maximum overlap | a point that has the largest number of intervals in the database overlapping it.
(See page 318)
|
|
|
|
| point-value representation | of a polynomial A(x) of degree-bound n is a set of n point-value pairs {(x0, y0), (x1, y1), . . . , (xn - 1, yn - 1)} such that all of the xk are distinct and yk = A(xk) for k = 0, 1, . . . , n - 1.
(See page 825)
|
|
|
|
| polylogarithmically bounded | A function f(n) is polylogarithmically bounded if f(n) = O(lgkn) for some constant k.
(See page 54)
|
|
|
|
| polynomial addition | if A(x) and B(x) are polynomials of degree-bound n, then their sum is a polynomial C(x), also of degree-bound n, such that C(x) = A(x) + B(x) for all x in the underlying field.
(See page 822)
|
|
|
|
| polynomially bounded | A function f(n) is polynomially bounded if f(n) = O(nk) for some constant k.
(See page 52)
|
|
|
|
| polynomially related | For some set I of problem instances, we say that two encodings e1 and e2 are polynomially related if there exist two polynomail-time computable functions f12 and f21 such that for any i ∈ I, we have
f12(e1(i)) = e2(i) and f21(e2(i)) = e1(i). That is, the encoding e2(i) can be computed from the encoding e1(i) by a polynomial-time algorithm, and vice versa. If two encodings e1 and e2 of an abstract problem are polynomially related, whether the problem is polynomial-time solvable or not is independent of which encoding we use.
(See page 974)
|
|
|
|
| polynomial multiplication | if A(x) and B(x) are polynomials of degree-bound n, then their product is a polynomial C(x) of degree-bound 2n -1 such that C(x) = A(x)B(x) for all x in the underlying field.
(See page 823)
|
|
|
|
| polynomial-time algorithm | An algorithm with integer inputs a1, a2, . . . , ak is a polynomial-time algorithm if it runs in time polynomial in lg a1, lg a2, . . . , lg ak, that is, polynomial in the lengths of its binary-encoded inputs.
(See page 850)
|
|
|
|
| polynomial-time algorithms | on inputs of size n, their worst-case running time is O(nk) for some constant k.
(See page 966)
|
|
|
|
| polynomial-time approximation scheme | property of an approximation scheme if for any fixed ε > 0, the scheme runs in time polynomial in the size n of its input instance.
(See page 1023)
|
|
|
|
| polynomial-time computable | A function f : {0, 1}* → {0, 1}* is polynomial-time computable if there exists a polynomial-time algorithm A that, given any input
x ∈ {0, 1}*, produces as output f(x).
(See page 974)
|
|
|
|
| polynomial-time reducible | A language L1 is polynomial-time reducible to a language L2, written L1 ≤P L2, if there exists a polynomial-time computable function
f : {0,1}* → {0,1}* such that for all x ∈ {0,1}*,x ∈ L1 if and only if f(x) ∈ L2. We call the function f the reduction function, and a polynomial-time algorithm F that computes f is called a reduction algorithm.
(See page 984)
|
|
|
|
| polynomial-time solvable | A concrete problem is polynomial-time solvable if there exists an algorithm to solve it in time O(nk) for some constant k.
(See page 973)
|
|
|
|
| pop | When a procedure terminates, its information is popped from the stack.
(See page 162)
|
|
|
|
| positive definite | An n x n matrix A is positive-definite if xTAx > 0 of all size-n vectors
x ≠ 0.
(See page 732)
|
|
|
|
| postorder tree walk | an algorithm so named because the key of the root of a subtree is printed after the values in its subtrees.
(See page 254)
|
|
|
|
| potential function | Φ - maps each data structure Di to a real number Φ(Di), which is the potential associated with data structure Di.
(See page 413)
|
|
|
|
| potential method | A method of amortized analysis which represents the prepaid work as "potential energy" or just "potential," that can be released to pay for future operations. The potential is associated with the data structure as a whole rather than with specific objects within the data structure.
(See page 412)
|
|
|
|
| predecessor | Given a graph G = (V, E), we maintain for each vertex v ∈ V a predecessor π[v] that is either another vertex or NIL.
(See page 584)
|
|
|
|
| predecessor matrix | To solve the all-pairs shortest-paths problem on an input adjacency matrix, we need to compute not only the shortest-path weights but also a predecessor matrix Π = (Πij), where Πij is NIL if either i = j or there is no path from i to j, and otherwise Πij is the predecessor of j on some shortest path from i.
(See page 621)
|
|
|
|
| predecessor subgraph | For each vertex i ∈ V, we define the predecessor subgraph of G for i as Gπ,i = (Vπ, i, Eπ, i), where Vπ, i = {j ∈ V : πij ≠ NIL} ∪ {i} and Eπ,i = {(πij, j) : j ∈ Vπ,i - {i}}.
(See page 621)
|
|
|
|
| predecessor-subgraph property | Once d[v] = δ(s, v) for all v ∈ V, the predecessor subgraph is the shortest-paths tree rooted at s.
(See page 587)
|
|
|
|
| preemption | processing code which allows a task to be suspended and restarted at a later time
(See page 403)
|
|
|
|
| prefix | Given a sequence X = (x1, x2, . . . , xm), we define the ith prefix of X, for i = 0, 1, . . . , m, as Xi = (x1, x2, . . . , xi).
(See page 351)
|
|
|
|
| prefix codes | codes in which no codeword is also a prefix of some other codeword. These could be considered "prefix-free codes".
(See page 385)
|
|
|
|
| preflow | a function f : V x V → R that satisfies skew symmetry, capacity constraints, and the following relaxation of flow conservation:
f(V, u) ≥ 0 for all vertices u ∈ V = {s}. That is, the total net flow at each vertex other than the source is nonnegative.
(See page 669)
|
|
|
|
| preorder tree walk | an algorithm so named because the key of the root of a subtree is printed before the values in either subtree.
(See page 254)
|
|
|
|
| primal | the original linear program when referring to dual linear programs.
(See page 805)
|
|
|
|
| primary clustering | A phenomenon where two keys that hash into differenct values compete with each other in successive rehashes.
(See page 239)
|
|
|
|
| primary or main memory | in a computer system normally consists of silicon memory chips.
(See page 434)
|
|
|
|
| prime | An integer a > 1 whose only divisors are the trivial divisors 1 and a is said to be a prime number (or, more simply, a prime). Primes have many special properties and play a critical role in number theory.
(See page 851)
|
2002 McGraw-Hill Higher Education