计算复杂性 (Fall 2018) and 高级算法 (Fall 2018)/Problem Set 1: Difference between pages
imported>TCSseminar |
imported>TCSseminar (Created page with "== 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 mul...") |
||
| Line 1: | Line 1: | ||
== 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 == | |||
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,\ldots, 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),\ldots,\phi(u_k)\}</math>, no ordering among children assumed. | |||
Give an efficient randomized algorithm with bounded one-sided error (false positive), for testing isomorphism between rooted trees with <math>n</math> vertices. Analyze your algorithm. | |||
== Problem 3 == | |||
Consider the following problem: | |||
*Fixed a Universe <math>U</math> of size <math>m</math>, given a set <math>S \subseteq U</math> of size <math>n</math> and for each <math>x \in S</math> a <math>r</math>-bit variable <math>v_x</math>, we want to store <math>S</math> and <math>\{v_x\}_{x\in S}</math> into a table, so that the query "Is <math>x\in S</math>, and if so, what's <math>v_x</math>?" can be answer quickly. | |||
The above problem, which is often refered to as '''dictionary''', is a generalization of the set membership problem that we have introduced in class, and there is another hash table called '''bloomier filter''' that solves this problem in linear (<math>O(nr)</math>) space and constant query time with tiny one-sided error probability. | |||
Now if we are allowed to answer arbitrarily when <math>x\notin S</math>, then without resorting to bloomier filter, show that we can store any instance(<math>S</math> and <math>\{v_x\}_{x\in S}</math>) into a table using at most <math>O(nr+\log\log m)</math> bits space, and then correctly answer this relaxed query based on table contents only. | |||
''Hint: You don't have to actually design an algorithm, just prove its existence is fine. You might want to use probabilistic method and [https://en.wikipedia.org/wiki/Perfect_hash_function perfect hashing].'' | |||
Revision as of 13:13, 18 September 2018
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
Two rooted trees [math]\displaystyle{ T_1 }[/math] and [math]\displaystyle{ T_2 }[/math] are said to be isomorphic if there exists a bijection [math]\displaystyle{ \phi }[/math] that maps vertices of [math]\displaystyle{ T_1 }[/math] to those of [math]\displaystyle{ T_2 }[/math] satisfying the following condition: for each internal vertex [math]\displaystyle{ v }[/math] of [math]\displaystyle{ T_1 }[/math] with children [math]\displaystyle{ u_1,u_2,\ldots, u_k }[/math], the set of children of vertex [math]\displaystyle{ \phi(v) }[/math] in [math]\displaystyle{ T_2 }[/math] is precisely [math]\displaystyle{ \{\phi(u_1), \phi(u_2),\ldots,\phi(u_k)\} }[/math], no ordering among children assumed.
Give an efficient randomized algorithm with bounded one-sided error (false positive), for testing isomorphism between rooted trees with [math]\displaystyle{ n }[/math] vertices. Analyze your algorithm.
Problem 3
Consider the following problem:
- Fixed a Universe [math]\displaystyle{ U }[/math] of size [math]\displaystyle{ m }[/math], given a set [math]\displaystyle{ S \subseteq U }[/math] of size [math]\displaystyle{ n }[/math] and for each [math]\displaystyle{ x \in S }[/math] a [math]\displaystyle{ r }[/math]-bit variable [math]\displaystyle{ v_x }[/math], we want to store [math]\displaystyle{ S }[/math] and [math]\displaystyle{ \{v_x\}_{x\in S} }[/math] into a table, so that the query "Is [math]\displaystyle{ x\in S }[/math], and if so, what's [math]\displaystyle{ v_x }[/math]?" can be answer quickly.
The above problem, which is often refered to as dictionary, is a generalization of the set membership problem that we have introduced in class, and there is another hash table called bloomier filter that solves this problem in linear ([math]\displaystyle{ O(nr) }[/math]) space and constant query time with tiny one-sided error probability.
Now if we are allowed to answer arbitrarily when [math]\displaystyle{ x\notin S }[/math], then without resorting to bloomier filter, show that we can store any instance([math]\displaystyle{ S }[/math] and [math]\displaystyle{ \{v_x\}_{x\in S} }[/math]) into a table using at most [math]\displaystyle{ O(nr+\log\log m) }[/math] bits space, and then correctly answer this relaxed query based on table contents only.
Hint: You don't have to actually design an algorithm, just prove its existence is fine. You might want to use probabilistic method and perfect hashing.