McGraw-Hill OnlineMcGraw-Hill Higher EducationLearning Center
Student Center | Instructor's Center | Introduction to Algorithms | Home
Glossary A-B
Glossary B-D
Glossary D-F
Glossary F-J
Glossary J-M
Glossary M-O
Glossary O-P
Glossary P-S
Glossary S-T
Glossary T-Z
Chapter Objectives
Chapter Overview
Glossary
PowerPoint Slides
Algorithm Pseudocode
Feedback
Help Center


small text cover image
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
Dynamic Programming

Glossary


optimization problems  In such problems there can be many possible solutions. Each solution has a value, and we wish to find a solution with the optimal (minimum or maximum) value. We call such a solution an optimal solution to the problem, as opposed to the optimal solution, since there may be several solutions that achieve the optimal value.
(See page 323)
optimal substructure  for assembly-line scheduling, an optimal solution to a problem (finding the fastest way through station Si, j) contains within it an optimal solution to subproblems (finding the fastest way through either S1, j-1 or S2, j-1). A problem exhibits optimal substructure if an optimal solution to the problem contains within it optimal solutions to subproblems.
(See page 327)
fully parenthesized  A product of matrices is fully parenthesized if it is either a single matrix or the product of two fully parenthesized matrix products, surrounded by parentheses.
(See page 331)
compatible  We can multiply two matrices A and B only if they are compatible: the number of columns of A must equal the number of rows of B.
(See page 332)
matrix-chain multiplication problem  Given a chain (A1, A2, . . . , An) of n matrices, where for i = 1, 2, . . . , n, matrix Ai has dimension pi-1 x pi, fully parenthesize the product
A1A2 . . . An in a way that minimizes the number of scalar multiplications.
(See page 332)
Catalan numbers  A sequence of numbers which grows as Ω(4n / n3/2).
(See page 333)
independent  The solution to one subproblem does not affect the solution to another subproblem of the same problem. Two subproblems of the same problem are independent if they do not share resources.
(See page 343)
overlapping subproblems  When a recursive algorithm revisits the same problem over and over again, we say that the optimization problem has overlapping subproblems. Two subproblems are overlapping if they are really the same subproblem that occurs as a subproblem of different problems.
(See page 344)
memoize  A memoized recursive algorithm maintains an entry in a table for the solution to each subproblem. Each table entry initially contains a special value to indicate that the entry has yet to be filled in. When the subproblem is first encountered during the execution of the recursive algorithm, its solution is computed and then stored in the table. Each subsequent time that the subproblem is encountered, the value stored in the table is simply looked up and returned. This approach presupposes that the set of all possible subproblem parameters is known and that the relation between table positions and subproblems is established. Another approach is to memoize by using hashing with the subproblem parameters as keys.
(See page 347)
common subsequence  Given two sequences X and Y, we say that a sequence Z is a common subsequence of X and Y if Z is a subsequence of both X and Y.
(See page 351)
longest-common-subsequence problem  We are given two sequences X = (x1, x2, . . . , xm) and
Y = (y1, y2, . . . , yn) and wish to find a maximum-length common subsequence of X and Y.
(See page 351)
prefix  Given a sequence X = (x1, x2, . . . , xm), we define the ith prefix of X, for i = 0, 1, . . . , m, as Xi = (x1, x2, . . . , xi).
(See page 351)
optimal binary search tree  A binary search tree organized so as to minimize the number of nodes visited in all searches, given that we know how often each word occurs. A binary search tree whose expected search cost is smallest.
(See page 357)
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)
edit distance  from x to y it is the cost of the least expensive operation sequence that transforms x to y.
(See page 366)








Copyright2002 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.