imported>Etone |
imported>Etone |
| Line 1: |
Line 1: |
| ==Problem 1== | | = Syllabus = |
| Some known facts:
| | *'''Time''': every Thursday, 6:30pm. |
| * Balls-into-bins: <math>m</math> balls are uniformly and independently thrown to <math>n</math> bins. If <math>m=\Theta(n)</math>, then the maximum load is <math>\Theta\left(\frac{\ln n}{\ln\ln n}\right)</math> with high probability. | | * '''Place''': CS building, 228. |
| * Power of two choices: <math>m</math> balls are sequentially thrown to <math>n</math> bins. For each ball, uniformly and independently choose random bins <math>i</math> and <math>j</math> (might be the same bin), and throw the ball to the currently less loaded bin among bin <math>i</math> and bin <math>j</math>. Assuming that <math>m=\Theta(n)</math>, after all <math>m</math> balls are thrown to bins, the maximum load is <math>\Theta\left(\ln \ln n\right)</math> with high probability. | |
|
| |
|
| Questions: Assume <math>n</math> balls and <math>n</math> bins. We throw the <math>n</math> balls sequentially.
| | * '''Organizer''': 尹一通 |
| # If we throw the first <math>\frac{n}{2}</math> balls uniformly and then throw the rest balls as the way of power-of-two-choices, what is the asymptotic maximum load with high probability?
| | :* office: CS building, 804 |
| # For the <math>k</math>th ball, if <math>k</math> is even, we throw the ball to a uniform bin; and if <math>k</math> is odd, we throw the ball as the way of power-of-two-choices. What is the asymptotic maximum load with high probability?
| | :* email: yitong.yin@gmail.com |
|
| |
|
| == Problem 2== | | = Schedule = |
| # Generalize the LazySelect algorithm for the general selection problem: finding the <math>k</math>th smallest element in an array. Choose appropriate parameters to do the job. | | :{|border="2" width="100%" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;" |
| # Use the Chernoff bounds instead of Chebyshev's inequality in the analysis of the above algorithm and try to use a smaller number of random samples.
| | |- |
| | | |bgcolor="#A7C1F2"|Dates||bgcolor="#A7C1F2"|Speakers||bgcolor="#A7C1F2"|Topics |
| == Problem 3 == | | |- |
| ;The Monte Carlo method for computing <math>\mathrm{e}</math>
| | |Sept. 26, 2011 ||张弛豪（上海交通大学） ||Chap.1 of Williamson-Shmoys. Introduction to approximation algorithms.<br> Approximation ratio; set cover; rounding an LP; LP duality; greedy algorithms. |
| | | |- |
| Suppose there are <math>n</math> peoples, each wearing a hat. We collect all their hats and randomly distribute the hats back to them, with each people receiving exactly one hat. We ask for the probability that none of the people receives his/her own hat. We denote this probability by <math>p(n)</math>
| | |Oct. 8, 2011 ||张弛豪（上海交通大学） ||Chap.2 of Williamson-Shmoys. Greedy algorithms and local search.<br> Scheduling with deadlines; <math>k</math>-center; minimize makespan; metric TSP; min-degree spanning tree. |
| | | |} |
| Formally, a '''permutation''' is a bijection <math>\pi:[n]\xrightarrow[\text{1-1}]{\text{onto}}[n]</math>. A '''fixed point''' for permutation <math>\pi</math> is an <math>i\in[n]</math> such that <math>\pi(i)=i</math>. Then <math>p(n)</math> is the probability that a uniformly random permutation has no fixed point. Such permutations are called '''derangements'''.
| |
| | |
| The derangement problem is taught in the undergraduate class [[组合数学 (Fall 2011)|Combinatorics]] at Nanjing University. See the [[组合数学 (Fall 2011)/Sieve_methods#Derangements|lecture notes]] for details. By the Principle of Inclusion-Exclusion (容斥原则), we know that <math>p(n)=\sum_{k=0}^n\frac{(-1)^k}{k!}</math>.
| |
| | |
| Recall that due to Taylor's expansion <math>\mathrm{e}^{-1}=\sum_{k=0}^\infty\frac{(-1)^k}{k!}=p(\infty)</math>.
| |
| | |
| Now suppose you are given access to a balckbox <math>derange(n)</math> which given as input a number <math>n</math>, samples a uniform and independent permutation <math>\pi</math> of <math>[n]</math>, and returns true if <math>\pi</math> has no fixed point and false if otherwise.
| |
| | |
| Give a randomized algorithm <math>randE(\epsilon,\delta)</math>, whose inputs are <math>0<\epsilon<0.1</math> and <math>0<\delta<\frac{1}{2}</math>. The returned value of the algorithm should satisfy that
| |
| :<math>\Pr[\mathrm{e}-\epsilon\le randE(\epsilon,\delta)\le\mathrm{e}+\epsilon]\ge1-\delta</math>.
| |
| | |
| * Your algorithm should call <math>derange(n)</math> as subroutine. Try to make both <math>n</math> and the number of times calling <math>derange(n)</math> as small as possible.
| |
| * Please give detailed analysis of your algorithm.
| |