Thomas H. Cormen,
Dartmouth College
Charles E. Leiserson,
Massachusetts Institute of Technology
Ronald L. Rivest,
Massachusetts Institute of Technology
Clifford Stein,
Columbia University
| (binary) heap data structure | an array object that can be viewed as a nearly complete binary tree
(See page 125)
|
 |
|
|
| 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)
|
|
|
|
| Analyzing an algorithm | predicting the resources that the algorithm requires.
(See page 21)
|
|
|
|
| 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 ≥ n0, 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)
|
|
|
|
| average-case | expected running time of an algorithm.
(See page 26)
|
|
|
|
| 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)
|
|
|
|
| correct algorithm | for every input instance it halts with the correct output. A correct algorithm solves the given computational problem.
(See page 6)
|
|
|
|
| coupon collector's problem | a person trying to collect each of b different coupons must acquire approximately b ln b randomly obtained coupons in order to succeed.
(See page 110)
|
|
|
|
| data structure | a way to store and organize data in order to facilitate access and modifications.
(See page 8)
|
|
|
|
| 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)
|
|
|
|
| Fibonacci numbers | The Fibonacci numbers are defined by the following recurrence:
F0 = 0 ,
F1 = 1 ,
Fi = Fi-1 + Fi-2 for i ≥ 2.Thus, each Finonacci number is the sum of the two previous ones, yielding the sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... .
(See page 56)
|
|
|
|
| hat-check problem | Each of n customers gives a hat to a hat-check person at a restaurant. The hat-check person gives the hats back to the customers in a random order. What is the expected number of customers that get back their own hat?
(See page 98)
|
|
|
|
| height | Viewing a heap as a tree, we define the height of a node in a heap to be the number of edges on the longest simple downward path from the node to a leaf, and we define the height of the heap to be the height of its root.
(See page 129)
|
|
|
|
| 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)
|
|
|
|
| Initialization | A loop invariant is true prior to the first iteration of the loop.
(See page 18)
|
|
|
|
| Input | A sequence of n numbers (a1, a2,...,an).
(See page 5)
|
|
|
|
| instance of a problem | consists of the input (satisfying whatever constraints are imposed in the problem statement) needed to compute a solution to the problem.
(See page 5)
|
|
|
|
| inversion | Let A[1..n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i, j) is called an inversion of A.
(See page 99)
|
|
|
|
| keys | another name for the numbers that we wish to sort
(See page 15)
|
|
|
|
| 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)
|
|
|
|
| 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)
|
|
|
|
| Maintenance | If a loop invariant is true before an iteration of the loop, it remains true before the next iteration.
(See page 18)
|
|
|
|
| master method | A method for solving recurrences - that is, for obtaining asymptotic "Θ" or "O" bounds on the solution. The master method provides bounds for recurrences of the form T(n) = aT(n / b) + f(n), where a ≥ 1, b > 1, and f(n) is a given function; it requires memorization of three cases, but once you do that, determining asymptotic bounds for many simple recurrences is easy.
(See page 62)
|
|
|
|
| max-heap property | In a max-heap, the max-heap property is that for every node i other than the root, A[PARENT(i)] ≥ A[i], that is, the value of a node is at most the value of its parent.
(See page 128)
|
|
|
|
| max-priority queue | supports the following operations. INSERT(S, x) inserts the element x into the set S. This operation could be written as S ← S ∪ {x}. MAXIMUM(S) returns the element of S with the largest key. EXTRACT-MAX(S) removes and returns the element of S with the largest key. INCREASE-KEY(S, x, k) increases the value of element x's key to the new value k, which is assumed to be at least as large as x's current key value. One application of max-priority queues is to schedule jobs on a shared computer.
(See page 138)
|
|
|
|
| min-heap property | A min-heap is organized in the opposite way from the max-heap; the min-heap property is that for every node i other than the root, A[PARENT(i)] ≤ A[i].
(See page 129)
|
|
|
|
| min-priority queue | supports the operations INSERT, MINIMUM, EXTRACT-MIN, and DECREASE-KEY. The min-priority queue can be used in an event-driven simulator.
(See page 138)
|
|
|
|
| Monge array | An m x n array A of real numbers is a Monge array if for all i, j, k, and l such that 1 ≤ i < k ≤ m and 1 ≤ j < l ≤ n, we have A[i, j] + A[k, l] ≤ A[i, l] + A[k, j].
(See page 88)
|
|
|
|
| monotone | the values returned by successive EXTRACT-MIN operations are monotonically increasing over time.
(See page 144)
|
|
|
|
| monotonically decreasing | A function f(n) is monotonically decreasing if m ≤ n implies
f(m) ≥ f(n).
(See page 51)
|
|
|
|
| monotonically increasing | A function f(n) is monotonically increasing if m ≤ n implies
f(m) ≤ f(n).
(See page 51)
|
|
|
|
| objects | typical organization for compound data. Composed of attributes or fields.
(See page 20)
|
|
|
|
| Output | A permutation (reordering) (a'1, a'2,...,a'n) of the input sequence such that a'1 ≤ a'2 ≤ · · · ≤ a'n.
(See page 5)
|
|
|
|
| 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)
|
|
|
|
| polylogarithmically bounded | A function f(n) is polylogarithmically bounded if f(n) = O(lgkn) for some constant k.
(See page 54)
|
|
|
|
| polynomially bounded | A function f(n) is polynomially bounded if f(n) = O(nk) for some constant k.
(See page 52)
|
|
|
|
| priority queue | a data structure for maintaining a set S of elements, each with an associated value called a key.
(See page 138)
|
|
|
|
| probabilistic analysis | the use of probability in the analysis of problems. Most commonly, we use probabilistic analysis to analyze the running time of an algorithm.
(See page 92)
|
|
|
|
| pseudorandom-number generator | a deterministic algorithm returning numbers that "look" statistically random
(See page 94)
|
|
|
|
| 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)
|
|
|
|
| random-access machine (RAM) | instructions are executed one after another, with no concurrent operations.
(See page 21)
|
|
|
|
| randomized | makes random choices to allow a probabilistic analysis. We call an algorithm randomized if its behavior is determined not only by its input but also by values produced by a random-number generator.
(See pages 26 & 94)
|
|
|
|
| random-number generator | A function RANDOM(a, b) which returns an integer between a and b, inclusive, with each such integer being equally likely.
(See page 94)
|
|
|
|
| record | each number to be sorted is usually part of a collection of data called a record
(See page 123)
|
|
|
|
| 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)
|
|
|
|
| recursion tree | In a recursion tree, each node represents the cost of a single subproblem somewhere in the set of recursive function invocations.
(See page 67)
|
|
|
|
| recursion-tree method | A method for solving recurrences - that is, for obtaining asymptotic "Θ" or "O" bounds on the solution. The recursion-tree method converts the recurrence into a tree whose nodes represent the costs incurred at various levels of the recursion; we use techniques for bounding summations to solve the recurrence.
(See page 62)
|
|
|
|
| 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)
|
|
|
|
| remainder (or residue) | For any integer a and any positive integer n, the value a mod n is the remainder (or residue) of the quotient a / n: a mod n = a - ⌊a/n⌋n.
(See page 51)
|
|
|
|
| running time | of an algorithm on a particular input is the number of primitive operations or "steps" executed.
(See page 23)
|
|
|
|
| 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)
|
|
|
|
| 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)
|
|
|
|
| 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)
|
|
|
|
| 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)
|
|
|
|
| Termination | When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.
(See page 18)
|
|
|
|
| uniform random permutation | Each of the possible n! permutations appears with equal probability. Every permutation of the numbers 1 through n is equally likely to be produced.
(See pages 93 & 101)
|
|
|
|
| worst-case running time | the longest running time for any input of size n.
(See page 26)
|
2002 McGraw-Hill Higher Education