组合数学 (Fall 2011)/Problem set 2 and 随机算法 (Fall 2011)/Problem set 2: Difference between pages

From TCS Wiki
(Difference between pages)
Jump to navigation Jump to search
VisualWikitext
imported>Etone
No edit summary
 
imported>Etone
 
Line 1: Line 1:
*<font color="red" size=5>题目要有解题过程。</font>
==Problem 1==
Some known facts:
* 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.
* 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.


== Problem 0 ==
Questions: Assume <math>n</math> balls and <math>n</math> bins. We throw the <math>n</math> balls sequentially.
你的姓名、年级、学号。
# 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?
# 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?


== Problem 1 ==
== Problem 2==
令<math>f_k(n)</math>为'''没有'''长为<math>k</math>的圈(cycle)的<math>[n]</math>的排列(permutation)的数量。
# 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.
#求<math>f_k(n)</math>。(可以不是闭合形式)
# 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.
#对常数<math>k</math>，求<math>\lim_{n\rightarrow\infty}\frac{f_k(n)}{n!}</math>。(闭合形式)


== Problem 2==
== Problem 3 ==
有三种颜色的宝石，串成20块宝石的项链，旋转(rotation)和镜像(reflection)都算等价。给出对于这种项链计数的pattern inventory。给出5种具体的<math>(n_1,n_2,n_3)</math>，以及第 <math>i</math> 种宝石刚好有 <math>n_i</math> 块 (<math>i=1,2,3</math>) 的项链的计数。
;The Monte Carlo method for computing <math>\mathrm{e}</math>


写一篇短文（字数不限），以论文的格式给出这道题目的解决过程。
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 one hat. We ask for the probability that none of the people receive his/her own hat. We denote this probability by <math>p(n)</math>


（可以编程解决，也可以使用一些符号计算工具，例如mathematica或linux下的MAXIMA。不建议手算。）
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 '''derangement'''.


如果有代码，也要提交源代码。
This derangement problem is taught in undergraduate class 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>.


== Open project (可选) ==
Recall that due to Taylor's expansion <math>\mathrm{e}=\sum_{k=0}^\infty\frac{(-1)^k}{k!}=p(\infty)</math>.
* 编一个程序，输入：<math>n,m,n_1,n_2,\ldots,n_{m}</math> 且有 <math>n_1+n_2+\cdots+n_m=n</math>.
输出：<math>n</math> 块宝石组成的项链，旋转(rotation)和镜像(reflection)都算等价，宝石有 <math>m</math> 种，第 <math>i</math> 种宝石刚好有 <math>n_i</math> 种，这样的项链的数量。


* Polya计数不仅仅用于数环状结构的对称染色。自己举一个非环状结构（例如某有机化合物），指定有限个颜色，给出pattern inventory。
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.
 
Develop a randomized algorithm <math>randE(\epsilon,\delta)</math>, whose inputs are <math>0<\epsilon<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 given detailed analysis of your algorithm.

Revision as of 08:07, 9 October 2011

Problem 1

Some known facts:

  • Balls-into-bins: [math]\displaystyle{ m }[/math] balls are uniformly and independently thrown to [math]\displaystyle{ n }[/math] bins. If [math]\displaystyle{ m=\Theta(n) }[/math], then the maximum load is [math]\displaystyle{ \Theta\left(\frac{\ln n}{\ln\ln n}\right) }[/math] with high probability.
  • Power of two choices: [math]\displaystyle{ m }[/math] balls are sequentially thrown to [math]\displaystyle{ n }[/math] bins. For each ball, uniformly and independently choose random bins [math]\displaystyle{ i }[/math] and [math]\displaystyle{ j }[/math] (might be the same bin), and throw the ball to the currently less loaded bin among bin [math]\displaystyle{ i }[/math] and bin [math]\displaystyle{ j }[/math]. Assuming that [math]\displaystyle{ m=\Theta(n) }[/math], after all [math]\displaystyle{ m }[/math] balls are thrown to bins, the maximum load is [math]\displaystyle{ \Theta\left(\ln \ln n\right) }[/math] with high probability.

Questions: Assume [math]\displaystyle{ n }[/math] balls and [math]\displaystyle{ n }[/math] bins. We throw the [math]\displaystyle{ n }[/math] balls sequentially.

  1. If we throw the first [math]\displaystyle{ \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?
  2. For the [math]\displaystyle{ k }[/math]th ball, if [math]\displaystyle{ k }[/math] is even, we throw the ball to a uniform bin; and if [math]\displaystyle{ 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?

Problem 2

  1. Generalize the LazySelect algorithm for the general selection problem: finding the [math]\displaystyle{ k }[/math]th smallest element in an array. Choose appropriate parameters to do the job.
  2. 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.

Problem 3

The Monte Carlo method for computing [math]\displaystyle{ \mathrm{e} }[/math]

Suppose there are [math]\displaystyle{ n }[/math] peoples, each wearing a hat. We collect all their hats and randomly distribute the hats back to them, with each people receiving one hat. We ask for the probability that none of the people receive his/her own hat. We denote this probability by [math]\displaystyle{ p(n) }[/math]

Formally, a permutation is a bijection [math]\displaystyle{ \pi:[n]\xrightarrow[\text{1-1}]{\text{onto}}[n] }[/math]. A fixed point for permutation [math]\displaystyle{ \pi }[/math] is an [math]\displaystyle{ i\in[n] }[/math] such that [math]\displaystyle{ \pi[i]=i }[/math]. Then [math]\displaystyle{ p(n) }[/math] is the probability that a uniformly random permutation has no fixed point. Such permutations are called derangement.

This derangement problem is taught in undergraduate class Combinatorics at Nanjing University. See the lecture notes for details. By the Principle of Inclusion-Exclusion (容斥原则), we know that [math]\displaystyle{ p(n)=\sum_{k=0}^n\frac{(-1)^k}{k!} }[/math].

Recall that due to Taylor's expansion [math]\displaystyle{ \mathrm{e}=\sum_{k=0}^\infty\frac{(-1)^k}{k!}=p(\infty) }[/math].

Now suppose you are given access to a balckbox [math]\displaystyle{ derange(n) }[/math] which given as input a number [math]\displaystyle{ n }[/math], samples a uniform and independent permutation [math]\displaystyle{ \pi }[/math] of [math]\displaystyle{ [n] }[/math], and returns true if [math]\displaystyle{ \pi }[/math] has no fixed point and false if otherwise.

Develop a randomized algorithm [math]\displaystyle{ randE(\epsilon,\delta) }[/math], whose inputs are [math]\displaystyle{ 0\lt \epsilon\lt 1 }[/math] and [math]\displaystyle{ 0\lt \delta\lt \frac{1}{2} }[/math]. The returned value of the algorithm should satisfy that

[math]\displaystyle{ \Pr[\mathrm{e}-\epsilon\le randE(\epsilon,\delta)\le\mathrm{e}+\epsilon]\ge1-\delta }[/math].
  • Your algorithm should call [math]\displaystyle{ derange(n) }[/math] as subroutine. Try to make both [math]\displaystyle{ n }[/math] and the number of times calling [math]\displaystyle{ derange(n) }[/math] as small as possible.
  • Please given detailed analysis of your algorithm.
Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=组合数学_(Fall_2011)/Problem_set_2&oldid=5055"