CS170 Efficient Algorithms and Intractable Problems HW12

课程主页：

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

这次回顾HW12。

2. Independent Set Approximation

参考资料：

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

给出如下算法：

• $S\leftarrow \varnothing$:
• while $G\neq \varnothing$:
  • 令$v$为$G$中度最小的节点
  • $S\leftarrow S\cup \{v\}$
  • 从$G$中删除$v$以及其邻居

考虑$S$和$G\backslash S$中节点的关系：

对于任意$u\in S$，最多存在$d$个$v\in G\backslash S$与其对应，所以

$$d |S|\ge |G\backslash S|$$

注意到

$$|S|+ |G\backslash S| = |G|$$

所以

$$\begin{aligned} |G|&=|S|+ |G\backslash S|\\ &\le |S|+ d|S|\\ |S|&\ge \frac{|G|}{d+1} \end{aligned}$$

由此得到更强的结论。

3. Modular Arithmetic

(a)

根据定义可得

$$\begin{aligned} a_1&=b_1 + k_1n \\ a_2&=b_2 + k_2n \\ k_1, k_2 &\in \mathbb Z \end{aligned}$$

那么

$$\begin{aligned} a_1 a_2&=(b_1 + k_1 n)(b_2 + k_2n )\\ &= b_1 b_2 + n(k_1 b_2 + k_2 b_1 + nk_1 k_2)\\ a_1a_2 &\equiv b_1 b_2 \bmod n \end{aligned}$$

(b)

根据定义可得

$$\begin{aligned} a_1&=b_1 + k_1n \\ a_2&=b_2 + k_2n \\ k_1, k_2 &\in \mathbb Z \end{aligned}$$

那么

$$\begin{aligned} a_1 +a_2&=b_1 + k_1 n+b_2 + k_2n\\ &= b_1 b_2 +n(k_1 +k_2)\\ a_1+a_2 &\equiv b_1+ b_2 \bmod n \end{aligned}$$

(c)

$$\begin{aligned} 3^{4001} &\equiv 3\times 9^{2000} \\ &\equiv 3 \times (-1)^{2000}\\ &\equiv 3\times 1\\ &\equiv 3 \bmod 10 \end{aligned}$$

4. Wilson’s Theorem

(a)

假设

$$x^2\equiv 1 \bmod p$$

那么

$$p|(x-1)(x+1)$$

即$p| x- 1$ 或$p | x+1$，结合$1\le x < p$可得

$$x= 1$$

或

$$x= p-1$$

(b)

根据(a)可得，$[2, p-1)$内的数可以两两配对，并且满足

$$xy \equiv 1 \bmod p$$

从而

$$(p-2) !\equiv 1 \bmod p$$

那么

$$\begin{aligned} (p-1)!&\equiv (p-2)!\times (p-1)\\ &\equiv -1 \bmod p \end{aligned}$$

(c)

假设$N$不是质数，那么存在$p,q < N$，满足

$$N= pq$$

不妨设$p\ge 2$，那么

$$q \le N /2 < N -1$$

如果

$$(N-1)!\equiv -1 \bmod N$$

那么

$$(N-1)! = k N -1=kpq -1$$

注意到

$$q | (N- 1)!$$

所以

$$\begin{aligned} (N-1)! &\equiv 0\\ &\equiv kpq -1\\ &\equiv -1 \bmod N \end{aligned}$$

这就产生了矛盾。

(d)

阶乘时间复杂度太高。

5. Random Prime Generation

$n$比特的最大数字为$2^{n}-1$，均小于$2^n$，根据定理可得$n$比特数字中的质数数量为

$$\Theta(2^n/ \log(2^n))=\Theta(2^n /n)$$

所以$n$比特数字中质数的比例为

$$\Theta(2^n/n/2^n)=\Theta(1/n)$$

所以选到质数的概率为$\Theta(1/n)$，根据几何分布的性质可得，在选择到质数之前，平均要采样

$$\Theta(n)$$

6. Streaming Algorithms

(a)

假设比特为$a$（初始化为$0$），输入为$b$，那么根据如下方式更新：

$$a= a\oplus b$$

如果$a=0$，那么表示总和为偶数，否则为奇数。

(b)

假设假设内存为$a$（初始化为$0$），输入为$b$，那么根据如下方式更新：

$$a=a+b\bmod N$$

根据定义，$a$需要的内存数量为$O(\log N)$比特。

(c)

$1$比特即可，不妨设比特为$a$（初始化为$0$），如果

$$N | b$$

则令

$$a = 1$$

如果$a=0$，那么表示乘积不被$N$整除，否则为表示被$N$整除。

(d)

由于要记录指数，所以需要$r$个部分，记为$M[r]$，其中$M[i]$需要的比特数量为$O(\log k_i)$，将$M[i]$初始化为$0$，注意到总空间为

$$O\left(\sum_{i=1}^r \log k_i\right)$$

考虑如下算法，假设输入为$b$：

• for $i=1,\ldots, r$:
  • if $p_i | b$:
    • $M[i] += 1$

如果对每个$i=1,\ldots, r$，都有$M[i] \ge k_i$，则表示$N$整除乘积。