imported>Etone |
imported>Etone |
| Line 1: |
Line 1: |
| <font color=red size=4>
| | == Problem 1== |
| * 注意写明自己的姓名与学号。
| | Solve the following recurrences: |
| * 必须包含完整的解题过程，中英文不限。 | | * <math>a_n=3a_{n-1}-2a_{n-2}</math>, given that <math>a_0=2</math> and <math>a_1=3</math>. |
| </font> | | * <math>b_n=\frac{1}{2}(b_{n-1}+b_{n-2})</math>, given that <math>b_0=0</math> and <math>b_1=1</math>. |
| ==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.
| | == Problem 2 == |
| | <math>n</math> persons are to be allocated to <math>q</math> distinct rooms. Find the number of ways that this can be done if only <math>m</math> of the <math>q</math> rooms have exactly <math>k</math> persons each, where <math>1\le m\le q</math> and <math>mk\le n</math>. |
|
| |
|
| (<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.)
| | == Problem 3== |
| | Prove the following identity: |
| | *<math>\sum_{k=1}^n k{n\choose k}= n2^{n-1}</math>. |
|
| |
|
| 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?
| | (Hint: Use double counting.) |
|
| |
|
| == Problem 2== | | == Problem 4 == |
| (Due to Karger and Motwani)
| | Show that among any group of <math>n</math> people, where <math>n\ge 2</math>, there are at least two people who know exactly the same number of people in the group (assuming that "knowing" is a symmetric relation). |
| * Let <math>S,T</math> be two disjoint subsets of a universe <math>U</math> such that <math>|S|=|T|=n</math>. Suppose we select a random set <math>R\subseteq U</math> by independently sampling each element of <math>U</math> with probability <math>p</math>. We say that the random sample <math>R</math> is ''good'' if the following two conditions hold: <math>R\cap S=\emptyset</math> and <math>R\cap T\neq\emptyset</math>. SHow that for <math>p=1/n</math>, the probability that <math>R</math> is good is larger than some positive constant.
| |
|
| |
|
| :(<font color=red>The hint for the second question was wrong. The question is now optional and use whatever tools you can come up with.</font>)
| | == Problem 5 == |
| * Suppose now that the random set <math>R</math> is chosen by sampling the elements of <math>U</math> with only '''''pairwise''''' independence. Show that for a suitable choice of the value of <math>p</math>, the probability that <math>R</math> is good is larger than some positive constant. <STRIKE>(Hint: Use the second moment.)</STRIKE>
| | Let <math>S</math> be a subset of <math>\{1,2,\ldots,2n\}</math> such that <math>|S|>n</math>. Show that there exist <math>a,b\in S</math> such that <math>a</math> and <math>b</math> are coprime. |
| | |
| == Problem 3== | |
| # 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.
| |
| | |
| == Problem 4==
| |
| (Generalization of Chernoff bound to the sum of geometric random variables.)
| |
| | |
| Let <math>X_1,X_2,\ldots,X_n</math> be independent geometrically distributed random variables each having expectation 2 (each of the <math>X_i</math> is an independent experiment counting the number of tosses of an unbiased coin up to and including the first HEADS). Let <math>X=\sum_{i=1}^n X_i</math> and <math>\delta</math> be a positive real constant. Use the moment generating functions to derive the best upper bound you can give on <math>\Pr[X>(1+\delta)(2n)]</math>.
| |
Problem 1
Solve the following recurrences:
- [math]\displaystyle{ a_n=3a_{n-1}-2a_{n-2} }[/math], given that [math]\displaystyle{ a_0=2 }[/math] and [math]\displaystyle{ a_1=3 }[/math].
- [math]\displaystyle{ b_n=\frac{1}{2}(b_{n-1}+b_{n-2}) }[/math], given that [math]\displaystyle{ b_0=0 }[/math] and [math]\displaystyle{ b_1=1 }[/math].
Problem 2
[math]\displaystyle{ n }[/math] persons are to be allocated to [math]\displaystyle{ q }[/math] distinct rooms. Find the number of ways that this can be done if only [math]\displaystyle{ m }[/math] of the [math]\displaystyle{ q }[/math] rooms have exactly [math]\displaystyle{ k }[/math] persons each, where [math]\displaystyle{ 1\le m\le q }[/math] and [math]\displaystyle{ mk\le n }[/math].
Problem 3
Prove the following identity:
- [math]\displaystyle{ \sum_{k=1}^n k{n\choose k}= n2^{n-1} }[/math].
(Hint: Use double counting.)
Problem 4
Show that among any group of [math]\displaystyle{ n }[/math] people, where [math]\displaystyle{ n\ge 2 }[/math], there are at least two people who know exactly the same number of people in the group (assuming that "knowing" is a symmetric relation).
Problem 5
Let [math]\displaystyle{ S }[/math] be a subset of [math]\displaystyle{ \{1,2,\ldots,2n\} }[/math] such that [math]\displaystyle{ |S|\gt n }[/math]. Show that there exist [math]\displaystyle{ a,b\in S }[/math] such that [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math] are coprime.