高级算法 (Fall 2018)/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 upper bound on the number of distinct min-cuts in any multigraph with vertices from the lower bound for success probability of Karger's min-cut algorithm.

Also recall that the algorithm taught in class guarantees to return a min-cut with probability at least . Does this imply a much tighter upper bound on the number of distinct min-cuts in any multigraph with 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 and are said to be isomorphic if there exists a bijection that maps vertices of to those of satisfying the following condition: for each internal vertex of with children , the set of children of vertex in is precisely , no ordering among children assumed.

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

Problem 3

Fix a universe and two subset , both with size . we create both Bloom filters () for (), using the same number of bits and the same hash functions.

  • Let be the Bloom filter formed by computing the bitwise AND of and . Argue that may not always be the same as the Bloom filter that are created for .
  • Bloom filters can be used to estimate set differences. Express the expected number of bits where and differ as a function of and .