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

每道题目的解答都要有完整的解题过程、分析和证明。中英文不限。

## 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 .