UC Berkeley CS 170 Fall 2023 作业 13

完整题面

列出你的学习小组中所有成员的姓名和 SID。如果你没有合作者，必须明确写出 "none"。

完整题面

有时，局部搜索（local search）算法可以为 NP 困难问题给出不错的近似解。

回顾 Max-Cut（最大割）问题：给定一个无权重图 \(G = (V, E)\)，我们要找到一个割 \((S, T)\)，使得「跨越」割的边数（即一个端点在 \(S\) 中、另一个端点在 \(T\) 中的边）最大化。考虑以下局部搜索算法：

1. 从任意一个割开始（例如 \((S, T) = (V, \emptyset)\)）。
2. 当存在某个顶点 \(v \in S\)，使得将 \(v\) 移到另一边后跨越的边数多于当前割 \((S, T)\)（即 \((S \setminus \{v\}, T \cup \{v\})\) 跨越的边更多），或存在某个 \(v \in T\) 使得 \((S \cup \{v\}, T \setminus \{v\})\) 跨越的边更多时，将 \(v\) 移动到割的另一侧。

现在我们来证明该算法具有的几个保证。

（a）给出该算法迭代次数的上界（即移动顶点的总次数）。

（b）证明当该算法终止时，所得到的割中至少有一半的边跨越该割。

完整题面

有时，极其简单的随机化算法也可以达到相当不错的近似比。

（a）考虑 Max 3-SAT 问题：给定一个实例，包含 \(m\) 个子句，每个子句恰好包含 3 个不同的文字（literal），找出能满足尽可能多子句的赋值。给出一个简单的随机化算法，使其在期望下达到 \(\frac{7}{8}\) 的近似比。也就是说，若最优解满足 \(c\) 个子句，你的算法应能在期望下产生一个满足至少 \(\frac{7c}{8}\) 个子句的赋值。

（b）给定一个 Max 3-SAT 实例 \(I\)，令 \(\mathrm{OPT}_I\) 表示在 \(I\) 中能被任意变量赋值满足的子句的最大比例。在所有实例 \(I\) 上，\(\mathrm{OPT}_I\) 的最小值是多少？换言之，\(\min_I \mathrm{OPT}_I\) 等于多少？

（c）（额外学分）将你在（a）中的算法去随机化（derandomize），即给出一个能达到相同近似比的确定性算法。证明你算法的正确性。

注意：这一小问特别难，请仅在完成作业其余部分且希望额外练习时再尝试。

完整题面

（a）设计一个算法，接收一个由 \([n] := \{1, \ldots, n\}\) 中 \(M\) 个整数组成的流 \(x_1, \ldots, x_M\)，并在任意时刻 \(t\) 能够输出 \(x_1, \ldots, x_t\) 中的一个均匀随机元素。你的算法至多使用关于 \(\log n\) 和 \(\log M\) 的多项式级别的空间。证明算法的正确性并分析空间复杂度。你的算法只能对数据流进行单遍扫描。

（b）对于由 \([n]\) 中 \(2n\) 个整数组成的流 \(S = x_1, \ldots, x_{2n}\)，若 \(j \in [n]\) 出现超过一次，则称 \(j\) 为重复元素。

证明 \(S\) 必须包含一个重复元素，并设计一个算法，以 \(S\) 为输入，以至少 \(1 - \frac{1}{n}\) 的概率输出一个重复元素。你的算法至多使用关于 \(\log n\) 的多项式级别的空间。证明算法的正确性并分析空间复杂度。你的算法只能对数据流进行单遍扫描。

完整题面

在本问题中，假设我们接收一个无限的整数流 \(x_1, x_2, \ldots\)，且每收到一个新整数后必须执行某些计算。由于我们可能会看到大量整数，因此希望限制总共使用的内存。以下所有部分，请给出算法的简要描述及其正确性的简要证明。

（a）证明：仅使用一个比特的内存，我们就能计算目前所见的所有整数之和是偶数还是奇数。

（b）证明：我们可以使用 \(O(\log N)\) 个比特的内存，计算目前所见的所有整数之和是否能被某个固定的整数 \(N\) 整除。

（c）假设 \(N\) 为质数。给出一个算法，检查 \(N\) 是否能整除目前所见的所有整数的乘积，并使用尽可能少的内存比特。

（d）现在，设 \(N\) 为任意整数，并假设已知其质因数分解：\(N = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}\)。给出一个算法，检查 \(N\) 是否能整除目前所见的所有整数的乘积，并使用尽可能少的内存比特。用 \(k_1, \ldots, k_r\) 写出你的算法所使用的比特数。