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

From EtoneWiki
Jump to: navigation, search
  • 每道题目的解答都要有完整的解题过程。中英文不限。

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\gt 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

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 4

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?