(Difference between pages)
imported>TCSseminar |
imported>TCSseminar |
| Line 1: |
Line 1: |
| == Problem 1== | | 截止2018.10.24 13:00，作业3已提交名单如下 |
| Recall that in class we show by the probabilistic method how to deduce a <math>\frac{n(n-1)}{2}</math> upper bound on the number of distinct min-cuts in any multigraph <math>G</math> with <math>n</math> vertices from the <math>\frac{2}{n(n-1)}</math> lower bound for success probability of Karger's min-cut algorithm.
| | {| class="wikitable" |
| | | |171250623 || 姜勇刚 |
| Also recall that the <math>FastCut</math> algorithm taught in class guarantees to return a min-cut with probability at least <math>\Omega(1/\log n)</math>. Does this imply a much tighter <math>O(\log n)</math> upper bound on the number of distinct min-cuts in any multigraph <math>G</math> with <math>n</math> vertices? Prove your improved upper bound if your answer is "yes", and give a satisfactory explanation if your answer is "no".
| | |- |
| | | |DZ1733021 || 夏瑞 |
| == Problem 2 ==
| | |- |
| Two ''rooted'' trees <math>T_1</math> and <math>T_2</math> are said to be '''isomorphic''' if there exists a bijection <math>\phi</math> that maps vertices of <math>T_1</math> to those of <math>T_2</math> satisfying the following condition: for each ''internal'' vertex <math>v</math> of <math>T_1</math> with children <math>u_1,u_2,\ldots, u_k</math>, the set of children of vertex <math>\phi(v)</math> in <math>T_2</math> is precisely <math>\{\phi(u_1), \phi(u_2),\ldots,\phi(u_k)\}</math>, no ordering among children assumed.
| | |DZ1833028 || 徐闽泽 |
| | | |- |
| Give an efficient randomized algorithm with bounded one-sided error (false positive), for testing isomorphism between rooted trees with <math>n</math> vertices. Analyze your algorithm.
| | |151220130 || 伍昱名 |
| | | |- |
| == Problem 3 ==
| | |161250027 || 高忆 |
| Fix a universe <math>U</math> and two subset <math>A,B \subseteq U</math>, both with size <math>n</math>. we create both Bloom filters <math>F_A</math>(<math>F_B</math>) for <math>A</math> (<math>B</math>), using the same number of bits <math> m</math> and the same <math>k</math> hash functions.
| | |- |
| *Let <math>F_C = F_A \and F_B</math> be the Bloom filter formed by computing the bitwise AND of <math>F_A</math> and <math>F_B</math>. Argue that <math>F_C</math> may not always be the same as the Bloom filter that are created for <math>A\cap B </math>.
| | |MP1733012 || 陆璐 |
| *Bloom filters can be used to estimate set differences. Express the expected number of bits where <math>F_A</math> and <math>F_B</math> differ as a function of <math>m, n, k</math> and <math>|A\cap B|</math>.
| | |- |
| | |MF1833009 || 陈越 |
| | |- |
| | |DZ1833011 || 何雨橙 |
| | |} |
Revision as of 05:27, 24 October 2018
截止2018.10.24 13:00，作业3已提交名单如下
| 171250623 |
姜勇刚
|
| DZ1733021 |
夏瑞
|
| DZ1833028 |
徐闽泽
|
| 151220130 |
伍昱名
|
| 161250027 |
高忆
|
| MP1733012 |
陆璐
|
| MF1833009 |
陈越
|
| DZ1833011 |
何雨橙
|