Thomas H. Cormen,
Dartmouth College
Charles E. Leiserson,
Massachusetts Institute of Technology
Ronald L. Rivest,
Massachusetts Institute of Technology
Clifford Stein,
Columbia University
| 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)
|
 |
|
|
| uniform random permutation | each of the possible n! permutations appears with equal probability.
(See page 93)
|
|
|
|
| randomized | 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 page 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)
|
|
|
|
| pseudorandom-number generator | a deterministic algorithm returning numbers that "look" statistically random
(See page 94)
|
|
|
|
| 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)
|
|
|
|
| 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)
|
|
|
|
| uniform random permutation | every permutation of the numbers 1 through n is equally likely to be produced.
(See page 101)
|
|
|
|
| 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)
|
|
|
|
| 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)
|
2002 McGraw-Hill Higher Education