imported>Etone |
imported>Etone |
| Line 1: |
Line 1: |
| == Problem 1== | | =Count Distinct Elements= |
| For any <math>\alpha\ge 1</math>, a cut <math>C</math> in an undirected (multi)graph <math>G(V,E)</math>is called an <math>\alpha</math>-min-cut if <math>|C|\le\alpha|C^*|</math> where <math>C^*</math> is a min-cut in <math>G</math>.
| |
|
| |
|
| # Give a lower bound to the probability that Karger's Random Contraction algorithm returns an <math>\alpha</math>-min-cut in a graph <math>G(V,E)</math> of <math>n</math> vertices.
| | == An estimator by hashing == |
| # Use the above bound to estimate the number of distinct <math>\alpha</math>-min cuts in <math>G</math>.
| |
|
| |
|
| == Problem 2== | | ==Flajolet-Martin algorithm== |
| Let <math>G(V,E)</math> be an undirected graph with positive edge weights <math>w:E\to\mathbb{Z}^+</math>. Given a partition of <math>V</math> into <math>k</math> disjoint subsets <math>S_1,S_2,\ldots,S_k</math>, we define
| |
| :<math>w(S_1,S_2,\ldots,S_k)=\sum_{uv\in E\atop \exists i\neq j: u\in S_i,v\in S_j}w(uv)</math>
| |
| as the cost of the '''<math>k</math>-cut''' <math>\{S_1,S_2,\ldots,S_k\}</math>. Our goal is to find a <math>k</math>-cut with maximum cost.
| |
| # Give a greedy algorithm for finding the weighted max <math>k</math>-cut. Prove that the approximation ratio is <math>(1-1/k)</math>.
| |
| # Consider the following local search algorithm for the weighted max cut (max 2-cut).
| |
| start with an arbitrary bipartition of <math>V</math> into disjoint <math>S_0,S_1</math>;
| |
| while (true) do
| |
| if <math>\exists i\in\{0,1\}</math> and <math>v\in S_i</math> such that <font color=red>(______________)</font>
| |
| then <math>v</math> leaves <math>S_i</math> and joins <math>S_{1-i}</math>;
| |
| continue;
| |
| end if
| |
| break;
| |
| end
| |
| :Fill in the blank parenthesis. Give an analysis of the running time of the algorithm. And prove that the approximation ratio is 0.5.
| |
|
| |
|
| == Problem 2== | | = Set Membership= |
| A '''matching''' of an undirected graph <math>G(V,E)</math> is a set <math>M\subseteq E</math> of edges such that <math>\forall e_1,e_2\in M, e_1\cap e_2=\emptyset</math>. A matching <math>M\subseteq E</math> is ''maximal'' if <math>\forall e\in E\setminus M</math>, <math>M\cup\{e\}</math> is not a matching. A maximal matching <math>M\subseteq E</math> is ''minimum'' if <math>|M|</math> is smallest among all maximal matchings in <math>G(V,E)</math>. A '''minimum maximal matching''' must also be a '''minimum [https://en.wikipedia.org/wiki/Edge_dominating_set edge dominating set]'''. Finding a minimum maximal matching is '''NP-hard'''.
| | |
| | == Perfect hashing== |
| | |
| | == Bloom filter == |
| | |
| | = Frequency Estimation= |
| | |
| | == Count-min sketch== |