Student Center | Instructor's Center | Introduction to Algorithms | Home

Introduction to Algorithms, 2/e

Thomas H. Cormen, Dartmouth College
Charles E. Leiserson, Massachusetts Institute of Technology
Ronald L. Rivest, Massachusetts Institute of Technology
Clifford Stein, Columbia University

Glossary A-B

(binary) heap data structure	an array object that can be viewed as a nearly complete binary tree (See page 125)



ρ(n)-approximation algorithm	an algorithm that achieves an approximation ratio of ρ(n). (See page 1022)



(discrete) random variable	X is a function from a finite or countably infinite sample space S to the real numbers. It associates a real number with each possible outcome of an experiment, which allows us to work with the probability distribution induced on the resulting set of numbers. (See page 1106)



(euclidean) norm	\|\|x\|\| of a vector x of size n is defined by \|\|x\|\| = (x₁² + x₂² + · · · + x_n²)^1/2 = (x^Tx)^1/2. Thus, the norm of x is its length in n-dimensional euclidean space. (See page 730)



(formula) satisfiability	formulate the problem in terms of the language SAT as follows. An instance of SAT is a boolean formula φ composed of n boolean variables: x₁, x₂, . . . , x_n; m boolean connectives: any boolean function with one or two inputs and one output, such as ^ (AND), V (OR), ¬ (NOT), → (implication), ↔ (if and only if); and parentheses. (Without loss of generality, we assume that there are no redundant parentheses, i.e., there is at most one pair of parentheses per boolean connective.) (See page 996)



(mutually) independent	We say that the events of the collection are (mutually) independent if every k-subset A_i₁, A_i₂, . . . , A_{i_k} of the collection, where 2 ≤ k ≤ n and 1 ≤ i₁ < i₂ < · · · < i_k ≤ n, satisfies Pr{A_i₁ ∩ A_i₂ ∩ · · · ∩ A_{i_k}} = Pr{A_i₁}Pr{A_i₂} · · · Pr{A_{i_k}}. (See page 1103)



0-1 integer-programming problem	Given an integer m x n matrix A and an integer m-vector b, we ask whether there is an integer n-vector x with elements in the set {0,1} such that Ax ≤ b. (See page 1017)



0-1 knapsack problem	A thief robbing a store finds n items: the ith item is worth v_i dollars and weighs w_i pounds, where v_i and w_i are integers. He wants to take as valuable a load as possible, but he can carry at most W pounds in his knapsack for some integer W. Which items should he take? (This is called the 0-1 knapsack problem because each item must either be taken or left behind; the thief cannot take a fractional amount of an item or take an item more than once. (See page 382)



2-3-4 tree	The simplest B-tree. Occurs when t = 2. Every internal node then has either 2, 3, or 4 children. (See page 439)



3-conjunctive normal form (3-CNF)	A boolean formula is in this form if each clause has exactly three distinct literals. (See page 999)



a-balanced	property of a given node x if size[left[x]] ≤ α · size[x] and size[right[x]] ≤ α · size[x]. The tree as a whole is α-balanced if every node in the tree is α-balanced. (See page 427)



abelian group	If a group (S, ⊕) satisfies the commutative law, then it is an abelian group. (See page 862)



abstract problem	defined for Q to be a binary relation on a set I of problem instances and a set S of problem solutions. (See page 972)



accepted	The language accepted by an algorithm A is the set of strings L = {x ∈ {0,1}* : A(x) = 1}, that is, the set of strings that the algorithms accepts. (See page 976)



accepted in polynomial time	A language L is accepted in polynomial time by an algorithm A if it is accepted by A and if in addition there is a constant k such that for any length-n string x ∈ L, algorithm A accepts x in time O(n^k). (See page 976)



accepts	An algorithm A accepts a string x ∈ {0, 1}* if, given input x, the algorithm's output A(x) is 1. (See page 976)



accounting method	In the accounting method of amortized analysis, we assign differing charges to different operations, with some operations charged more or less than they actually cost. (See page 410)



activity-selection problem	to select a maximum-size subset of mutually compatible activities. (See page 371)



admissible edge	If G = (V, E) is a flow network with source s and sink t, f is a preflow in G, and h is a height function, then we say that (u, v) is an admissible edge if c_f(u, v) > 0 and h(u) = h(v) + 1. Otherwise, (u, v) is inadmissible. (See page 681)



admissible network	is G_{f, h} = (V, E_f,h), where E_f,h is the set of admissible edges. The admissible network consists of those edges through which flow can be pushed. (See page 681)



aggregate analysis	for all n a sequence of n operations takes worst-case time T(n) in total. (See page 406)



algorithm	any well-defined computational procedure that takes some value, or set of values, as *input* and produces some value, or set of values, as *output. A sequence of computational steps that transform the input into the output. (See* page 5)



alphabet	Ε is a finite set of symbols. (See page 975)



amortized analysis	In an amortized analysis, the time required to perform a sequence of data-structure operations is averaged over all the operations performed. Guarantees the average performance of each operation in the worst case. (See page 405)



amortized cost	average cost, T(n)/n. Applies to each operation, even when there are several types of operations in the sequence. The amount charged to an operation (See page 406, 410)



Analyzing an algorithm	predicting the resources that the algorithm requires. (See page 21)



AND & OR gates	each gate takes two binary inputs x and y and produces a single binary output z (See page 987)



approximation algorithm	an algorithm that returns near-optimal solutions (See page 1022)



approximation errors	η = Ac - y is the size-m vector of approximation errors. (See page 763)



approximation ratio	a randomized algorithm for a problem has an approximation ratio of ρ(n) if, for any input of size n, the exptected cost C of the solution produced by the randomized algorithm is within a factor of ρ(n) of the cost C* of an optimal solution: (See page 1039)



approximation scheme	for an optimization problem is an approximation algorithm that takes as input not only an instance of the problem, but also a value ε > 0 such that for any fixed ε, the scheme is a (1 + ε)-approximation algorithm. (See page 1023)



arbitrage	the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. (See page 615)



asymptotically larger	f(n) is asymptotically larger than g(n) if f(n) = ω(g(n)). (See page 49)



asymptotically positive	a function that is positive for all sufficiently large n



asymptotically smaller	We say that f(n) is asymptotically smaller than g(n) if f(n) = o(g(n)). (See page 49)



asymptotically tight bound	For all n ≥ n₀, the function f(n) is equal to g(n) to within a constant factor. We say that g(n) is an asymptotically tight bound for f(n). (See page 43)



augmenting path	Given a flow network G = (V, E) and a flow f, an augmenting path p is a simple path from s to t in the residual network G_f. By the definition of the residual network, each edge (u, v) on an augmenting path admits some additional positive flow from u to v without violating the capacity constraint on the edge. For the Hopcraft-Karp bipartite matching algorithm we say that a simple path P in G is an augmenting path with respect to M if it starts at an unmatched vertex in L, ends at an unmatched vertex in R, and its edges belong alternately to M and E - M. (This definition of an augmenting path is related to, but different from, an augmenting path in a flow network.) (See page 654)



auxiliary hash function	refers to an ordinary hash function h': U → {0, 1, ... , m - 1). (See page 239)



auxiliary linear program	finds a slack form for which the basic solution is feasible. (See page 811)



average-case	expected running time of an algorithm. (See page 26)



AVL tree	An AVL tree is a binary tree that is height balanced (See page 296)



*B-tree**	Another common variant on a B-tree. Requires each internal node to be at least 2/3 full, rather than at least half full, as a B-tree requires. (See page 439)



B+-tree	A common variant on a B-tree. Stores all the satellite information in the leaves and stores only keys and child pointers in the internal nodes, thus maximizing the branching factor of the internal nodes. (See page 438)



balanced	By constraining the way nodes can be colored on any path from the root to a leaf, red-black trees ensure that no such path is more than twice as long as any other, so that the tree is approximately balanced. (See page 271)



base-a pseudoprime	n is a base-a pseudoprime if n is compositie and a^n-1 ≡ 1 (mod n). (See page 889)



basic feasible solution	a basic solution which is also feasible. (See page 792)



basic solution	set all the (nonbasic) variables on the right-hand side to 0 and then compute the values of the (basic)variables on the left-hand side. (See page 792)



basic variables	the variables on the left-hand side of an equality. (See page 782)



Bernoulli trial	defined as an experiment with only two possible outcomes: success, which occurs with probability p, and failure, which occurs with probability q = 1 - p. When we speak of Bernoulli trials collectively, we mean that the trials are mutually independent and, unless we specifically say otherwise, that each has the same probability p for success. Two important distributions arise from Bernoulli trials: the geometric distribution and the binomial distribution. (See page 1112)



binary-search-tree property	Let x be a node in a binary search tree. If y is a node in the left subtree of x, then key[y] ≤ key[x]. If y is a node in the right subtree of x, then key[x] ≤ key[y]. (See page 254)



birthday paradox	How many people must there be in a room before there is a 50% chance that two of them were born on the same day of the year? (See page 106)



bitonic	A sequence is bitonic if it monotonically increases and then monotonically decreases, or if it can be circularly shifted to monotonically increase and then monotonically decrease. (See page 618)



bitonic sequence	a sequence that monotonically increases and then monotonically decreases, or can be circularly shifted to become monotonically increasing and then monotonically decreasing. (See page 712)



bitonic sorter	a network that sorts bitonic sequences. (See page 715)



bitonic tours	Tours that start at the leftmost point, go strictly left to right to the rightmost point, and then go strictly right to left back to the starting point. (See page 364)



bit-reversal permutation	swaps elements whose indices have binary representations that are the reverse of each other. (See page 425)



bit vector	an array of bits (See page 222)



black-height	We call the number of black nodes on any path from, but not including, a node x down to a leaf the black-height of the node, denoted bh(x). (See page 274)



B-tree	a balanced search tree designed to work well on magnetic disks or other direct-access secondary storage devices. Similar to red-black trees, but they are better at minimizing disk I/O operations. Similar to red-black trees in that every n-node B-tree has height O(lg n), although the height of a B-tree can be considerably less than that of a red-black tree because its branching factor can be much larger. Differ from red-black trees in that B-tree nodes may have many children, from a handful to thousands. A B-tree T is a rooted tree (whose root is root[T]) having properties. See page 438-439 for a listing of properties. (See page 434)



Bland's rule	breaks a tie caused by a cycle by always choosing the variable with the smallest index. (See page 803)



Boole's inequality	For any finite or countably infinite sequence of events A₁, A₁, . . . , Pr{A₁ ∪ A₂ ∪ · · ·} ≤ Pr{A₁} + Pr{A₂} + · · ·. (See page 1105)

2002 McGraw-Hill Higher Education
Any use is subject to the Terms of Use and Privacy Policy.
McGraw-Hill Higher Education is one of the many fine businesses of The McGraw-Hill Companies.