Thomas H. Cormen,
Dartmouth College
Charles E. Leiserson,
Massachusetts Institute of Technology
Ronald L. Rivest,
Massachusetts Institute of Technology
Clifford Stein,
Columbia University
| decided in polynomial time | A language L is decided in polynomial time by an algorithm A if there is a constant k such that for any length-n string x ∈ {0,1}*, the algorithm correctly decides whether x ∈ L in time O(nk). Thus, to accept a language, an algorithm need only worry about strings in L, but to decide a language, it must correctly accept or reject every string in {0,1}*.
(See page 976)
|
 |
|
|
| decision problems | the answer is simply "yes" or "no" (or, more formally, "1" or "0")
(See page 969)
|
|
|
|
| degeneracy | phenomenon which occurs when an iteration leaves the objective value unchanged.
(See page 802)
|
|
|
|
| depth | of a wire is defined as follows: An input wire of a comparison network has depth 0. Now, if a comparator has two input wires with depths dx and dy, then its output wires have depth max(dx, dy) + 1. Because there are no cycles of comparators in a comparison network, the depth of a wire is well defined, and we define the depth of a comparator to be the depth of its output wires. The depth of a comparison network is the maximum depth of an output wire or, equivalently, the maximum depth of a comparator. If each comparator takes one time unit to produce its ouput value, and if network inputs appear at time 0, a comparator at depth d produces its outputs at time d; the depth of the network therefore equals the time for the network to produce values at all of its output wires.
(See page 707)
|
|
|
|
| diagonal matrix | has aij = 0 whenever i ≠ j. Because all of the off-diagonal elements are zero, the matrix can be specified by listing the elements along the diagonal.
(See page 726)
|
|
|
|
| dictionary | A dynamic set that supports the operations to insert elements into, delete elements from, and test membership in a set.
(See page 197)
|
|
|
|
| digital signature | σ for the message M′ using key SA and the equation σ = SA(M′).
(See page 883)
|
|
|
|
| direct-address table | To represent the dynamic set, we use an array, or direct-address table, denoted by T[0..m - 1], in which each position, or slot, corresponds to a key in the universe U.
(See page 222)
|
|
|
|
| discharged | An overflowing vertex u is discharged by pushing all of its excess flow through admissible edges to neighboring vertices, relabeling u as necessary to cause edges leaving u to become admissible.
(See page 683)
|
|
|
|
| discrete | A probability distribution is discrete if it is defined over a finite or countably infinite sample space.
(See page 1101)
|
|
|
|
| Discrete Fourier Transform (DFT) | The vector y = (y0, y1, . . . , yn - 1) is the Discrete Fourier Transform (DFT) of the coefficient vector a = (a0, a1, . . . , an - 1). We also write
y = DFTn(a).
(See page 833)
|
|
|
|
| disjoint-set forest | each member points only to its parent. The root of each tree contains the representative and is its own parent.
(See page 505)
|
|
|
|
| disjunctive normal form (DNF) | an OR of AND's
(See page 1000)
|
|
|
|
| divide-and-conquer | typical approach followed by recursive algorithms: they break the problem into several subproblems that are similar to the original problem but smaller in size, solve the subproblems recursively, and then combine these solutions to create a solution to the original problem.
(See page 28)
|
|
|
|
| divides | d | a (read "d divides a") means that a = kd for some integer k. Every integer divides 0. If a > 0 and d | a, then |d| ≤ |a|.
(See page 850)
|
|
|
|
| division method | In the division method for creating hash functions, we map a key k into one of m slots by taking the remainder of k divided by m. That is, the hash function is
h(k) = k mod m.
(See page 230)
|
|
|
|
| divisor | If d | a and d ≥ 0, d is a divisor of a. Note that d | a if and only if -d | a, so that no generality is lost by defining the divisors to be nonnegative, with the understanding that the negative of any divisor of a also divides a. A divisor of an integer a is at least 1 but not greater than |a|.
(See page 850)
|
|
|
|
| double hashing | involves the use of two hash functions, h1(key) and h2(key). h1, which is known as the primary hash function, is first used to determine the position at which the record should be placed. If that position is occupied, the rehash function rh(i, key) = (i + h2(key)) % tablesize is used successively until an empty location is found. As long as h2(key1) does not equal h2(key2), records with keys key1 and key2 do not compete for the same set of locations.
(See page 240)
|
|
|
|
| doubly linked list | a object with a key field and two other pointer fields: next and prev.
(See page 204)
|
|
|
|
| d-regular | We say that a bipartite graph G = (V, E), where V = L ∪ R, is d-regular if every vertex v ∈ V has degree exactly d. Every d-regular bipartite graph has a matching of cardinality |L| by arguing that a minimum cut of the corresponding flow network has capacity |L|.
(See page 669)
|
|
|
|
| dynamic | the type of sets manipulated by algorithms. They can grow, shrink, or otherwise change over time.
(See page 197)
|
|
|
|
| dynamic graph data structures | support various queries while allowing the structure of a graph to change through operations that insert or delete vertices or edges. Examples of the queries that are supported include vertex connectivity, edge connectivity, minimum spanning trees, biconnectivity, and transitive closure.
(See page 433)
|
|
|
|
| dynamic trees | maintain a forest of disjoint rooted trees. Each edge in each tree has a real-valued cost. Support queries to find parents, roots, edge costs, and the minimum edge cost on a path from a node up to a root. May be manipulated by cutting edges, updating all edge costs on a path from a node up to a root, linking a root into another tree, and making a node the root of the tree it appears in. Used in some of the asymptotically fastest network-flow algorithms.
(See page 432)
|
|
|
|
| early | a property of a task in a schedule if it finishes before or on its scheduled deadline.
(See page 399)
|
|
|
|
| early-first form | An arbritrary schedule in which the early tasks precede the late tasks.
(See page 399)
|
|
|
|
| ε-dense | A graph G = (V, E) is ε-dense if |E| = Θ(V1+ε) for some constant ε inthe range 0 < ε ≤ 1.
(See page 641)
|
|
|
|
| edge connectivity | of an undirected graph is the minimum number k of edges that must be removed to disconnect the graph.
(See page 664)
|
|
|
|
| edit distance | from x to y it is the cost of the least expensive operation sequence that transforms x to y.
(See page 366)
|
|
|
|
| Edmonds-Karp algorithm | The bound on FORD-FULKERSON can be improved if we implement the computation of the augmenting path p with a breadth-first search, that is, if the augmenting path is a shortest path from s to t in the residual network, where each edge has unit distance (weight). We call the FORD-FULKERSON method so implemented the Edmonds-Karp algorithm.
(See page 661)
|
|
|
|
| elementary insertion | procedure which inserts all items in table[T] into new-table or inserts x into table[T]
(See page 418)
|
|
|
|
| ellipsoid algorithm | The first polynomial-time algorithm for linear programming.
(See page 776)
|
|
|
|
| empty | the stack contains no elements, top[S] = 0
(See page 201)
|
|
|
|
| empty string | zero-length, denoted ε
(See page 907)
|
|
|
|
| encoding | of a set S of abstract objects is a mapping e from S to the set of binary strings. The codomain of e need not be binary strings over a finite alphabet having at least 2 symbols will do.
(See page 973)
|
|
|
|
| equality constraints | A linear program not in standard form because it has an equal sign rather than a less-than-or-equal-to.
(See page 778)
|
|
|
|
| escape problem | Given m ≤ n2 starting points (x1, y1), (x2, y2), . . . , (xm, ym) in the grid, the escape problem is to determine whether or not there are m vertex-disjoint paths from the starting points to any m different points on the boundary.
(See page 692)
|
|
|
|
| essential term | one of the eight terms appearing on the right-hand side of one of the equations (28.9)-(28.12).
(See page 738)
|
|
|
|
| Euler tour | of a connected, directed graph G = (V, E) is a cycle that traverses each edge of G exactly once, although it may visit a vertex more than once.
(See page 966)
|
|
|
|
| evaluating | operation consists of computing the value of A(x0) on the polynomial
A(x) at a given point x0.
(See page 824)
|
|
|
|
| event | a subset of the sample space S.
(See page 1100)
|
|
|
|
| excess flow | We call the total net flow at a vertex u the excess flow into u, given by e(u) = f(V, u).
(See page 669)
|
|
|
|
| expand | When an item is inserted into a full table, the expand function allocates a new table with more slots than the old table had. An example of expansion occurs when the procedure determines that a table T is full, then inserts all items in T into a new table, frees T, renames the new table to T, then inserts x into T.
(See page 417)
|
|
|
|
| exponential height | We denote the height of a randomly built binary search on n keys by Xn, and we define the exponential height Yn = 2Xn.
(See page 265)
|
|
|
|
| factor | to decompose into a product of primes.
(See page 896)
|
|
|
|
| fair coin | one for which the probability of obtaining a head is the same as the probability of obtaining a tail.
(See page 1101)
|
|
|
|
| fan-out | the number of element inputs fed by a wire.
(See page 988)
|
|
|
|
| feasible | a linear program which has feasible solutions.
(See page 778)
|
|
|
|
| feasible region | If we graph the constraints in the (x1, x2)-Cartesian coordinate system, the set of feasible solutions forms a convex region in the two-dimensional space called the feasible region.
(See page 773)
|
|
|
|
| feasible solution | in linear programming, any vector x that satisfies Ax ≤ b, or to determine that no feasible solution exists. A setting of variables that satisfies all the constraints.
(See pages 601, 773)
|
|
|
|
| Fibonacci heap | a collection of min-heap-ordered trees. The trees in a Fibonacci heap are not constrained to be binomial trees. Unlike trees within binomial heaps, which are ordered, trees within Fibonacci heaps are rooted but unordered.
(See page 477)
|
|
|
|
| Fibonacci numbers | The Fibonacci numbers are defined by the following recurrence:
F0 = 0 ,
F1 = 1 ,
Fi = Fi-1 + Fi-2 for i ≥ 2.Thus, each Finonacci number is the sum of the two previous ones, yielding the sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... .
(See page 56)
|
|
|
|
| final-state function | A finite automaton M induces a function φ, called the final-state function, from Ε* to Q such that φ(w) is the state M ends up in after scanning the string w. Thus, M accepts a string w if and only if φ(w) ∈ A.
(See page 917)
|
|
|
|
| find path | For the disjoint-set forest, three disjoint-set operations are performed as follows: A MAKE-SET operation simply creates a tree with just one node. A FIND-SET operation is performed by following parent pointers until the root of the tree is found. The nodes visited on this path toward the root constitute the find path.
(See page 506)
|
|
|
|
| finite group | If a group (S, ⊕) satisfies |S| < ∞, then it is a finite group.
(See page 862)
|
|
|
|
| first-fit | The first-fit heuristic takes each object in turn and places it into the first bin that can accommodate it.
(See page 1050)
|
|
|
|
| flow-network | A flow-network G = (V, E) is a directed graph in which each edge (u, v) ∈ E has a nonnegative capacity c(u, v) ≥ 0.
(See page 644)
|
|
|
|
| flow sum | The flow sum f1 + f2 is the function from V x V to R defined by (f1 + f2)(u, v) = f1(u, v) + f2(u, v) for all u, v ∈ V.
(See page 650)
|
|
|
|
| Floyd-Warshall algorithm | algorithm resulting from use of a different dynamic-programming formulation to solve the all-pairs shortest-patsh problem on a directed graph G = (V, E). Negative-weight edges may be present, but it assumes that there are no negative-weight cycles.
(See page 629)
|
|
|
|
| fractional knapsack problem | This is similar to the 0-1 knapsack problem but the thief can take fractions of items, rather than having to make a binary (0-1) choice for each item.
(See page 382)
|
|
|
|
| free list | singly linked list containing free objects. The free list uses only the next array, which stores the next pointers within the list. The head of the free list is held in the global variable free. When the dynamic set represented by linked list L is nonempty, the free list may be intertwined with list L. Each object in the representation is either in list L or in the free list, but not in both. The free list is a stack: the next object allocated is the last one freed.
(See page 211)
|
|
|
|
| full column rank | An m x n matrix has full column rank if its rank is n.
(See page 731)
|
2002 McGraw-Hill Higher Education