imported>TCSseminar |
|
| Line 1: |
Line 1: |
| *每道题目的解答都要有<font color="red" size=5>完整的解题过程</font>。中英文不限。
| | == Summary == |
| | | Importing file |
| == Problem 1 ==
| |
| Recall that in class we show by the probabilistic method how to deduce a <math>\frac{n(n-1)}{2}</math> upper bound on the number of distinct min-cuts in any multigraph <math>G</math> with <math>n</math> vertices from the <math>\frac{2}{n(n-1)}</math> lower bound for success probability of Karger's min-cut algorithm.
| |
| | |
| Also recall that the <math>FastCut</math> algorithm taught in class guarantees to return a min-cut with probability at least <math>\Omega(1/\log n)</math>. Does this imply a much tighter <math>O(\log n)</math> upper bound on the number of distinct min-cuts in any multigraph <math>G</math> with <math>n</math> vertices? Prove your improved upper bound if your answer is "yes", and give a satisfactory explanation if your answer is "no".
| |
| | |
| == Problem 2 ==
| |
| | |
| Consider the function <math>f:\mathbb{R}^n\to\mathbb{R}</math> defined as
| |
| | |
| :<math>f(\vec x)=f(x_1,x_2,\dots,x_n)=\prod_{i=1}^{n}(a_ix_i-b_i)</math>,
| |
| | |
| where <math>\{a_i\}_{1\le i\le n}</math> and <math>\{b_i\}_{1\le i\le n}</math> are '''unknown''' coefficients satisfy that <math>a_i, b_i\in \mathbb{Z}</math> and <math>0\le a_i, b_i \le n</math> for all <math>1\le i\le n</math>.
| |
| | |
| Let <math>p>n</math> be the smallest prime strictly greater than <math>n</math>. The function <math>g:\mathbb{Z}_p^n\to\mathbb{Z}_p</math> is defined as
| |
| | |
| :<math>g(\vec x)=g(x_1,x_2,\dots,x_n)=\prod_{i=1}^{n}(a_ix_i-b_i)</math>,
| |
| | |
| where <math>+</math> and <math>\cdot</math> are defined over the finite field <math>\mathbb{Z}_p</math>.
| |
| | |
| By the properties of finite field, for any value <math>\vec r\in\mathbb{Z}_p^n</math>, it holds that <math>g(\vec r)=f(\vec r)\bmod p</math>.
| |
| | |
| Since the coefficients <math>\{a_i\}_{1\le i\le n}</math> and <math>\{b_i\}_{1\le i\le n}</math> are unknown, you can't calculate <math>f(\vec x)</math> directly. However, there exists an oracle <math>O</math>, each time <math>O</math> gets an input <math>\vec x</math>, it immediately outputs the value of <math>g(\vec x)</math>.
| |
| | |
| 1. Prove that <math>f\not\equiv 0 \Rightarrow g\not\equiv 0</math>.
| |
| | |
| 2. Use the oracle <math>O</math> to design an algorithm to determine whether <math>f\equiv 0</math>, with error probability at most <math>\epsilon</math>, where <math>\epsilon\in (0,1)</math> is a constant.
| |
| | |
| == Problem 3 ==
| |
| Fix a universe <math>U</math> and two subset <math>A,B \subseteq U</math>, both with size <math>n</math>. we create both Bloom filters <math>F_A</math>(<math>F_B</math>) for <math>A</math> (<math>B</math>), using the same number of bits <math> m</math> and the same <math>k</math> hash functions.
| |
| *Let <math>F_C = F_A \land F_B</math> be the Bloom filter formed by computing the bitwise AND of <math>F_A</math> and <math>F_B</math>. Argue that <math>F_C</math> may not always be the same as the Bloom filter that are created for <math>A\cap B </math>.
| |
| *Bloom filters can be used to estimate set differences. Express the expected number of bits where <math>F_A</math> and <math>F_B</math> differ as a function of <math>m, n, k</math> and <math>|A\cap B|</math>.
| |
| | |
| == Problem 4 ==
| |
| 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{\rho}_{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{\rho}_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[(1 - \varepsilon) Z \leq \widehat{Z} \leq (1 + \varepsilon)Z\right] \geq 1- \delta</math>.
| |
| Try to make <math>s</math> as small as possible.
| |
| | |
| == Problem 5 ==
| |
| Suppose there is a coin <math> C </math>.
| |
| During each query, it outputs HEAD with probability <math>p</math> and TAIL with probability <math>1-p</math>, where <math> p \in (0, 1) </math> is a real number.
| |
| * Let <math> q \in (0, 1) </math> be another real number. Design an algorithm that outputs HEAD with probability <math>q</math> and TAIL with probability <math>1-q</math>. There is no other random sources for your algorithm except the coin <math>C</math>. Make sure that your algorithm halts with probability <math>1</math>.
| |
| * What is the expected number of queries for the coin <math>C</math> that your algorithm use before it halts?
| |
