Tik-61.183 Special course on information technology III

Randomized algorithms
Spring 2000
Heikki Mannila

Exercises 3, due March 15, 2000

Complete last time's exercise 2.4: show that the given algorithm does indeed select a permutation uniformly.
Set X:=(1,2,...,n).
Repeat for i=1,2,...,n-1:
    Select a number r in {i,i+1,...,n} at random.
    Exchange X[i] with X[r].
Output X.

Monday, 06-Mar-2000 11:08:58 EET