随机算法 (Spring 2013)/Problem Set 2: Difference between revisions
imported>Etone (Created page with "== Problem 1== # Generalize the LazySelect algorithm for the <math>k</math>-selection problem: Given as input an array of <math>n</math> distinct numbers and an integer <math>k<…") |
imported>Etone No edit summary |
||
| Line 1: | Line 1: | ||
== Problem | ==Problem 1== | ||
(Due to Karp) | |||
Consider a bin containing <math>d</math> balls chosen at random (''without replacement'') from a collection of <math>n</math> distinct balls. Without being able to see or count the balls in the bin, we would like to simulate random sampling ''with replacement'' from the original set of <math>n</math> balls. Our only access to the balls in that we can sample ''without replacement'' from the bin. | |||
(<font color=red>Spoiler alert</font>: You may want to stop here for a moment and start thinking about the solution before proceeding to read the following part.) | |||
Consider the following strategy. Suppose that <math>k<d</math> balls have been drawn from the bin so far. Flip a coin with probability of HEADS being <math>k/n</math>. If HEADS appears, then pick one of the <math>k</math> previously drawn balls uniformly at random; otherwise, draw a random ball from the bin. Show that each choice is independently and uniformly distributed over the space of the <math>n</math> original balls. How many times can we repeat the sampling? | |||
== Problem 2== | |||
# Generalize the LazySelect algorithm for the <math>k</math>-selection problem: Given as input an array of <math>n</math> distinct numbers and an integer <math>k</math>, find the <math>k</math>th smallest number in the array. | # Generalize the LazySelect algorithm for the <math>k</math>-selection problem: Given as input an array of <math>n</math> distinct numbers and an integer <math>k</math>, find the <math>k</math>th smallest number in the array. | ||
# Use the Chernoff bounds instead of Chebyshev's inequality in the analysis of the LazySelect Algorithm and try to use as few random samples as possible. | # Use the Chernoff bounds instead of Chebyshev's inequality in the analysis of the LazySelect Algorithm and try to use as few random samples as possible. | ||
Revision as of 14:10, 8 April 2013
Problem 1
(Due to Karp)
Consider a bin containing [math]\displaystyle{ d }[/math] balls chosen at random (without replacement) from a collection of [math]\displaystyle{ n }[/math] distinct balls. Without being able to see or count the balls in the bin, we would like to simulate random sampling with replacement from the original set of [math]\displaystyle{ n }[/math] balls. Our only access to the balls in that we can sample without replacement from the bin.
(Spoiler alert: You may want to stop here for a moment and start thinking about the solution before proceeding to read the following part.)
Consider the following strategy. Suppose that [math]\displaystyle{ k\lt d }[/math] balls have been drawn from the bin so far. Flip a coin with probability of HEADS being [math]\displaystyle{ k/n }[/math]. If HEADS appears, then pick one of the [math]\displaystyle{ k }[/math] previously drawn balls uniformly at random; otherwise, draw a random ball from the bin. Show that each choice is independently and uniformly distributed over the space of the [math]\displaystyle{ n }[/math] original balls. How many times can we repeat the sampling?
Problem 2
- Generalize the LazySelect algorithm for the [math]\displaystyle{ k }[/math]-selection problem: Given as input an array of [math]\displaystyle{ n }[/math] distinct numbers and an integer [math]\displaystyle{ k }[/math], find the [math]\displaystyle{ k }[/math]th smallest number in the array.
- Use the Chernoff bounds instead of Chebyshev's inequality in the analysis of the LazySelect Algorithm and try to use as few random samples as possible.