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

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.