课程主页：

https://cs170.org/

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

课程视频：

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

参考资料：

https://cs170.org/assets/pdf/hw09-sol.pdf

吴彧文（atyuwen）Algorithms.Exercises.solution

这次回顾HW10。

2. Existence of Perfect Matchings

参考：

https://cs170.org/assets/pdf/hw09-sol.pdf

证明：

$\Rightarrow$：

如果$G$有一个完美匹配，那么对于任意$X\subseteq L$，存在$Y\subseteq R,|Y|=|X|$，使得$X$和$Y$相连（利用该完美匹配的一部分即可）。

$\Leftarrow$：

依然使用吴彧文（atyuwen）Algorithms.Exercises.solution 7.23的图：

按照之前的方式增加$S,T$，对于任意Cut $C$，假设$L, N$属于Cut，$M,R$不属于Cut，下面证明$M$为空集。

假设$M$不为空集，那么根据定义可得$V$中至少存在$|M|$个顶点和其相连，但是由于$M$不属于Cut，所以必然不和$V$中顶点相连，这就产生了矛盾，因此必然有$M=\varnothing$，即对于任意的Cut，其大小都为

从而最小割的大小为$|U|$，根据最大流，最小割定理，可得最大流大小为$|U|$。

3. A Redution Warm-up

个人感觉结论错误，考虑下图：

a <-> b
b <-> c

DFS给出的有向图为

a -> b -> c

该有向图存在长度为$|V|-1$的路径，但是显然原图不存在Rudrata路径。

4. Decision vs. Search vs. Optimization

(a)

利用如下方式删除：

  • 删除节点$v$
  • 对于$(u,v)\in E$，如果$u$的度为$1$，则删除$u,(u,v)$；否则仅删除$(u,v)$

注意到

  • 如果$v$不属于最小覆盖，则删除后的图的最小覆盖不变；
  • 否则最小覆盖至少减少一个元素。
    • 这是因为由于删除$v$而删除的节点$u$必然不属于最小覆盖，因为如果$u$属于最小覆盖，那么其度为$1$，但是因为选择了$v$，所以必然不需要选择$u$。

因此可以得到如下算法：

  • for $i=b,b-1,\ldots, 1$:
    • if not decision($i$):
      • $b = i + 1$
      • break
  • $S=\{\}$
  • for $v=1,\ldots, |V|$:
    • remove $v$
    • if decision($b- 1$):
      • $S=S\cup \{v\}$
  • return $S$

第一步是确定最小覆盖的元素数量，第二步是计算具体的最小覆盖。

时间复杂度为

(b)

利用二分搜索确定最优解。

  • $l=1, r=|V|$
  • While ($l< r$):
    • $m = (l + r) / 2$
    • if search($m$):
      • $r = m - 1$
    • else:
      • $l=m$
  • return $l$

时间复杂度为

5. Convex Hull

(a)

procedure ConvexHull(list of points $P[1\ldots n]$)

  • Set $low$ := the point with the minimum $y$-coordinate, breaking ties by minimum $x$-coordinate.
  • Create a list $S[1\ldots n − 1]$ of the remaining points sorted increasingly by the anglebetween the vector $point − low$ and the vector $(1, 0)$ (i.e the x-axis) . Initialize
  • $Hull := [low, S[1],S[2]]$
  • for $p \in S[3\ldots n − 1]$ do
    • if $Hull[-1]$在三角形$p, Hull[-2],low$内部：
      • 删除$S[-1]$
    • $Hull.append(p)$
  • Return $Hull$

时间复杂度为$O(n\log n)$

(b)
  • 假设数组为$[a_1,\ldots, a_n]$
  • 找到最大值$M$，最小值$m$
  • 做变换：$b_i =\frac{a_i - m}{M-m}\in [0, 1]$
  • 构造点集$(\cos b_i, \sin b_i)$
  • 在该点集上计算凸包既可以返回排序后的$b_i$
  • 恢复$a_i=(M-m)b_i + m$

规约时间复杂度：$O(n)$。

正确性是因为，在单位圆上的点的凸包是全体点集。

6. More Reductions

(a)

增加两个非负整数

  • $a_{n+1}=\sum_{i=1}^n a_i$
  • $a_{n+2}=2k$

对非负整数$[a_1,\ldots, a_{n+2}]$调用Partition，那么可以判断是否存在$P\subseteq [n+2]$，满足

注意到

所以$a_{n+1}$和$a_{n+2}$不同属于一个Partition（$n+1\in P, n+2\in [n+2]\backslash P$或者$n+2\in P, n+1\in [n+2]\backslash P$），从而Partition的解可以推出Subset Sum的解。

(b)

取

  • $w_i =a_i$
  • $v_i=a_i$
  • $W=V=k$

那么求解该Knapsack问题可以判断是否存在$P$，满足

即判断是否存在$P$，满足

7. Runtime of NP

错误，因为规约的时间不一定为$O(n^k)$。