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

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


Problem 1

Recall that in class we show by the probabilistic method how to deduce a ${\displaystyle {\frac {n(n-1)}{2}}}$ upper bound on the number of distinct min-cuts in any multigraph ${\displaystyle G}$ with ${\displaystyle n}$ vertices from the ${\displaystyle {\frac {2}{n(n-1)}}}$ lower bound for success probability of Karger's min-cut algorithm.

Also recall that the ${\displaystyle FastCut}$ algorithm taught in class guarantees to return a min-cut with probability at least ${\displaystyle \Omega (1/\log n)}$. Does this imply a much tighter ${\displaystyle O(\log n)}$ upper bound on the number of distinct min-cuts in any multigraph ${\displaystyle G}$ with ${\displaystyle n}$ 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 ${\displaystyle T_{1}}$ and ${\displaystyle T_{2}}$ are said to be isomorphic if there exists a bijection ${\displaystyle \phi }$ that maps vertices of ${\displaystyle T_{1}}$ to those of ${\displaystyle T_{2}}$ satisfying the following condition: for each internal vertex ${\displaystyle v}$ of ${\displaystyle T_{1}}$ with children ${\displaystyle u_{1},u_{2},\ldots ,u_{k}}$, the set of children of vertex ${\displaystyle \phi (v)}$ in ${\displaystyle T_{2}}$ is precisely ${\displaystyle \{\phi (u_{1}),\phi (u_{2}),\ldots ,\phi (u_{k})\}}$, no ordering among children assumed.

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

Problem 3

Fix a universe ${\displaystyle U}$ and two subset ${\displaystyle A,B\subseteq U}$, both with size ${\displaystyle n}$. we create both Bloom filters ${\displaystyle F_{A}}$(${\displaystyle F_{B}}$) for ${\displaystyle A}$ (${\displaystyle B}$), using the same number of bits ${\displaystyle m}$ and the same ${\displaystyle k}$ hash functions.

• Let ${\displaystyle F_{C}=F_{A}\land F_{B}}$ be the Bloom filter formed by computing the bitwise AND of ${\displaystyle F_{A}}$ and ${\displaystyle F_{B}}$. Argue that ${\displaystyle F_{C}}$ may not always be the same as the Bloom filter that are created for ${\displaystyle A\cap B}$.
• Bloom filters can be used to estimate set differences. Express the expected number of bits where ${\displaystyle F_{A}}$ and ${\displaystyle F_{B}}$ differ as a function of ${\displaystyle m,n,k}$ and ${\displaystyle |A\cap B|}$.