[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/2/exercise2.shtml [an error occurred while processing this directive]
[an error occurred while processing this directive] Index of /style/plain

# Index of /style/plain

Parent Directory  -
blue20.gif1999-11-03 19:09 37
blue120.gif1999-11-03 19:08 42
cis_plain.css2000-04-20 12:16 3.1K
cis_plain.css.old2000-01-25 10:42 2.3K
cis_plain_footer.shtml2000-09-08 16:08 322
scientific.shtml2000-03-08 14:05 4.8K
template.html1999-12-03 14:11 332
template.shtml1999-11-12 12:58 321
template.shtml.krista1999-12-03 14:11 267
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 2, due February 16, 2000

1.
Assume we have a file containing N records, where N is so large that we cannot keep all of the file in memory at one time. We wish to select a random subset of n records from the file. We will use the following algorithm:
Set t:=0, m:=0.
Repeat until m=n:
Generate a random number U, uniformly distributed between 0 and 1.
If U<(n-m)/(N-t), then
Add the next record from the file into the subset.
Set m:=m+1.
Else
Skip the next record.
Set t:=t+1.
Prove that the algorithm doesn't try to read more than N records from the file. Prove that each of the  subsets is equally likely to be selected.
2.
Let p(x,y) be the probability that exactly x records are selected from among the first y by the previous algorithm. Show that

3.
What is the expected value of t when the algorithm terminates? What is the variance?

4.
Devise an algorithm to select a random permutation of n objects using O(n) random numbers. Each permutation should be equally likely.

http://www.cis.hut.fi/Opinnot/T-61.6030/k2000/exercises/2/exercise2.shtml
webmaster@www.cis.hut.fi
Wednesday, 09-Feb-2000 20:43:29 EET