CS170 Efficient Algorithms and Intractable Problems HW13

课程主页：

https://cs170.org/

https://inst.eecs.berkeley.edu/~cs170/fa18/

课程视频：

https://www.bilibili.com/video/BV1wK411g7ck

参考资料：

https://blogs.asarkar.com/assets/docs/algorithms-curated/Maximum%20Independent%20Set%20Problem%20-%20Chekuri.pdf

这次回顾HW13。

2. Universal Hashing

备注：

个人感觉这里有个前提条件，就是$a_1,a_2$是从$[m]$中均匀选择的。

(a)

假设$(x_1,x_2)\neq (y_1, y_2)$，并且

$$a_1x_1 + a_2 x_2 \equiv a_1y_1 +a_2 y_2 \bmod m$$

不失一般性，假设$x_2\neq y_2$，那么

$$a_1(x_1 -y_1 )\equiv a_2(x_2 - y_2) \bmod m$$

由于$m$是质数，并且$x_2 -y_2\neq 0$，所以

$$a_2 \equiv (x_2- y_2)^{-1} a_1 (x_1- y_1)\bmod m$$

即存在唯一的$a_2\in [m]$满足条件。

由于$a_1,a_2$是从$[m]$中均匀选择的，所以是Universal Hashing。

(b)

如果$m=2^k$，那么对于$x_2-y_2\neq 0$，不一定存在逆元$(x_2 -y _2)^{-1}$，所以不一定是Universal Hashing。

(c)

如果对于$x\neq y$，我们有

$$f_1(x) = f_2(y)$$

将$f_1$视为固定的函数，那么$f_2$一共有$(m-1)^{m-1}$种选择，注意到全体函数一共有$(m-1)^m$个，从而发生上述事件的概率为

$$\frac{(m-1)^{m-1}}{(m-1)^m}=\frac{1}{m-1}$$

所以是Universal Hashing。

Universal Hashing的定义：https://en.wikipedia.org/wiki/Universal_hashing

3. Preventing Conflicts

(a)

同hw5。

(b)

将小于等于$|V|$的数利用比特表示并将比特数补齐为偶数，不妨设为比特数量为$n$，显然$n=O(\log|V|)$。

现在考虑如下算法：

• 投掷均匀的硬币$n$次，得到$[a_0, \ldots ,a_{n-1}]$，

• 对于$i\in [1,\ldots, |V|]$，假设其比特表示为$[b_0,\ldots, b_{n-1}]$，如果

  $$\sum_{i=0}^{n-1} 1(a_i =b_i) > \frac{n}{2}$$

  那么将$i$放在左边，否则放在右边。

显然投掷筛子的数量为$O(\log |V| )$，所以只要说明

$$\mathbb P \left(\sum_{i=0}^{n-1} 1(a_i =b_i)> \frac{n}{2} \right) =\frac 1 2$$

即可。

令

$$X_i = 1(a_i =b_i)$$

那么

$$\mathbb P(X_i=1) = \frac 1 2$$

所以

$$\sum_{i=0}^{n-1} 1(a_i =b_i) =\sum_{i=0}^{n-1} X_i \sim B\left(n,\frac 1 2\right)$$

又因为$n$为偶数，所以

$$\mathbb P \left(\sum_{i=0}^{n-1} 1(a_i =b_i)> \frac{n}{2} \right) =\mathbb P\left(X> \frac{n}{2} \right)=\frac 1 2$$

4. Streaming for Voting

同HW2摩尔投票法。