高级算法 (Fall 2018)/Problem Set 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".
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.
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 .