Thomas H. Cormen,
Dartmouth College
Charles E. Leiserson,
Massachusetts Institute of Technology
Ronald L. Rivest,
Massachusetts Institute of Technology
Clifford Stein,
Columbia University
| scaling | A scaling algorithm solves a problem by initially considering only the highest order bit of each relevant input value (such as an edge weight). It then refines the initial solution by looking at the two highest-order bits. It progressively looks at more and more high-order bits, refining the solution each time, until all bits have been considered and the correct solution has been computed.
(See page 616)
|
 |
|
|
| schedule | Given a finite set S of unit-time tasks, a schedule for S is a permutation of S specifying the order in which these tasks are to be performed.
(See page 399)
|
|
|
|
| secondary clustering | a milder form of clustering in which different keys that hash to the same value follow the same rehash path
(See page 240)
|
|
|
|
| secondary storage | computer memory based on magnetic disks. The amount of such secondary storage often exceeds the amount of primary memory by at least two orders of magnitude.
(See page 435)
|
|
|
|
| second-best minimum spanning tree | Let Τ be the set of all spanning trees of G, and let T' be a minimum spanning tree of G. Then, the second-best minimum spanning tree is a spanning tree T such that w(T) = minT'' ∈ Τ - {T'}{w(T'')}.
(See page 575)
|
|
|
|
| selection point | can be specified formally as follows: Input: A set A of n (distinct) numbers and a number i, with 1 ≤ i ≤ n. Output: The element of x ∈ A that is larger than exactly i - 1 other elements of A.
(See page 183)
|
|
|
|
| selector vertices | The only other vertices in V′ other than those of widgets are selector vertices s1, s2, . . . , sk. We use edges incident on selector vertices in G′ to select the k vertices of the cover in G.
(See page 1009)
|
|
|
|
| sentinel | a dummy object that allows us to simplify boundary conditions. For example, suppose that we provide with list L an object nil[L] that represents NIL but has all the fields of the other list elements. Whenever we have a reference to NIL in list code, we replace it by a reference to the sentinel nil[L].
(See page 206)
|
|
|
|
| short circuiting | describes a property of the boolean operators "and" and "or". When we evaluate the expression "x and y" we first evaluate x. If x evaluates to FALSE, then the entire expression cannot evaluate to TRUE, and so we do not evaluate y. If, on the other hand, x evaluates to TRUE, we must evaluate y to determine the value of the entire expression. Similarly, in the expression "x or y" we evaluate the expression y only if x evaluates to FALSE.
(See page 20)
|
|
|
|
| shortest path | A shortest path from vertex u to vertex v is defined as any path p with weight w(p) = δ(u, v).
(See page 580)
|
|
|
|
| shortest-paths tree | rooted at s, it is a directed subgraph G' = (V', E'), where V' ⊆ V and
E' ⊆ E, such that- V' is the set of vertices reachable from s in G,
- G' forms a rooted tree with root s, and
- for all v ∈ V', the unique simple path from s to v to G' is a shortest path from s to v in G.
(See page 584)
|
|
|
|
| simple uniform hashing | the assumption that any given element is equally likely to hash to any of the m slots, independently of where any other element has hashed to.
(See page 226)
|
|
|
|
| simplex | If we have three variables, then each constraint is described by a half-space in three-dimensional space. The feasible region formed by the intersection of these half-spaces is called a simplex.
(See page 775)
|
|
|
|
| simplex algorithm | takes as input a linear program and returns an optimal solution.
(See page 775)
|
|
|
|
| single-source shortest-paths problem | given a graph G = (V, E), we want to find a shortest path from a given source vertex s ∈ V to each vertex v ∈ V.
(See page 581)
|
|
|
|
| singly linked list | If a list is singly linked, we omit the prev pointer in each element.
(See page 204)
|
|
|
|
| singular value decomposition | SVD - an m x n matrix A is factored into A = Q1ΕQ2T, where Ε is an
m x n matrix with nonzero values only on the diagonla, Q1 is m x m with mutually orthonormal columns, and Q2 is n x n, also with mutually orthonormal columns.
(See page 769)
|
|
|
|
| size | of a clique is the number of vertices it contains. The size of a vertex cover is the number of vertices in it. Size is the number of comparators a comparison network contains. Depends on the number of inputs and outputs.
(See pages 707, 1003 & 1006)
|
|
|
|
| slack | A linear program in slack form is the maximization of a linear function subject to linear equalities. Slack measures the difference between the left-hand and right-hand sides of an equation.
(See pages 773 & 781)
|
|
|
|
| slack variable | measures the slack, or difference, between the left-hand and right-hand sides of an equation.
(See page 781)
|
|
|
|
| solution | A set of values for x1, x2, . . . , xn that satisfy all of the equations simultaneously.
(See page 742)
|
|
|
|
| sorted in place | the numbers are rearranged within the array with at most a constant number of them stored outside the array at any time.
(See page 16)
|
|
|
|
| sorted list | If a list is sorted, the linear order of the list corresponds to the linear order of keys stored in elements of the list; the minimum element is the head of the list, and the maximum element is the tail.
(See page 204)
|
|
|
|
| sorting network | a comparison network for which the output sequence is monotonically increasing (that is, b1 ≤ b2 ≤ · · · ≤ bn) for every input sequence. Not every comparison network is a sorting network.
(See page 707)
|
|
|
|
| spanning tree | For a graphic matroid MG for a connected, undirected graph G, every maximal independent subset of MG must be a free tree with exactly
|V| - 1 edges that connects all the vertices of G. Such a tree is called a spanning tree of G. Since T is acyclic and connects all of the vertices, it must form a tree, which we call a spanning tree since it "spans" the graph G.
(See pages 394, 561)
|
|
|
|
| spanning tree verification | given a graph G = (V, E) and a tree T ⊆ E, determine whether T is a minimum spanning tree of G.
(See page 579)
|
|
|
|
| splay trees | a form of binary search tree on which the standard search-tree operations run in O(lg n) amortized time. One application simplifies dynamic trees.
(See page 432)
|
|
|
|
| splitting 2-3-4 trees | The split operation is like an "inverse" join; given a dynamic set S and an element x ∈ S, it creates a set S' consisting of all elements in S - {x} whose keys are less than key[x] and a set S'' consisting of all elements in S - {x} whose keys are greater than key[x].
(See page 453)
|
|
|
|
| square | A square matrix is a n x n matrix
(See page 726)
|
|
|
|
| stack | Compilers usually execute recursive procedures by using a stack that contains pertinent information, including the parameter values, for each recursive call. The maximum amount of stack space used at any time during a computation. In a stack, the element deleted from the set is the one most recently inserted: the stack implements a last-in, first-out, or LIFO, policy.
(See pages 162, 200)
|
|
|
|
| stack depth | the maximum amount of stack space used at any time during a computation
(See page 162)
|
|
|
|
| standard | a conanical form in which to describe properties of and algorithms for linear programs. Informally, a linear program in standard form is the maximization of a linear function subject to linear inequalities.
(See page 773)
|
|
|
|
| standard deviation | of a random variable X is the positive square root of the variance of X. The standard deviation of a random variable X is sometimes denoted σX or simply σ when the random variable X is understood from context. With this notation, the variance of X is denoted σ2.
(See page 1110)
|
|
|
|
| static | once the keys are stored in the table, the set of keys never changes
(See page 245)
|
|
|
|
| strictly decreasing | A function f(n) is strictly decreasing if m < n implies f(m) > f(n).
(See page 51)
|
|
|
|
| strictly increasing | A function f(n) is strictly increasing if m < n implies f(m) < f(n).
(See page 51)
|
|
|
|
| string-matching problem | Assume that the text is an array T[1..n] of length n and that the pattern is an array P[1..m] of length m ≤ n. Further assume that the elements of P and T are characters drawn from a finite alphabet Ε. The character arrays P and T are often called strings of characters. Pattern P occurs with shift s in text T (or, equivalently, pattern P occurs beginning at position s + 1 in text T) if 0 ≤ s ≤ n - m and
T[s + 1..s + m] = P[1..m] (that is, if T[s + j] = P[j], for 1 ≤ j ≤ m). If P occurs with shift s in T, then we call s a valid shift; otherwise, we call s an invalid shift. The string-matching problem is the problem of finding all valid shifts with which a given pattern P occurs in a given text T.
(See page 906)
|
|
|
|
| subgraph-isomorphism problem | takes two graphs G1 and G2 and asks whether G1 is isomorphic to a subgraph of G2.
(See page 1017)
|
|
|
|
| subgroup | a nonempty closed subset of a finite group
(See page 866)
|
|
|
|
| subgroup generated by a | The subgroup generated by a, denoted ⟨a⟩ or (⟨a⟩, ⊕), is defined by ⟨a⟩ = {a(k) : k ≥ 1}. We say that a generates the subgroup ⟨a⟩ or that a is a generator of ⟨a⟩.
(See page 867)
|
|
|
|
| subset-sum problem | given a finite set S ⊂ N and a target t ∈ N. We ask whether there is a subset S′ ⊆ S whose elements sum to t.
|
|
|
|
| substitution method | A method for solving recurrences - that is, for obtaining asymptotic "Θ" or "O" bounds on the solution. In the substitution method, we guess a bound and then use mathematical induction to prove our guess correct.
(See page 62)
|
|
|
|
| substring | s′ of a string s is an ordered sequence of consecutive elements of s.
(See page 1095)
|
|
|
|
| symmetric difference | Given two sets A and B, the symmetric difference A ⊕ B is defined as (A - B) ∪ (B - A), that is the elements that are in exactly one of the two sets.
(See page 696)
|
|
|
|
| symmetric matrix | satisfies the condition A = AT.
(See page 728)
|
|
|
|
| tail | In a FIFO queue when an element is enqueued, it takes its place at the tail of the queue.
(See page 202)
|
|
|
|
| tail recursion | A method used with Quicksort which avoids the second recursive call by using an iterative control structure.
(See page 162)
|
|
|
|
| tautology | Let φ be a boolean formula constructed from the boolean input variables x1, x2, . . . , xk, negations (¬), AND's(^), OR's(V), and parentheses. The formula φ is a tautology if it evaluates to 1 for every assignment of 1 and 0 to the input variables.
(See page 983)
|
|
|
|
| terminating case | once encountered, the loop terminates after a constant number of additional operations.
(See page 428)
|
|
|
|
| Termination | When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.
(See page 18)
|
|
|
|
| tight | property of an equality constraint for a particular setting of its nonbasic variables if they cause the constraint's basic variable to become 0.
(See page 791)
|
|
|
|
| Toeplitz matrix | an n x n matrix A = (aij) such that aij = ai-1, j-1 for i = 2, 3, . . . , n and
j = 2, 3, . . . , n.
(See page 844)
|
|
|
|
| total net flow | at a vertex is defined to be the total positive flow leaving a vertex minus the total positive flow entering a vertex.
(See page 645)
|
|
|
|
| total path length | We define the total path length P(T) of a binary tree T as the sum, over all nodes x in T, of the depth of node x, which we denote by
d(x, T).
(See page 270)
|
|
|
|
| transitive closure | The transitive closure of G is defined as the graph G* = (V, E*), where E* = {(i, j) : there is a path from vertex i to vertex j in G}.
(See page 632)
|
|
|
|
| transpose | The transpose of a matrix A is the matrix AT obtained by exchanging the rows and columns of A.
(See page 726)
|
|
|
|
| transposition network | A comparison network is a transposition network if each comparator connects adjacent lines.
(See page 721)
|
|
|
|
| traveling-salesman problem | closely related to the hamiltonian-cycle problem. A salesman must visit n cities. Modeling the problem as a complete graph with n vertices, we can say that the salesman wishes to make a tour, or hamiltonian cycle, visiting each city exactly once and finishing at the city he starts from. There is an integer cost c(i, j) to travel from city i to city j, and the salesman wishes to make the tour whose total cost is minimum, where the total cost is the sum of the individual costs along the edges of the tour.
(See page 1012)
|
|
|
|
| treap | a binary search tree with a modified way of ordering the nodes
(See page 297)
|
|
|
|
| triangle inequality | For any edge (u, v) ∈ E, we have δ(s, v) ≤ δ(s, u) + w(u, v). The cost function c satisfies the triangle inequality if for all vertices u, v, w ∈ V, c(u, w) ≤ c(u, v) + c(v, w). The triangle inequality is a natural one, and in many applications it is automatically satisfied.
(See pages 587, 1028)
|
|
|
|
| tridiagonal matrix | matrix for which tij = 0 if |i - j| > 1. Nonzero entries appear only on the main diagonal, immediately above the main diagonal
(ti,j+1 for i = 1, 2, . . . , n - 1), or immediately below the main diagonal
(ti+1,j for i = 1, 2, . . . , n - 1).
(See page 727)
|
2002 McGraw-Hill Higher Education