Thomas H. Cormen,
Dartmouth College
Charles E. Leiserson,
Massachusetts Institute of Technology
Ronald L. Rivest,
Massachusetts Institute of Technology
Clifford Stein,
Columbia University
| prime distribution function | π(n) specifies the number of primes that are less than or equal to n.
(See page 888)
|
 |
|
|
| primitive root | If ordn(g) = |Zn*|, then every element in Zn* is a power of g, modulo n, and we say that g is a primitive root or a generator of Zn*.
(See page 877)
|
|
|
|
| principal nth root of unity | ωn = e2πi/n is called the principal nth root of unity; all of the other complex nth roots of unity are powers of ωn.
(See page 831)
|
|
|
|
| priority queue | a data structure for maintaining a set S of elements, each with an associated value called a key.
(See page 138)
|
|
|
|
| probabilistic analysis | the use of probability in the analysis of problems. Most commonly, we use probabilistic analysis to analyze the running time of an algorithm.
(See page 92)
|
|
|
|
| probability | Pr{A} is the probability of the event A.
(See page 1101)
|
|
|
|
| probability density function | The function f(x) = Pr{X = x} is the probability density function of the random variable X.
(See page 1107)
|
|
|
|
| probability distribution | A probability distribution Pr{} on a sample space S is a mapping from events of S to real numbers such that the following probability axioms are satisfied:- Pr{A} ≥ 0 for any event A.
- Pr{S} = 1.
- Pr{A ∪ B} = Pr{A} + Pr{B} for any two mutually exclusive events A and B.
(See page 1101)
|
|
|
|
| probe | used to examine (or probe) the hash table in search of a particular item.
(See page 237)
|
|
|
|
| program counter | special memory location, keeps track of which instruction is to be executed next.
(See page 990)
|
|
|
|
| proper | A subgroup S′ of a group S is a proper subgroup if S′ ≠ S.
(See page 866)
|
|
|
|
| pseudorandom-number generator | a deterministic algorithm returning numbers that "look" statistically random
(See page 94)
|
|
|
|
| push | When a procedure is invoked, its information is pushed onto the stack. We call the operation PUSH(u, v) a push from u to v. if a push operation applies to some edge (u, v) leaving a vertex u, we also say that the push operation applies to u.
(See pages 162, 672)
|
|
|
|
| quadratic function | the worst-case running time can be expressed as an2 + bn + c for constants a, b, and c that again depend on the statement costs ci.
(See page 25)
|
|
|
|
| quadratic probing | uses a hash function of the form h(k, i) = (h'(k) + c1i + c2i2) mod m, where h' is an auxiliary hash function, c1 and c2 ≠ 0 are auxiliary constants, and i = 0, 1, ... m - 1.
(See page 239)
|
|
|
|
| quadratic residue | Let p be an odd prime. A number a ⊆ Zp* is a quadratic residue if the equation x2 = a (mod p) has a solution for the unknown x.
(See page 903)
|
|
|
|
| queries | operations on a dynamic set which simply return information about the set
(See page 198)
|
|
|
|
| queue | In a queue, the element deleted is always the one that has been in the set for the longest time: the queue implements a first-in, first-out, or FIFO, policy.
(See page 200)
|
|
|
|
| quotient | The value q = ⌊a/n⌋ is the quotient of the division.
(See page 851)
|
|
|
|
| random-access machine (RAM) | instructions are executed one after another, with no concurrent operations.
(See page 21)
|
|
|
|
| randomized ρ(n)-approximation algorithm | a randomized algorithm that achieves an approximation ratio of
ρ(n). In other words, a randomized approximation algorithm is like a deterministic approximation algorithm, except that the approximation ratio is for an expected value.
(See page 1039)
|
|
|
|
| randomly built binary search tree | defined on n keys as one that arises from inserting the keys in random order into an initially empty tree, where each of the n! permutations of the input keys is equally likely.
(See page 265)
|
|
|
|
| random-number generator | A function RANDOM(a, b) which returns an integer between a and b, inclusive, with each such integer being equally likely.
(See page 94)
|
|
|
|
| rank | an element's position in the linear order of the set. It is also the upper bound on the height of a node.
(See pages 302, 506)
|
|
|
|
| record | each number to be sorted is usually part of a collection of data called a record
(See page 123)
|
|
|
|
| recurrence | an equation or inequality that describes a function in terms of its value on smaller inputs.
(See page 62)
|
|
|
|
| recurrence equation | or recurrence, describes the overall running time on a problem of size n in terms of the running time on smaller inputs.
(See page 32)
|
|
|
|
| recursion tree | In a recursion tree, each node represents the cost of a single subproblem somewhere in the set of recursive function invocations.
(See page 67)
|
|
|
|
| recursion-tree method | A method for solving recurrences - that is, for obtaining asymptotic "Θ" or "O" bounds on the solution. The recursion-tree method converts the recurrence into a tree whose nodes represent the costs incurred at various levels of the recursion; we use techniques for bounding summations to solve the recurrence.
(See page 62)
|
|
|
|
| recursive | structure used in many useful algorithms: to solve a given problem, they call themselves recursively one or more times to deal with closely related sub-problems.
(See page 28)
|
|
|
|
| red-black properties | A binary search tree is a red-black tree if it satisfies the following red-black properties: 1. Every node is either red or black. 2. The root is black. 3. Every leaf (NIL) is black. 4. If a node is red, then both its children are black. 5. For each node, all paths from the node to descendant leaves contain the same number of black nodes.
(See page 271)
|
|
|
|
| red-black tree | a binary search tree with one extra bit of storage per node: its color, which can be either RED or BLACK.
(See page 271)
|
|
|
|
| reduction algorithm | a procedure that transforms any instance α of A into some instance β of B with the following characteristics:- The transformation takes polynomial time.
- The answers are the same. That is, the answer for α is "yes" if and only if the answer for β is also "yes."
(See page 970)
|
|
|
|
| rejected | an input that is not accepted
(See page 917)
|
|
|
|
| rejects | An algorithm A rejects a string x if A(x) = 0.
(See page 976)
|
|
|
|
| relabeled | When we call the operation RELABEL(u), we say that vertex u is relabeled. Note that when u is relabeled, Ef must contain at least one edge that leaves u, so that the minimization in the code is over a nonempty set. This property follows from the assumption that u is overflowing. Since e[u] > 0, we have e[u] = f(V, u) > 0, and hence there must be at least one vertex v such that f[v, u] > 0. But then, cf(u, v) = c(u, v) - f[u, v] = c(u, v) + f[v, u] > 0, which implies that (u, v) ∈ Ef. The operation RELABEL(u) thus gives u the greatest height allowed by the constraints on height functions.
(See page 673)
|
|
|
|
| relatively prime | Two integers a, b are relatively prime if their only common divisor is 1, that is if gcd(a, b) = 1.
(See page 854)
|
|
|
|
| relaxing | The process of relaxing an edge (u, v) consists of testing whether we can improve the shortest path to v found so far by going through u and, if so, updating d[v] and π[v].
(See page 585)
|
|
|
|
| release time | the time before which a task is not available to be processed.
(See page 403)
|
|
|
|
| remainder (or residue) | The value r = a mod n is the remainder (or residue) of the division. For any integer a and any positive integer n, the value a mod n is the remainder (or residue) of the quotient a / n: a mod n = a - ⌊a/n⌋n.
(See pages 51, 851)
|
|
|
|
| representative | some member of the set. In some applications, it doesn't matter which member is used as the representative; we only care that if we ask for the representative of the dynamic set twice without modifying the set between the requests, we get the same answer both times. In other applications, there may be a prespecified rule for choosing the representative, such as choosing the smallest member in the set (assuming, of course, that the elements can be ordered).
(See page 498)
|
|
|
|
| residual capacity | The amount of additional flow we can push from u to v before exceeding the capacity of c(u, v) is the residual capacity of (u, v), given by cf(u, v) = c(u, v) - f(u, v). The maximum amount by which we can increase the flow on each edge in an augmenting path p is the residual capacity of p, given by cf = min{cf(u, v) : (u, v) is on p}.
(See page 651)
|
|
|
|
| residual network | Given a flow network G = (V, E) and a flow of f, the residual network of G induced by f is Gf = (V, Ef), where Ef = {(u, v) ∈ V x V : cf(u, v) > 0}. Each edge of the residual network, or residual edge, can admit a flow that is greater than 0.
(See page 652)
|
|
|
|
| respects | A cut respects a set A of edges if no edge in A crosses the cut.
(See page 563)
|
|
|
|
| reweighting | a technique which works as follows: If all edge weights w in a graph
G = (V, E) are nonnegative, we can find shortest paths between all pairs of vertices by running Dijkstra's algorithm once from each vertex; with the Fibonacci-heap min-priority queue, the running time of this all-pairs algorithm is O(V2 lg V + VE). If G has negative-weight edges but no negative-weight cycles, we simply compute a new set of nonnegative edge weights that allows us to use the same method.
(See page 636)
|
|
|
|
| right-converted | We say that a binary search tree T1 can be right-converted to binary search tree T2 if it is possible to obtain T2 from T1 via a series of calls to RIGHT-ROTATE.
(See page 279)
|
|
|
|
| right spine | Symmetrically, the right spine of T is the path from the root consisting of only right edges.
(See page 298)
|
|
|
|
| rotation | We change the pointer structure through rotation, a local operation in a search tree that preserves the binary-search-tree property.
(See page 277)
|
|
|
|
| row rank | of A is the size of the largest set of linearly independent rows of A.
(See page 731)
|
|
|
|
| row vector | the transpose of a column vector.
(See page 726)
|
|
|
|
| rule of product | the number of ways to choose an ordered pair is the number of ways to choose the first element times the number of ways to choose the second element. That is, if A and B are two finite sets, then
|A x B| = |A| · |B|.
(See page 1095)
|
|
|
|
| rule of sum | the number of ways to choose an element from one of two disjoint sets is the sum of the cardinalities of the sets. That is, if A and B are two finite sets with no members in common, then |A ∪ B| = |A| + |B|.
(See page 1094)
|
|
|
|
| running time | of an algorithm on a particular input is the number of primitive operations or "steps" executed.
(See page 23)
|
|
|
|
| safe edge | A greedy strategy is captured by the following "generic" algorithm, which grows the minimum spanning tree one edge at a time. The algorithm manages a set of edges A, maintaining the following loop invariant: Prior to each iteration, A is a subset of some minimum spanning tree. At each step, an edge (u, v) is determined which can be added to A without violating this invariant, in the sense that A ∪{(u, v)} is also a subset of a minimum spanning tree. Such an edge is called a safe edge for A, since it can be safely added to A while maintaining the invariant.
(See page 562)
|
|
|
|
| sample space | We define probability in terms of a sample space S, which is a set whose elements are called elementary events. Each elementary event can be viewed as a possible outcome of an experiment.
(See page 1100)
|
|
|
|
| satellite data | An object may contain satellite data, which are carried around in other object fields but are otherwise unused by the set implementation.
(See page 197)
|
|
|
|
| satisfiable | A boolean formula is satisfiable if there is some assignment of the values 0 and 1 to its variables that causes it to evaluate to 1. A one-output boolean combinational circuit is satisfiable if it has a satisfying assignment. A formula with a satisfying assignment is a satisfiable formula.
(See pages 967, 988)
|
|
|
|
| satisfying assignment | for a boolean combinational circuit it is a truth assignment that causes the output of the circuit to be 1. For a boolean formula it is a truth assignment that causes it to evaluate to 1.
(See page 988)
|
|
|
|
| saturating push | It is a saturating push if edge (u, v) becomes saturated (cf(u, v) = 0 afterward); otherwise, it is a nonsaturating push. If an edge is saturated, it does not appear in the residual network.
(See page 672)
|
|
|
|
| scalar flow product | Let f be a flow in a network, and let α be a real number. The scalar flow product, denoted αf, is a function from V x V to R defined by (αf)(u, v) = α · f(u, v).
(See page 650)
|
|
|
|
| scalar multiple | If λ is a number and A = (aij) is a matrix, then λA = (λaij) is the scalar multiple of A obtained by multiplying each of its elements by λ.
(See page 729)
|
2002 McGraw-Hill Higher Education