Thomas H. Cormen,
Dartmouth College
Charles E. Leiserson,
Massachusetts Institute of Technology
Ronald L. Rivest,
Massachusetts Institute of Technology
Clifford Stein,
Columbia University
| greedy algorithm | always makes the choice that looks best at the moment. That is, it makes a locally optimum choice in the hope that this choice will lead to a globally optimal solution.
(See page 370)
|
 |
|
|
| compatible activities | Activities ai and aj are compatible if the intervals [si, fi) and [sj, fj) do not overlap (i.e., ai and aj are compatible if si ≥ fj or sj ≥ fi).
(See page 371)
|
|
|
|
| activity-selection problem | to select a maximum-size subset of mutually compatible activities.
(See page 371)
|
|
|
|
| greedy-choice property | a globally optimal solution can be arrived at by making a locally optimal (greedy) choice. The greedy choice is the one that looks best in the current problem, without considering results from subproblems.
(See page 380)
|
|
|
|
| optimal substructure | A problem exhibits optimal substructure if an optimal solution to the problem contains within it optimal solutions to subproblems.
(See page 381)
|
|
|
|
| 0-1 knapsack problem | A thief robbing a store finds n items: the ith item is worth vi dollars and weighs wi pounds, where vi and wi 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)
|
|
|
|
| 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)
|
|
|
|
| prefix codes | codes in which no codeword is also a prefix of some other codeword. These could be considered "prefix-free codes".
(See page 385)
|
|
|
|
| Huffman code | optimal prefix codes constructed by a greedy algorithm invented by Huffman
(See page 387)
|
|
|
|
| maximal | If A is an independent subset in a matroid M, then A is maximal if it has no extensions. That is, A is maximal if it is not contained in any larger independent subset of M.
(See page 394)
|
|
|
|
| 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.
(See page 394)
|
|
|
|
| minimum-spanning-tree problem | Given a connected undirected graph G = (V, e) and a length function ω such that ω(e) is the (positive) length of edge e, find a subset of the edges that connects all of the vertices together and has minimum total length. (The term "length" refers to the original edge weights for the graph, reserving the term "weight" to refer to the weights in the associated matroid.)
(See page 395)
|
|
|
|
| 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)
|
|
|
|
| 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)
|
|
|
|
| deadlines | a set of n integers d1, d2, . . . , dn, such that each di satisfies 1 ≤ di ≤ n and task ai is supposed to finish by time di.
(See page 399)
|
|
|
|
| penalties | a set of n nonnegative weights w1, w2, . . . , wn, such that a penalty of wi is incurred if task ai is not finished by time di and no penalty is incurred if a task finishes by its deadline.
(See page 399)
|
|
|
|
| late | a property of a task in a schedule if it finishes after its deadline.
(See page 399)
|
|
|
|
| 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)
|
|
|
|
| canonical form | An arbitrary schedule in which the early tasks precede the late tasks and the early tasks are scheduled in order of monotonically increasing deadlines.
(See page 399)
|
|
|
|
| independent tasks | property of a set of tasks such that no tasks are late in the associated schedule.
(See page 400)
|
|
|
|
| completion time | the time at which a task completes processing.
(See page 402)
|
|
|
|
| release time | the time before which a task is not available to be processed.
(See page 403)
|
|
|
|
| preemption | processing code which allows a task to be suspended and restarted at a later time
(See page 403)
|
2002 McGraw-Hill Higher Education