课程主页:

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$与其对应,所以

注意到

所以

由此得到更强的结论。

3. Modular Arithmetic

(a)

根据定义可得

那么

(b)

根据定义可得

那么

(c)

4. Wilson’s Theorem

(a)

假设

那么

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

(b)

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

从而

那么

(c)

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

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

如果

那么

注意到

所以

这就产生了矛盾。

(d)

阶乘时间复杂度太高。

5. Random Prime Generation

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

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

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

6. Streaming Algorithms

(a)

假设比特为$a$(初始化为$0$),输入为$b$,那么根据如下方式更新:

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

(b)

假设假设内存为$a$(初始化为$0$),输入为$b$,那么根据如下方式更新:

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

(c)

$1$比特即可,不妨设比特为$a$(初始化为$0$),如果

则令

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

(d)

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

考虑如下算法,假设输入为$b$:

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

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