imported>Etone |
imported>Etone |
| Line 1: |
Line 1: |
| *作业电子版于2019/10/9 00:00am之前提交到邮箱 njuadvalg@163.com
| |
| *每道题目的解答都要有<font color="red" size=5>完整的解题过程</font>。中英文不限。
| |
|
| |
| == Problem 1 == | | == Problem 1 == |
| Modify the Karger's Contraction algorithm so that it works for the ''weighted min-cut problem''. Prove that the modified algorithm returns a weighted minimum cut with probability at least <math>\frac{2}{n(n-1)}</math>.
| | (Matching vs. Star) |
| The weighted min-cut problem is defined as follows.
| |
|
| |
|
| *'''Input''': an undirected weighted graph <math>G(V, E)</math>, where every edge <math>e \in E</math> is associated with a positive real weight <math>w_e</math>;
| | Given a graph <math>G(V,E)</math>, a ''matching'' is a subset <math>M\subseteq E</math> of edges such that there are no two edges in <math>M</math> sharing a vertex, and a ''star'' is a subset <math>S\subseteq E</math> of edges such that every pair <math>e_1,e_2\in S</math> of distinct edges in <math>S</math> share the same vertex <math>v</math>. |
| *'''Output''': a cut <math>C</math> in <math>G</math> such that <math>\sum_{e \in C} w_e</math> is minimized.
| |
|
| |
|
| == Problem 2 ==
| | Prove that any graph <math>G</math> containing more than <math>2(k-1)^2</math> edges either contains a matching of size <math>k</math> or a star of size <math>k</math>. |
| Let <math>G=(V,E)</math> be a graph, where <math>n = |V|</math> and <math>m = |E|</math>. In class, we generated a random cut <math>\{S,T\}</math> by sampling <math>X_v \in \{0,1\}</math> uniformly and independently for each <math>v \in V</math> and constructing <math>S = \{v \in V \mid X_v = 1 \}</math> and <math>T = \{v \in V \mid X_v = 0 \}</math>. Now, consider an alternative way to generate the random cut <math>\{S,T\}</math>. Suppose that <math>n</math> is an even number. Define a collection of subset as
| |
| :<math>\mathcal{F} = \{H \subseteq V: |H| = n /2 \}</math>.
| |
| We sample a random subset <math>S \in \mathcal{F}</math> uniformly at random and construct <math>T = V \setminus S</math>.
| |
| * Give the expected size <math>|E(S,T)|</math> of such random cut.
| |
| * Let <math>\mathcal{R}(\cdot)</math> denote such a random source that given any <math>0\leq p\leq 1</math>, <math>\mathcal{R}(p)</math> returns an independent random sample <math>X \in \{0,1\}</math> such that <math>\Pr[X= 1] = p</math>. Give an algorithm that uses <math>\mathcal{R}(\cdot)</math> as a subroutine to generate random subset <math>S \in \mathcal{F}</math> uniformly at random. Prove the correctness of your algorithm. Analyze the number of times that the random sources is called by the algorithm.
| |
|
| |
|
| == Problem 3 ==
| | (Hint: Learn from the proof of Erdos-Rado's sunflower lemma.) |
| Two ''rooted'' trees <math>T_1</math> and <math>T_2</math> are said to be '''isomorphic''' if there exists a bijection <math>\phi</math> that maps vertices of <math>T_1</math> to those of <math>T_2</math> satisfying the following condition: for each ''internal'' vertex <math>v</math> of <math>T_1</math> with children <math>u_1, u_2, ..., u_k</math>, the set of children of vertex <math>\phi(v)</math> in <math>T_2</math> is precisely <math>\{\phi(u_1), \phi(u_2),...,\phi(u_k)\}</math>, no ordering among children assumed.
| |
|
| |
|
| Given an efficient randomized algorithm with bounded one-side error (false positive), for testing isomorphism between rooted trees with <math>n</math> vertices. Analyze your algorithm.
| | == Problem 2 == |
| | | (Frankl 1986) |
| == Problem 4 == | |
| Design a randomized algorithm to decide if an integer sequence <math>a_1,...,a_n</math> is a permutation of another integer sequence <math>b_1,...,b_n</math>. Bound the probability of the error and analyze the time complexity.
| |
| | |
| == Problem 5 ==
| |
| Let <math>X_1,X_2,\ldots,X_n</math> be <math>n</math> random variables, where each <math>X_i \in \{0, 1\}</math> follows the distribution <math>\mu_i</math>. For each <math>1\leq i \leq n</math>, let <math>\rho_i = \mathbb{E}[X_i]</math> and assume <math>\rho_i \geq \frac{1}{2}</math>. Consider the problem of estimating the value of
| |
| :<math>Z = \prod_{i = 1}^n \rho_i</math>.
| |
| For each <math>1\leq i \leq n</math>, the algorithm draws <math>s</math> random samples <math>X_i^{(1)},X_i^{(2)},\ldots,X_i^{(s)}</math> independently from the distribution <math>\mu_i</math>, and computes
| |
| :<math>\widehat{Z}_{i}=\frac{1}{s}\sum_{j=1}^s X_i^{(j)}</math>.
| |
| Finally, the algorithm outputs the product of all <math>\widehat{Z}_{i}</math>:
| |
| :<math>\widehat{Z}=\prod_{i= 1}^n\widehat{Z}_i</math>.
| |
| Express <math>s</math> as a function of <math>n,\varepsilon,\delta</math> so that the output <math>\widehat{Z}</math> satisfies
| |
| :<math>\Pr\left[\mathrm{e}^{-\varepsilon}Z \leq \widehat{Z} \leq \mathrm{e}^{\varepsilon}Z\right] \geq 1- \delta</math>.
| |
| Try to make <math>s</math> as small as possible.
| |
|
| |
|
| == Problem 6 ==
| | Let <math>\mathcal{F}\subseteq {[n]\choose k}</math> be a <math>k</math>-uniform family, and suppose that it satisfies that <math>A\cap B \not\subset C</math> for any <math>A,B,C\in\mathcal{F}</math>. |
| In Balls-and-Bins model, we throw <math>m</math> balls independently and uniformly at random into <math>n</math> bins. We know that the maximum load is <math>\Theta\left(\frac{\log n}{\log\log n}\right)</math> with high probability when <math>m=\Theta(n)</math>.
| | * Fix any <math>B\in\mathcal{F}</math>. Show that the family <math>\{A\cap B\mid A\in\mathcal{F}, A\neq B\}</math> is an anti chain. |
| The two-choice paradigm is another way to throw <math>m</math> balls into <math>n</math> bins: each ball is thrown into the least loaded of two bins chosen independently and uniformly at random(it could be the case that the two chosen bins are exactly the same, and then the ball will be thrown into that bin), and breaks the tie arbitrarily. When <math>m=\Theta(n)</math>, the maximum load of two-choice paradigm is known to be <math>\Theta(\log\log n)</math> with high probability, which is exponentially less than the maxim load when there is only one random choice. This phenomenon is called '''''the power of two choices'''''.
| | * Show that <math>|\mathcal{F}|\le 1+{k\choose \lfloor k/2\rfloor}</math>. |
|
| |
|
| Here are the questions:
| | ==Problem 3 == |
| *Consider the following paradigm: we throw <math>n</math> balls into <math>n</math> bins. The first <math>\frac{n}{2}</math> balls are thrown into bins independently and uniformly at random. The remaining <math>\frac{n}{2}</math> balls are thrown into bins using the two-choice paradigm. What is the maximum load with high probability? You need to give an asymptotically tight bound (in the form of <math>\Theta(\cdot)</math>).
| | An <math>n</math>-player tournament (竞赛图) <math>T([n],E)</math> is said to be '''transitive''', if there exists a permutation <math>\pi</math> of <math>[n]</math> such that <math>\pi_i<\pi_j</math> for every <math>(i,j)\in E</math>. |
|
| |
|
| *Replace the above paradigm to the following: the first <math>\frac{n}{2}</math> balls are thrown into bins using the two-choice paradigm while the remaining <math>\frac{n}{2}</math> balls are thrown into bins independently and uniformly at random. What is the maximum load with high probability in this case? You need to give an asymptotically tight bound.
| | Show that for any <math>k\ge 3</math>, there exists a finite <math>N(k)</math> such that every tournament of <math>n\ge N(k)</math> players contains a transitive sub-tournament of <math>k</math> players. Express <math>N(k)</math> in terms of Ramsey number. |
|
| |
|
| *Replace the above paradigm to the following: assume all <math>n</math> balls are thrown in a sequence. For every <math>1\le i\le n</math>, if <math>i</math> is odd, we throw <math>i</math>-th ball into bins independently and uniformly at random, otherwise, we throw it into bins using the two-choice paradigm. What is the maximum load with high probability in this case? You need to give an asymptotically tight bound.
| | ==Problem 4== |
| | We color each non-empty subset of <math>[n]=\{1,2,\ldots,n\}</math> with one of the <math>r</math> colors in <math>[r]</math>. Show that for any finite <math>r</math> there is a finite <math>N</math> such that for all <math>n\ge </math>$, for any <math>r</math>-coloring of all non-empty subsets of <math>[n]</math>, there always exist <math>1\le i<j<k\le n</math> such that the intervals <math>[i,j)=\{i,i+1,\ldots, j-1\}</math>, <math>[j,k)=\{j,j+1,\ldots, k-1\}</math> and <math>[i,k)=\{i,i+1,\ldots, k-1\}</math> are all assigned with the same color by the <math>r</math>-coloring. |
Problem 1
(Matching vs. Star)
Given a graph [math]\displaystyle{ G(V,E) }[/math], a matching is a subset [math]\displaystyle{ M\subseteq E }[/math] of edges such that there are no two edges in [math]\displaystyle{ M }[/math] sharing a vertex, and a star is a subset [math]\displaystyle{ S\subseteq E }[/math] of edges such that every pair [math]\displaystyle{ e_1,e_2\in S }[/math] of distinct edges in [math]\displaystyle{ S }[/math] share the same vertex [math]\displaystyle{ v }[/math].
Prove that any graph [math]\displaystyle{ G }[/math] containing more than [math]\displaystyle{ 2(k-1)^2 }[/math] edges either contains a matching of size [math]\displaystyle{ k }[/math] or a star of size [math]\displaystyle{ k }[/math].
(Hint: Learn from the proof of Erdos-Rado's sunflower lemma.)
Problem 2
(Frankl 1986)
Let [math]\displaystyle{ \mathcal{F}\subseteq {[n]\choose k} }[/math] be a [math]\displaystyle{ k }[/math]-uniform family, and suppose that it satisfies that [math]\displaystyle{ A\cap B \not\subset C }[/math] for any [math]\displaystyle{ A,B,C\in\mathcal{F} }[/math].
- Fix any [math]\displaystyle{ B\in\mathcal{F} }[/math]. Show that the family [math]\displaystyle{ \{A\cap B\mid A\in\mathcal{F}, A\neq B\} }[/math] is an anti chain.
- Show that [math]\displaystyle{ |\mathcal{F}|\le 1+{k\choose \lfloor k/2\rfloor} }[/math].
Problem 3
An [math]\displaystyle{ n }[/math]-player tournament (竞赛图) [math]\displaystyle{ T([n],E) }[/math] is said to be transitive, if there exists a permutation [math]\displaystyle{ \pi }[/math] of [math]\displaystyle{ [n] }[/math] such that [math]\displaystyle{ \pi_i\lt \pi_j }[/math] for every [math]\displaystyle{ (i,j)\in E }[/math].
Show that for any [math]\displaystyle{ k\ge 3 }[/math], there exists a finite [math]\displaystyle{ N(k) }[/math] such that every tournament of [math]\displaystyle{ n\ge N(k) }[/math] players contains a transitive sub-tournament of [math]\displaystyle{ k }[/math] players. Express [math]\displaystyle{ N(k) }[/math] in terms of Ramsey number.
Problem 4
We color each non-empty subset of [math]\displaystyle{ [n]=\{1,2,\ldots,n\} }[/math] with one of the [math]\displaystyle{ r }[/math] colors in [math]\displaystyle{ [r] }[/math]. Show that for any finite [math]\displaystyle{ r }[/math] there is a finite [math]\displaystyle{ N }[/math] such that for all [math]\displaystyle{ n\ge }[/math]$, for any [math]\displaystyle{ r }[/math]-coloring of all non-empty subsets of [math]\displaystyle{ [n] }[/math], there always exist [math]\displaystyle{ 1\le i\lt j\lt k\le n }[/math] such that the intervals [math]\displaystyle{ [i,j)=\{i,i+1,\ldots, j-1\} }[/math], [math]\displaystyle{ [j,k)=\{j,j+1,\ldots, k-1\} }[/math] and [math]\displaystyle{ [i,k)=\{i,i+1,\ldots, k-1\} }[/math] are all assigned with the same color by the [math]\displaystyle{ r }[/math]-coloring.