Randomization - Data Structures and Problem Solving Using Java - page 406

Note that rewriting the call to swap with the call to r.nextInt(0,n-1) does
not work, even for three elements. There are 3! = 6 possible permutations, and
the number of different sequences that could be computed by the three calls to
nextInt is 3 3 = 27. Because 6 does not divide 27 exactly, some permutations
must be more likely than others.

randomized algorithms

9.5

Suppose that you are a professor who is giving weekly programming assign-
ments. You want to ensure that the students are doing their own programs or,
at the very least, that they understand the code that they are submitting. One
solution is to give a quiz on the day each program is due. However, these
quizzes take time from class and doing so might be practical for only roughly
half the programs. Your problem is to decide when to give the quizzes.
Of course, if you announce the quizzes in advance, that could be interpreted
as an implicit license to cheat for the 50 percent of the programs that will not get a
quiz. You could adopt the unannounced strategy of giving quizzes on alternate
programs, but students would quickly figure out that strategy. Another possibility
is to give quizzes on what seem like the important programs, but that would likely
lead to similar quiz patterns from semester to semester. Student grapevines being
what they are, this strategy would probably be worthless after one semester.
One method that seems to eliminate these problems is to flip a coin. You
make a quiz for every program (making quizzes is not nearly as time consum-
ing as grading them), and at the start of class, you flip a coin to decide
whether the quiz is to be given. This way neither you nor your students can
know before class whether a quiz will be given. Also, the patterns do not
repeat from semester to semester. The students can expect a quiz to occur with
50 percent probability, regardless of previous quiz patterns. The disadvantage
of this strategy is that you could end up giving no quizzes during an entire
semester. Assuming a large number of programming assignments, however,
this is not likely to happen unless the coin is suspect. Each semester the
expected number of quizzes is half the number of programs, and with high
probability, the number of quizzes will not deviate much from this.

This example illustrates the randomized algorithm, which uses random
numbers, rather than deterministic decisions, to control branching. The run-
ning time of the algorithm depends not only on the particular input, but also
on the random numbers that occur.
The worst-case running time of a randomized algorithm is almost always
the same as the worst-case running time of the nonrandomized algorithm. The

A randomized algo-
rithm uses
random numbers
rather than
deterministic deci-
sions to control
branching.