高级算法 (Fall 2019)/Problem Set 1

Under construction

• 每道题目的解答都要有完整的解题过程。中英文不限。

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]\displaystyle{ \frac{2}{n(n-1)} }[/math]. The weighted min-cut problem is defined as follows.

• Input: an undirected weighted graph $G(V, E)$, where every edge $e \in E$ is associated with a positive real weight $w_e$;
• Output: a cut $C$ in $G$ such that $\sum_{e \in C} w_e$ is minimized.

Problem 2

Let $G=(V,E)$ be a graph, where $n = |V|$ and $m = |E|$. In class, we generate a random $S-T$ cut by sampling $X_v \in \{0,1\}$ uniformly and independently for each $v \in V$ and constructing $S = \{v \in V \mid X_v = 1 \}$ and $T = \{v \in V \mid X_v = 0 \}$. Now, consider an alternative way to generate the random $S-T$ cut. Suppose $n$ is an even number. Define a collection of subset as

\mathcal{F} = \{H \subseteq V: |H| = n /2 \}

We sample a random subset $S \in \mathcal{F}$ uniformly at random and construct $T = V \setminus S$.

• Find the expected size of such random $S-T$ cut.
• Let $\mathcal{R}(\cdot)$ be a random source. Given any $0\leq p\leq 1$, $\mathcal{R}(p)$ returns an independent random sample $X \in \{0,1\}$ such that $\Pr[X= 1] = p$. Give an algorithm that uses $\mathcal{R}(\cdot)$ to generate random subset $S \in \mathcal{F}$ uniformly at random. Analyze the time complexity of your algorithm.

Problem 3

Two rooted trees $T_1$ and $T_2$ are said to be \textbf{isomorphic} if there exists a bijection $\phi$ that maps vertices of $T_1$ to those of $T_2$ satisfying the following condition: for each \emph{interval} vertex $v$ of $T_1$ with children $u_1, u_2, ..., u_k$, the set of children of vertex $\phi(v)$ in $T_2$ is precisely $\{\phi(u_1), \phi(u_2),...,\phi(u_k)\}$, no ordering among children assumed.

Given an efficient randomized algorithm with bounded one-side error (false positive), for testing isomorphism between rooted trees with $n$ vertices. Analyze your algorithm.

Problem 4

Design a randomized algorithm to decide if an integer sequence $a_1,...,a_n$ is a permutation of another integer sequence $b_1,...,b_n$. Bound the probability of the error and analyze the time complexity.

Problem 5

Let $X_1,X_2,\ldots,X_n$ be $n$ random variables, where each $X_i \in \{0, 1\}$ follows the distribution $\mu_i$. For each $1\leq i \leq n$, let $\rho_i = \E{X_i}$ and assume $\rho_i \geq \frac{1}{2}$. Consider the problem of estimating the value of

Z = \prod_{i = 1}^n \rho_i.

For each $1\leq i \leq n$, the algorithm draws $s$ random samples $X_i^{(1)},X_i^{(2)},\ldots,X_i^{(s)}$ independently from the distribution $\mu_i$, and computes

\widehat{Z}_{i}=\frac{1}{s}\sum_{j=1}^s X_i^{(j)}.

Finally, the algorithm outputs the product of all $\widehat{Z}_{i}$:

\widehat{Z}=\prod_{i= 1}^n\widehat{Z}_i.

Express $s$ as a function of $n,\varepsilon,\delta$ so that the output $\widehat{Z}$ satisfies

\Pr\left[\mathrm{e}^{-\varepsilon}Z \leq \widehat{Z} \leq \mathrm{e}^{\varepsilon}Z\right] \geq 1- \delta.

Try to make $s$ as small as possible.