高级算法 (Fall 2021)/Problem Set 1: Difference between revisions
imported>TCSseminar |
imported>TCSseminar No edit summary |
||
| Line 1: | Line 1: | ||
*每道题目的解答都要有<font color="red" size=5>完整的解题过程</font>。中英文不限。 | *每道题目的解答都要有<font color="red" size=5>完整的解题过程</font>。中英文不限。 | ||
== 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 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 1 == | == Problem 1 == | ||
Revision as of 06:35, 12 September 2021
- 每道题目的解答都要有完整的解题过程。中英文不限。
Problem 1
Recall that in class we show by the probabilistic method how to deduce a [math]\displaystyle{ \frac{n(n-1)}{2} }[/math] upper bound on the number of distinct min-cuts in any multigraph [math]\displaystyle{ G }[/math] with [math]\displaystyle{ n }[/math] vertices from the [math]\displaystyle{ \frac{2}{n(n-1)} }[/math] lower bound for success probability of Karger's min-cut algorithm.
Also recall that the [math]\displaystyle{ FastCut }[/math] algorithm taught in class guarantees to return a min-cut with probability at least [math]\displaystyle{ \Omega(1/\log n) }[/math]. Does this imply a much tighter [math]\displaystyle{ O(\log n) }[/math] upper bound on the number of distinct min-cuts in any multigraph [math]\displaystyle{ G }[/math] with [math]\displaystyle{ 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]\displaystyle{ f:\mathbb{R}^n\to\mathbb{R} }[/math] defined as
- [math]\displaystyle{ f(\vec x)=f(x_1,x_2,\dots,x_n)=\prod_{i=1}^{n}(a_ix_i-b_i) }[/math],
where [math]\displaystyle{ \{a_i\}_{1\le i\le n} }[/math] and [math]\displaystyle{ \{b_i\}_{1\le i\le n} }[/math] are unknown coefficients satisfy that [math]\displaystyle{ a_i, b_i\in \mathbb{Z} }[/math] and [math]\displaystyle{ 0\le a_i, b_i \le n }[/math] for all [math]\displaystyle{ 1\le i\le n }[/math].
Let [math]\displaystyle{ p\gt n }[/math] be the smallest prime strictly greater than [math]\displaystyle{ n }[/math]. The function [math]\displaystyle{ g:\mathbb{Z}_p^n\to\mathbb{Z}_p }[/math] is defined as
- [math]\displaystyle{ g(\vec x)=g(x_1,x_2,\dots,x_n)=\prod_{i=1}^{n}(a_ix_i-b_i) }[/math],
where [math]\displaystyle{ + }[/math] and [math]\displaystyle{ \cdot }[/math] are defined over the finite field [math]\displaystyle{ \mathbb{Z}_p }[/math].
By the properties of finite field, for any value [math]\displaystyle{ \vec r\in\mathbb{Z}_p^n }[/math], it holds that [math]\displaystyle{ g(\vec r)=f(\vec r)\bmod p }[/math].
Since the coefficients [math]\displaystyle{ \{a_i\}_{1\le i\le n} }[/math] and [math]\displaystyle{ \{b_i\}_{1\le i\le n} }[/math] are unknown, you can't calculate [math]\displaystyle{ f(\vec x) }[/math] directly. However, there exists an oracle [math]\displaystyle{ O }[/math], each time [math]\displaystyle{ O }[/math] gets an input [math]\displaystyle{ \vec x }[/math], it immediately outputs the value of [math]\displaystyle{ g(\vec x) }[/math].
1. Prove that [math]\displaystyle{ f\not\equiv 0 \Rightarrow g\not\equiv 0 }[/math].
2. Use the oracle [math]\displaystyle{ O }[/math] to design an algorithm to determine whether [math]\displaystyle{ f\equiv 0 }[/math], with error probability at most [math]\displaystyle{ \epsilon }[/math], where [math]\displaystyle{ \epsilon\in (0,1) }[/math] is a constant.
Problem 1
Recall that in class we show by the probabilistic method how to deduce a [math]\displaystyle{ \frac{n(n-1)}{2} }[/math] upper bound on the number of distinct min-cuts in any multigraph [math]\displaystyle{ G }[/math] with [math]\displaystyle{ n }[/math] vertices from the [math]\displaystyle{ \frac{2}{n(n-1)} }[/math] lower bound for success probability of Karger's min-cut algorithm.
Also recall that the [math]\displaystyle{ FastCut }[/math] algorithm taught in class guarantees to return a min-cut with probability at least [math]\displaystyle{ \Omega(1/\log n) }[/math]. Does this imply a much tighter [math]\displaystyle{ O(\log n) }[/math] upper bound on the number of distinct min-cuts in any multigraph [math]\displaystyle{ G }[/math] with [math]\displaystyle{ 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]\displaystyle{ f:\mathbb{R}^n\to\mathbb{R} }[/math] defined as
- [math]\displaystyle{ f(\vec x)=f(x_1,x_2,\dots,x_n)=\prod_{i=1}^{n}(a_ix_i-b_i) }[/math],
where [math]\displaystyle{ \{a_i\}_{1\le i\le n} }[/math] and [math]\displaystyle{ \{b_i\}_{1\le i\le n} }[/math] are unknown coefficients satisfy that [math]\displaystyle{ a_i, b_i\in \mathbb{Z} }[/math] and [math]\displaystyle{ 0\le a_i, b_i \le n }[/math] for all [math]\displaystyle{ 1\le i\le n }[/math].
Let [math]\displaystyle{ p\gt n }[/math] be the smallest prime strictly greater than [math]\displaystyle{ n }[/math]. The function [math]\displaystyle{ g:\mathbb{Z}_p^n\to\mathbb{Z}_p }[/math] is defined as
- [math]\displaystyle{ g(\vec x)=g(x_1,x_2,\dots,x_n)=\prod_{i=1}^{n}(a_ix_i-b_i) }[/math],
where [math]\displaystyle{ + }[/math] and [math]\displaystyle{ \cdot }[/math] are defined over the finite field [math]\displaystyle{ \mathbb{Z}_p }[/math].
By the properties of finite field, for any value [math]\displaystyle{ \vec r\in\mathbb{Z}_p^n }[/math], it holds that [math]\displaystyle{ g(\vec r)=f(\vec r)\bmod p }[/math].
Since the coefficients [math]\displaystyle{ \{a_i\}_{1\le i\le n} }[/math] and [math]\displaystyle{ \{b_i\}_{1\le i\le n} }[/math] are unknown, you can't calculate [math]\displaystyle{ f(\vec x) }[/math] directly. However, there exists an oracle [math]\displaystyle{ O }[/math], each time [math]\displaystyle{ O }[/math] gets an input [math]\displaystyle{ \vec x }[/math], it immediately outputs the value of [math]\displaystyle{ g(\vec x) }[/math].
1. Prove that [math]\displaystyle{ f\not\equiv 0 \Rightarrow g\not\equiv 0 }[/math].
2. Use the oracle [math]\displaystyle{ O }[/math] to design an algorithm to determine whether [math]\displaystyle{ f\equiv 0 }[/math], with error probability at most [math]\displaystyle{ \epsilon }[/math], where [math]\displaystyle{ \epsilon\in (0,1) }[/math] is a constant.
Problem 1
Recall that in class we show by the probabilistic method how to deduce a [math]\displaystyle{ \frac{n(n-1)}{2} }[/math] upper bound on the number of distinct min-cuts in any multigraph [math]\displaystyle{ G }[/math] with [math]\displaystyle{ n }[/math] vertices from the [math]\displaystyle{ \frac{2}{n(n-1)} }[/math] lower bound for success probability of Karger's min-cut algorithm.
Also recall that the [math]\displaystyle{ FastCut }[/math] algorithm taught in class guarantees to return a min-cut with probability at least [math]\displaystyle{ \Omega(1/\log n) }[/math]. Does this imply a much tighter [math]\displaystyle{ O(\log n) }[/math] upper bound on the number of distinct min-cuts in any multigraph [math]\displaystyle{ G }[/math] with [math]\displaystyle{ 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]\displaystyle{ f:\mathbb{R}^n\to\mathbb{R} }[/math] defined as
- [math]\displaystyle{ f(\vec x)=f(x_1,x_2,\dots,x_n)=\prod_{i=1}^{n}(a_ix_i-b_i) }[/math],
where [math]\displaystyle{ \{a_i\}_{1\le i\le n} }[/math] and [math]\displaystyle{ \{b_i\}_{1\le i\le n} }[/math] are unknown coefficients satisfy that [math]\displaystyle{ a_i, b_i\in \mathbb{Z} }[/math] and [math]\displaystyle{ 0\le a_i, b_i \le n }[/math] for all [math]\displaystyle{ 1\le i\le n }[/math].
Let [math]\displaystyle{ p\gt n }[/math] be the smallest prime strictly greater than [math]\displaystyle{ n }[/math]. The function [math]\displaystyle{ g:\mathbb{Z}_p^n\to\mathbb{Z}_p }[/math] is defined as
- [math]\displaystyle{ g(\vec x)=g(x_1,x_2,\dots,x_n)=\prod_{i=1}^{n}(a_ix_i-b_i) }[/math],
where [math]\displaystyle{ + }[/math] and [math]\displaystyle{ \cdot }[/math] are defined over the finite field [math]\displaystyle{ \mathbb{Z}_p }[/math].
By the properties of finite field, for any value [math]\displaystyle{ \vec r\in\mathbb{Z}_p^n }[/math], it holds that [math]\displaystyle{ g(\vec r)=f(\vec r)\bmod p }[/math].
Since the coefficients [math]\displaystyle{ \{a_i\}_{1\le i\le n} }[/math] and [math]\displaystyle{ \{b_i\}_{1\le i\le n} }[/math] are unknown, you can't calculate [math]\displaystyle{ f(\vec x) }[/math] directly. However, there exists an oracle [math]\displaystyle{ O }[/math], each time [math]\displaystyle{ O }[/math] gets an input [math]\displaystyle{ \vec x }[/math], it immediately outputs the value of [math]\displaystyle{ g(\vec x) }[/math].
1. Prove that [math]\displaystyle{ f\not\equiv 0 \Rightarrow g\not\equiv 0 }[/math].
2. Use the oracle [math]\displaystyle{ O }[/math] to design an algorithm to determine whether [math]\displaystyle{ f\equiv 0 }[/math], with error probability at most [math]\displaystyle{ \epsilon }[/math], where [math]\displaystyle{ \epsilon\in (0,1) }[/math] is a constant.