COMP5270 Sample Exam 2 中文详细题解

来源: Sample Exam #2.pdf
说明: 原 PDF 是 sample exam 题目册，没有附官方 solutions。下面是按课程讲义和 tutorial/assignment 思路整理的中文详细题解。
重点: SetCover 的 LP rounding、Las Vegas expected time 的坑、dyadic intervals + CountMinSketch 做 range counting。

---

总览

题目	分值	主题
Problem 1	10	MCQ，覆盖 LV/MC、balls in bins、hashing、KKT、LSH、Max-Cut
Problem 2	15	SetCover 的 ILP/LP relaxation 和 randomized rounding
Problem 3	15	条件期望运行时间 的 Las Vegas algorithm
Problem 4	20	streaming range counting，dyadic intervals，CountMinSketch

---

Problem 1: Multiple Choice

每小题 1 分，答错 0 分，不答 0.5 分。

(1)

题意：如果这 10 道 MCQ 只回答自己非常有把握的题，期望分数是否至少 5？

答案：True。

理由：完全不答 10 题就有

分。若只在自己正确概率大于 时才答，则答题的期望分数至少不低于不答。因此这种策略的期望分数至少是 5。

(2)

题意：expected time 为 的 Las Vegas algorithm 是否总能转成 running time 、失败概率为任意小常数的 Monte Carlo algorithm？

答案：True。

做法：运行原算法最多 步，超时就 abort。由 Markov：

选足够大的常数 ，就能让失败概率变成任意小常数。非超时时 Las Vegas 算法答案一定正确，所以这就是 Monte Carlo。

(3)

题意：向 个 bins 独立均匀扔多少 balls，才能以至少 的概率让每个 bin 至少被 hit 两次？

答案：。

至少 hit 一次就是 coupon collector，已经需要 。至少 hit 两次的 sharp threshold 是

但在 big-Theta 级别仍然是

(4)

题意：CountMinSketch 和 Misra-Gries guarantee 类似，但 Misra-Gries 更快且提供 linear sketch？

答案：False。

Misra-Gries 是 deterministic counter algorithm，不是 linear sketch。CountMinSketch 才是线性 sketch 风格，适合合并 stream / strict turnstile 场景。

(5)

题意：若 来自 strongly universal family，则 是全体独立均匀 bits？

答案：False。

Strongly universal 只保证任意两个不同输入的 hash values 是 independent uniform，也就是 pairwise independence。它不保证所有 的 hash values jointly independent。

经典反例思路： 是 independent fair bits，令 。任意两者 pairwise independent，但三者不是 jointly independent。

(6)

题意：与 separate chaining 不同，open addressing 是否能处理 load factor ？

答案：Cannot。

Open addressing 把所有元素直接存在 array cells 里。若 ，元素数量超过 cell 数量，根本放不下。

(7)

题意：“strongly universal”和“pairwise independent” hash families 是否是同一个概念？

答案：True。

在本课程语境中，strongly universal 的意思就是对任意 ， 和 像两个 independent uniform values。这正是 pairwise independent hash family。

(8)

题意：Karger-Klein-Tarjan algorithm 是哪个问题的 randomized algorithm？

答案：Minimum Spanning Tree。

KKT 是 randomized linear-time MST algorithm。Karger contraction 是 Min-Cut，不要混淆。

(9)

题意：Hamming space 的 LSH sensitivity 最紧是哪一项？

答案：。

Hamming LSH 用随机坐标 ，近点和远点 collision probability 分别约为

对应 sensitivity

(10)

题意：Max-Cut 的 LP relaxation randomized rounding 给出 0.878-factor approximation？

答案：False。

0.878 是 Goemans-Williamson 的 SDP rounding 结果，不是普通 LP relaxation 的 randomized rounding。课程里基础 randomized cut 给出的是 -approximation。

---

Problem 2: SetCover 的 LP Rounding

SetCover：

• universe 是 ；
• 有 sets ；
• set 成本为 ；
• 目标选 覆盖所有元素，并最小化

---

(a) 哪个 ILP 对应 SetCover？

答案：左边。

左边 ILP：

subject to

解释：

• 表示选择 set ；
• 对每个元素 ，约束要求至少一个包含 的 set 被选；
• 目标函数就是选中 sets 的总成本。

右边的变量按元素 定义，不是选择 sets，因此不对应 SetCover。

---

(b) SetCover 解和 ILP 解之间的转换

从 set cover 到 ILP solution

给定 set cover ，定义

因为 覆盖 ，所以对每个 ，存在 使 。于是

目标值：

从 ILP solution 到 set cover

给定 integral feasible solution ，令

对任意元素 ，ILP 约束给出

因为 是 0/1，所以至少有一个 满足 且 ，即 。因此 覆盖 。

成本同样相等：

---

(c) LP relaxation

把

放松成

得到 LP：

subject to

记 LP optimum 为 。因为这是 minimization relaxation，feasible region 变大，所以

其中 是原 SetCover 的最优 integral cost。

---

(d) 固定元素 没被覆盖的概率至多

算法做 轮。每一轮中，对于还没选过的 set ，用概率 选择它。

对固定 set ，经过 轮后它仍未被选择的概率是

现在固定一个元素 。它没被覆盖等价于所有包含它的 sets 都没有被选择：

由于不同 set 的随机选择相互独立：

用 ：

LP constraint 对元素 给出

所以

---

(e) 取 后以至少 概率得到 set cover

令坏事件 表示元素 没被覆盖。由 (d)：

用 union bound：

要让失败概率至多 ，只需

例如取

即可。于是 ，输出是 set cover 的概率至少 。

---

(f) 证明

对 set ，经过 轮后被选中的概率是

用 union bound 或 Bernoulli inequality：

因此

因为

所以

---

(g) 得到 -approximation with probability at least

取

由 (e)，输出是 set cover 的概率至少 。

由 (f)，

用 Markov：

所以成本至多 的概率至少 。

两个好事件同时发生的概率至少

在同时发生时：

• 是合法 set cover；
• 成本

因此算法以至少 的概率输出 -approximation。

---

Problem 3: Las Vegas Algorithm 的 Expected Time

已知 Las Vegas algorithm 的 running time 为 ，满足

并且只知道

---

(a) 证明

用 law of total expectation：

---

(b) 和 的关系

函数

是 convex function。由 Jensen：

也就是说：

这是下界，不是上界。因此 并不能推出 。少量概率落在很大的 上，可能让 爆掉。

---

(c) 构造 使 finite 但

令

先算 ：

公式

在 时给出

所以

但

这说明只控制 不能控制 。

---

构造新 Las Vegas Algorithm

算法 每次运行 至多

步；如果没结束，就重新开始，直到某次结束。

令 表示一次 iteration 中：

---

(d) 证明

在条件 下：

更准确地说，对任意满足 的值，

用 Markov：

因此

对所有 平均后得到

---

(e) 证明

由 Markov inequality：

所以

---

(f) loop 的 expected iterations 是

一次 iteration 成功结束的概率：

每次 iteration 独立重新运行 ，所以 iteration 数服从 geometric-type distribution，期望至多

---

(g) 为什么 是 Las Vegas，并给出 expected time

是 Las Vegas algorithm，所以只要它 terminate，输出就是正确的。

只是反复运行 ，每次超时就丢弃，不会接受错误答案。因此 仍然 always correct，只是 running time random，所以它是 Las Vegas algorithm。

每次 iteration 最多运行

步。由 (f)，expected iterations 是 。所以

这不是 polynomial in ，但至少是一个只依赖 的 finite upper bound。

---

Problem 4: Streaming Range Counting with Dyadic Intervals

有 个人依次到来。第 个人给出

其中 是 identifier， 是 salary。

目标：stream 结束后，对任意 query interval

回答 salary 落在其中的人数

误差要求：

for every fixed query 。

---

(a) 一个简单方法

最直接的方法：维护完整 salary histogram。

建立数组

初始全 0。读到 salary 时：

回答 query 时输出

这是 exact answer，所以满足 99% guarantee，甚至概率为 1。

空间复杂度：

每个 counter 最大为 ，需要 bits。一共 个 counters：

bits。

如果 很大，这对 notepad 来说不现实，所以后面用 dyadic intervals 降空间。

---

(b) Dyadic intervals 有多少个？

题目定义 dyadic intervals：

其中

第 层有 个 intervals，所以总数是

如果 不是 2 的幂，可以 padding 到下一个 power of two，不影响 big-Oh。

---

(c) 任意 interval 可分成 个 dyadic intervals

把 dyadic intervals 看成一棵 binary tree：

• root 是整个 ；
• 每个 node 代表一个 interval；
• 左右 children 把当前 interval 对半分。

对 query interval ，用标准 segment tree decomposition：

1. 从 root 开始；
2. 如果某个 node interval 完全包含在 中，就收下它；
3. 如果完全不相交，就丢掉；
4. 如果部分相交，就递归到 children。

在每一层，最多只有常数个 boundary intervals 需要继续分裂；完全落在 query 中的部分会被直接收下。因此总共选出的 dyadic intervals 数量是

更具体地，通常可以界为 。

---

(d) 画出

当 时，binary tree 是：

                 I_{0,0} = {1,2,3,4}
                /                     \
       I_{1,0} = {1,2}          I_{1,1} = {3,4}
         /          \              /          \
I_{2,0}={1}  I_{2,1}={2}  I_{2,2}={3}  I_{2,3}={4}

这里：

• level ：1 个 interval；
• level ：2 个 intervals；
• level ：4 个 singleton intervals。

---

(e) 用 dyadic estimates 回答任意 range query

假设对所有 dyadic intervals 都有好估计：

其中

对任意 query interval ，由 (c)，可分解为不相交 dyadic intervals：

其中

定义估计：

真实值：

因为这些 intervals 不相交。

误差：

---

(f) 固定 level ，如何估计所有 ？

固定一个 level 。这一层把 salary universe 分成 个 disjoint intervals。

把每个 incoming salary 映射成它所在的 interval index：

于是 stream 变成 interval IDs 的 frequency stream。目标是估计每个 interval ID 的 frequency：

使用 CountMinSketch：

• universe size 至多 ；
• stream length 是 ；
• width ；
• depth ；
• 每个 counter 存到 ，每个 hash seed 存 bits。

CountMinSketch 保证对任意 fixed ：

更精确地说，CountMinSketch 通常给 one-sided guarantee：

with probability at least ，这当然推出 absolute error bound。

空间复杂度：

counter 数量是

每个 counter/hash 相关存储用 bits，所以总空间：

更标准地写成：

bits。

---

(g) 组合所有 levels，得到目标空间和 query time

我们对每个 level

各维护一份 CountMinSketch。

参数选择：

由 (c)，任意 query interval 分解成至多

个 dyadic intervals。

令

为了让 query 中用到的所有 dyadic interval estimates 同时正确，取

于是

Space

单个 level 的空间由 (f) 是

一共有 个 levels，所以总空间：

因为 ：

bits。

这正是题目要求的

Query algorithm

给定 ：

1. 把 分解成 个 dyadic intervals；
2. 对每个 dyadic interval，在对应 level 的 CountMinSketch 中查询；
3. 把这些 estimates 加起来。

Correctness probability

对 query 中的每个 dyadic interval，失败概率至多 。用 union bound：

所以所有 dyadic estimates 同时正确的概率至少 。在这个事件上，由 (e)，总误差至多

因此满足题目 guarantee。

Query time

分解 range 需要

个 dyadic intervals。

每个 CountMinSketch query 需要查 个 rows。

所以每次 range query 的时间是

如果把 hash evaluation 视作 ，这就是最终 query time。

---

最后复习重点

1. SetCover LP rounding：重复 轮，每轮按 选 set；元素未覆盖概率 。
2. SetCover cost bound：，所以 ；再用 Markov 把期望转成高概率。
3. Jensen 的方向： convex，所以 。知道 小，不代表 小。
4. LV 到 capped LV：按 截断，每轮成功概率 ，expected iterations 。
5. Dyadic intervals：任意 range 可拆成 个 dyadic intervals。
6. Range counting sketch：每层维护 CountMinSketch，query 时分解区间并求和，误差预算设为 。