Tik-61.183 Special course on information technology III

Randomized algorithms
Spring 2000
Heikki Mannila

Exercises 3, due March 15, 2000

1.
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.



http://www.cis.hut.fi/Opinnot/T-61.6030/k2000/exercises/3/exercise3.shtml
jkseppan@mail.cis.hut.fi
Monday, 06-Mar-2000 11:08:58 EET