[an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] HUT - CIS /Opinnot/T-61.6030/k2000/exercises/3/exercise3.shtml [an error occurred while processing this directive]
         [an error occurred while processing this directive] Index of /style/plain

Index of /style/plain

[ICO]NameLast modifiedSizeDescription

[PARENTDIR]Parent Directory  -  
[IMG]blue20.gif1999-11-03 19:09 37  
[IMG]blue120.gif1999-11-03 19:08 42  
[TXT]cis_plain.css2000-04-20 12:16 3.1K 
[   ]cis_plain.css.old2000-01-25 10:42 2.3K 
[TXT]cis_plain_footer.shtml2000-09-08 16:08 322  
[TXT]cis_plain_header.shtml2001-08-03 10:00 1.3K 
[   ]cis_plain_header.shtml.old2001-08-03 09:46 1.2K 
[TXT]scientific.shtml2000-03-08 14:05 4.8K 
[TXT]template.html1999-12-03 14:11 332  
[TXT]template.shtml1999-11-12 12:58 321  
[TXT]template.shtml.krista1999-12-03 14:11 267  
[TXT]template.txt1999-11-12 12:58 321  

Apache/2.4 Server at www.cis.hut.fi Port 80


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
webmaster@www.cis.hut.fi
Monday, 06-Mar-2000 11:08:58 EET