Thomas H. Cormen,
Dartmouth College
Charles E. Leiserson,
Massachusetts Institute of Technology
Ronald L. Rivest,
Massachusetts Institute of Technology
Clifford Stein,
Columbia University
| keys | another name for the numbers that we wish to sort
(See page 15)
|
 |
|
|
| 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)
|
|
|
|
| loop invariant | At the start of each iteration of the for loop, the subarray consists of the elements originally in the subarray but in sorted order.
(See page 17)
|
|
|
|
| Initialization | A loop invariant is true prior to the first iteration of the loop.
(See page 18)
|
|
|
|
| Maintenance | If a loop invariant is true before an iteration of the loop, it remains true before the next iteration.
(See page 18)
|
|
|
|
| Termination | When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.
(See page 18)
|
|
|
|
| objects | typical organization for compound data. Composed of attributes or fields.
(See page 20)
|
|
|
|
| passed by value | the called procedure receives its own copy of the parameters, and if it assigns a value to a parameter, the change is not seen by the calling procedure.
(See page 20)
|
|
|
|
| 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)
|
|
|
|
| Analyzing an algorithm | predicting the resources that the algorithm requires.
(See page 21)
|
|
|
|
| random-access machine (RAM) | instructions are executed one after another, with no concurrent operations.
(See page 21)
|
|
|
|
| running time | of an algorithm on a particular input is the number of primitive operations or "steps" executed.
(See page 23)
|
|
|
|
| linear function | running time can be expressed as an + b for constants a and b that depend on the statement costs ci.
(See page 25)
|
|
|
|
| quadratic function | the worst-case running time can be expressed as an2 + bn + c for constants a, b, and c that again depend on the statement costs ci.
(See page 25)
|
|
|
|
| worst-case running time | the longest running time for any input of size n.
(See page 26)
|
|
|
|
| average-case | expected running time of an algorithm.
(See page 26)
|
|
|
|
| probabilistic analysis | technique by which we determine expected running times.
(See page 26)
|
|
|
|
| randomized algorithm | makes random choices to allow a probabilistic analysis.
(See page 26)
|
|
|
|
| incremental | The approach used for insertion sort: having sorted the subarray
A[1..j - 1], we insert the single element A[j] into its proper place, yielding the sorted array A[1..j].
(See page 27)
|
|
|
|
| recursive | structure used in many useful algorithms: to solve a given problem, they call themselves recursively one or more times to deal with closely related sub-problems.
(See page 28)
|
|
|
|
| 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)
|
|
|
|
| recurrence equation | or recurrence, describes the overall running time on a problem of size n in terms of the running time on smaller inputs.
(See page 32)
|
2002 McGraw-Hill Higher Education