## Tik-61.183 Special course on information technology IIIRandomized algorithmsSpring 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 |