Thomas H. Cormen,
Dartmouth College
Charles E. Leiserson,
Massachusetts Institute of Technology
Ronald L. Rivest,
Massachusetts Institute of Technology
Clifford Stein,
Columbia University
| trim | To trim a list L by δ means to remove as many elements from L as possible, in such a way that if L′ is the resulting of trimming L, then for every element y that was removed from L, there is an element z still in L′ that approximates y.
(See page 1045)
|
 |
|
|
| trivial divisors | Every integer a is divisible by the trivial divisors 1 and a.
(See page 851)
|
|
|
|
| truth assignment | for a boolean combinational circuit is a set of boolean input values. For a boolean formula φ it is a set of values for the variables of φ.
(See page 988 & 996)
|
|
|
|
| truth table | describes the operation of the logic gates, and of any boolean combinational element. Gives the outputs of the combinational element for each possible setting of the inputs.
(See page 987)
|
|
|
|
| two-pass method | used by the FIND-SET procedure, it makes one pass up the find path to find the root, and it makes a second pass back down the find path to update each node so that it points directly to the root.
(See page 508)
|
|
|
|
| unbounded | a linear program which has some feasible solutions but does not have a finite optimal objective value.
(See page 778)
|
|
|
|
| underdetermined | If the number of equations is less than the number n of unknowns - or, more generally, if the rank of A is less than n. An underdetermined system typically has infinitely many solutions, although it may have no solutions at all if the equations are inconsistent.
(See page 743)
|
|
|
|
| underflows | If an empty stack is popped, we say the stack underflows, which is normally an error.
(See page 201)
|
|
|
|
| uniform hashing | generalizes the notion of simple uniform hashing to the situation in which the hash function produces not just a single number, but a whole probe sequence. Uniform hashing assumes that each key is equally likely to have any of the m! permutations of (0, 1, ... , m - 1) as its probe sequence.
(See page 239)
|
|
|
|
| uniform probability distribution | If S is finite and every elementary event s ∈ S has probability Pr{s} = 1 / |S|, then we have the uniform probability distribution on S. In such a case the experiment is often described as "picking an element of S at random."
(See page 1101)
|
|
|
|
| uniform random permutation | Each of the possible n! permutations appears with equal probability. Every permutation of the numbers 1 through n is equally likely to be produced.
(See pages 93 & 101)
|
|
|
|
| union by rank | A heuristic to improve the running time. Similar to the weighted-union heuristic used with the linked-list representation. The idea is to make the root of the tree with fewer nodes point to the root of the tree with more nodes. Rather than explicitly keeping track of the size of the subtree rooted at each node, an approach that eases the analysis is used. In each node, a rank is maintained that is an upper bound on the height of the node. In union by rank, the root with smaller rank is made to point to the root with larger rank during a UNION operation.
(See page 506)
|
|
|
|
| unit | The integer 1 is a unit and is neither prime nor composite. Similarly, the integer 0 and all negative integers are neither prime nor composite.
(See page 851)
|
|
|
|
| unit lower-triangular | A lower-triangular matrix is unit lower-triangular if it has all 1's along the diagonal.
(See page 728)
|
|
|
|
| unit-time task | a job, such as a program to be run on a computer, that requires exactly one unit of time to complete.
(See page 399)
|
|
|
|
| unit upper-triangular | An upper-triangular matrix is unit upper-triangular if it has all 1's along the diagonal.
(See page 727)
|
|
|
|
| unit vector | ei - the vector whose ith element is 1 and all of whose other elements are 0.
(See page 726)
|
|
|
|
| universal hashing | Using this method, enough of the functions work well for any random input set that if one function is chosen randomly from the class, it is likely to perform well on any input set that is actually presented.
(See page 232)
|
|
|
|
| unsorted list | If the list is unsorted, the elements can appear in any order.
(See page 204)
|
|
|
|
| upper-bound property | We always have d[v] ≥ δ(s, v) for all vertices v ∈ V, and once d[v] achieves the value of δ(s, v), it never changes.
(See page 587)
|
|
|
|
| upper-triangular matrix | one for which uij = 0 if i > j. All entries below the diagonal are zero.
(See page 727)
|
|
|
|
| variance | of a random variable X with mean E[X] is Var[X] = E[(X - E[X])2] = E[X2 - 2XE[X] + E2[X]] = E[X2] - 2E2[X] + E2[X] = E[X2] - E2[X].
(See page 1110)
|
|
|
|
| vector | a one-dimensional array of numbers.
(See page 726)
|
|
|
|
| verification algorithm | defined as being a two-argument algorithm A, where one argument is an ordinary input string x and the other is a binary string y called a certificate.
(See page 980)
|
|
|
|
| verifies | A two-argument algorithm A verifies an input string x if there exists a certificate y such that A(x, y) = 1.
(See page 980)
|
|
|
|
| vertex-cover | of an undirected graph G = (V, E) is a subset V′ ⊆ V such that if
(u, v) ∈ E, then u ∈ V′ or v ∈ V′ (or both). That is, each vertex "covers" its incident edges, and a vertex cover for G is a set of vertices that covers all the edges in E. The vertex cover of an undirected graph G = (V, E) is a subset V′ ⊆ V such that if (u, v) is an edge of G, then either u ∈ V′ or
v ∈ V′ (or both). The size of a vertex cover is the number of vertices in it.
(See page 1006)
|
|
|
|
| vertex cover problem | to find a vertex cover of minimum size in a given undirected graph. We call such a vertex cover an optimal vertex cover. this problem is the optimization version of an NP-complete decision problem.
(See page 1024)
|
|
|
|
| weak duality | states that any feasible solution to the primal linear program has a value no greater than that of any feasible solution to the dual linear program.
(See page 805)
|
|
|
|
| weight | of path p = ⟨v0, v1, . . . , vk⟩ is the sum of the weights of its constituent edges. The weight of a cut is the number of edges crossing the cut.
(See pages 580, 1043)
|
|
|
|
| weighted-union heuristic | each list includes the length of the list and we always append the smaller list onto the longer, with ties broken arbitrarily.
(See page 503)
|
|
|
|
| widget | a piece of a graph that enforces certain properties.
(See page 1008)
|
|
|
|
| wire | transmits a value from place to place. Wires can connect the output of one comparator to the input of another, but otherwise they are either network input wires or network output wires.
(See page 705)
|
|
|
|
| worst-case running time | the longest running time for any input of size n.
(See page 26)
|
|
|
|
| zero matrix | a matrix whose every entry is 0.
(See page 726)
|
|
|
|
| zero-one principle | if a sorting network works correctly when each input is drawn from the set {0, 1}, then it works correctly on arbitrary input numbers. (The numbers can be integers, reals, or, in general, any set of values from any linearly ordered set.)
(See page 709)
|
|
|
|
| weighted graphs | graphs for which each edge has an associated weight, typically given by a weight function w : E → R.
(See page 529)
|
2002 McGraw-Hill Higher Education