CS170 Efficient Algorithms and Intractable Problems Section5
课程主页：
https://inst.eecs.berkeley.edu/~cs170/fa18/
课程视频：
https://www.bilibili.com/video/BV1wK411g7ck
这次回顾Section 5。
1.Horn Formula Practice
(a)
| 迭代轮数 | $x$ | $y$ | $z$ | $w$ |
|---|---|---|---|---|
| 0 | f | f | f | f |
| 1 | t | t | f | f |
| 2 | t | t | f | t |
| 3 | 产生矛盾 |
(b)
| 迭代轮数 | $x$ | $y$ | $z$ | $w$ |
|---|---|---|---|---|
| 0 | f | f | f | f |
| 1 | f | f | t | t |
2. Huffiman Proofs
1
假设$i$是出现次数最多的字符，那么其出现比例$p_i > \frac{2}{5}$，在最后一轮之前，每轮至少有个两个字符$j,k$（合并后的字符视为一个字符）出现频率比$i$小，这是因为如果该结论不成立，那么
这就与定义矛盾，因此在最后一轮之前都不会合并$i$，从而$i$在最后一轮合并，由此可得存在长度为$1$的编码。
对于第二个结论，利用反证法证明。
假设结论不成立，设字符$i$的编码长度为$1$，那么在每轮中至少有个两个字符$j,k$（合并后的字符视为一个字符）出现频率比$i$小，因此
这就与定义矛盾，因此假设不成立。
2
此题参考了习题解答。
最长编码长度为$n-1$，该情形在如下条件时达到：
注意到不可能存在长度为$n$的编码，这是因为编码长度等于合并的次数（合并后的次数累加到叶节点的合并次数），而一共只有$n$个节点，所以一个节点最多合并$n-1$次。
3. Finding Counterexamples
(a)
按照贪心算法，路线的权重和为
但是显然最优解为
(b)
此题参考了习题解答。
假设该算法第一轮选择了对角线，那么算法结束，最终结果为$1$，但实际上正确结果为$2$。
为了证明另一个结论，假设贪心算法得到的解为$E_1$（包含$a$条边），最优解为$E_2$（包含$b$条边），那么$\forall e\in E_2$，或者
$e\in E_1$，或者$e$和$E_1$中某条边相交，或者$e$和$E_1$中任意一条边不相交。
注意第三种情形是不可能的，因为如果存在这种边，那么必然会被贪心算法添加至$E_1$。
设$E_2$第$i$种情形对应的数量为$x_i$，注意到这里的边两两不相交，因此第二种情形的每条边最多对应于$E_1$中两条边（因为一条边有两个节点），从而
因此
结论得证。
4. Worst-case Instances for Greedy Set-Cover
此题参考了习题解答。
注意到
利用归纳法不难得出贪心算法的选择顺序为：
5. Planting Trees
(a)
选择奇数项或者偶数项的反例
99, 8, 5, 100选择最大值的反例
3, 8, 7(b)
(c)
对应不选位置$i$的情形：
(d)
对应选位置$i$的情形：
(e)
将之前的结论结合得到如下算法：
- $f(1)= x_1$
- $f(2) = \max(x_1, x_2)$
- for $i=3,\ldots,n$:
- $f(i)=\max(f(i-1), x_i + f(i-2))$
- return $f(n)$