课程主页：

https://cs170.org/

https://inst.eecs.berkeley.edu/~cs170/fa18/

课程视频：

https://www.bilibili.com/video/BV1wK411g7ck

这次回顾Section 8。

1. Taking a Dual

对偶问题为

2. Weighted Rock-Paper-Scissors

(a)
r p s
r 0 -5 3
p 5 0 -1
s -3 1 0
(b)

假设策略为$(x_1,x_2,x_3)$，那么LP问题为

3. Domination

(a)

由于$E$支配$D$，所以选择$D$的概率为$0$。

(b)

注意到删除行$D$之后，列$A$严格最优，而列是选择最小值，所以选择$A$的概率为$0$。

(c)

由于列必然不选择$A$，所以剩下可选的行为

	B	C
E	2	-2
F	-2	2

由课本上的讨论可得选择$E,F$的概率都为$\frac 1 2$

4. MT2 Practice: Greedy

(a)
(a1, b1) = (0, 2)
(a2, b2) = (1.5, 2.5)
(a3, b3) = (2.1, 4)

显然最优解为$2$，但是算法$A$给出的结果是$1$。

(b)

利用反证法证明。

假设算法$B$给出的区间集合为$C_1$，如果存在元素更多的区间集合$C_2 $，对应的区间元素分别为

那么根据算法$B$的特点，可以将$C_2$中第一个元素替换为$C_1$中第一个元素，这是因为显然有

这样得到的新集合依然是不相交区间，并且可以将$C_2$中第二个元素替换为$C_1$中第二个元素，如果$|C_2|>|C_1|$，那么经过$|C_1|$次替换后$C_2$还有元素，该元素和$C_1$中最后一个区间不相交，但是根据算法$B$，必然不存在这样的区间，所以必然有

(c)

假设算法$A$得到的区间集合为$C_1$，算法$B$得到的区间集合为$C_2$，对应的区间元素分别为

考虑$(a^{1}_i, b^1_i)$，或者该区间属于$C_2$，或者该区间最多和$C_2$中两个区间相交，这是因为如果和$c_2$中大于两个区间相交，那么必然存在区间$(a_j^2,b_j^2)$满足

因为选择$(a_i^1,b_i^1)$是合理的，所以将其替换为$(a_j^2,b_j^2)$也是合理的，但是根据算法$A$，应该选择$(a_j^2,b_j^2)$，这就产生了矛盾，所以$(a^{1}_i, b^1_i)$最多和$C_2$中两个区间相交，根据此对应关系，我们可得

5. MT2 Practice: MSTs

(a)

如果边的权重不同，那么每次选择最小割时必然是唯一的，所以MST唯一。

(b)

不正确，考虑下图

a					e
	c --------- d
b					f

其中边为$(a, b),(b, c),(a, c);(d,e),(e,f),(d,f);(c,d)$，假设$(c,d)$的权重最大，显然必然包含这条边。

(c)

结论是正确的。

记权重最小的唯一边为$a$，利用反证法，如果$a$不属于某个MST，那么在MST中添加$a$必然得到环，删除环中某条边得到MST，但是总权重显然更小，这就产生了矛盾。

备注：

这一这题和(b)存在区别，因为(b)可能给出如下证明：

记权重最大的唯一边为$a$，利用反证法，如果$a$属于MST，那么在MST中添加图中任意其他边$b$，然后删除$a$依然得到MST，但是总权重显然更小，这就产生了矛盾。

该证明是错误的，因为不一定存在另一条边$b$，使得将其添加到MST后形成环。

6. MT2 Practice: Dynamic Programming

(a)

考虑如下例子

1: 2
2: 3
3: 1
4: 1

贪心算法产生的路径是

1, 3, 4, 5

最优路径为

1, 2, 5
(b)

记$a[i]$为到达$i$的最少步骤数，给出如下算法

  • $a[1]=0$
  • $a[i]=\infty, i=2,\ldots,n$
  • for $i=2,\ldots,n$
    • for $j=1,\ldots,\min(i-1, d(i))$
      • if $i-j \ge 1$:
        • $a[i]=\min(a[i],a[i-j] + 1)$
  • return $a[n]$