CS170 Efficient Algorithms and Intractable Problems HW6

课程主页：

https://cs170.org/

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

课程视频：

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

参考资料：

https://people.eecs.berkeley.edu/~daw/teaching/cs170-s03/Notes/lecture15.pdf

https://piazza.com/class_profile/get_resource/honxzoabz711ew/hvep5i3vb292gs

这次回顾HW6。

2. Horn Formulas

参考资料：

https://people.eecs.berkeley.edu/~daw/teaching/cs170-s03/Notes/lecture15.pdf

set all variables to false
$W=\{v|(\Rightarrow v)\in \text{formulas} \}$
while $W\neq \varnothing$:
- $\forall v\in W$, delete it from $W$, set it to true
- for clause in formulas $c$ where $v$ in leftside of $c$:
  - delete $v$ from $c$
  - if leftside of $c$ is empty:
    - $W=\{c\}\cup W$

假设Horn Formula的长度为$n$，那么上述算法的时间复杂度为$O(n)$。

3. Graph Game

参考资料：

https://piazza.com/class_profile/get_resource/honxzoabz711ew/hvep5i3vb292gs

(a)

在权重都非负的情形下，不标记节点会让分数更小。

(b)

按照权重按从大到小的顺序进行操作，权重相同的节点取任意顺序即可，假设排序后得到序列

$w_1\ge w_2\ge \ldots \ge w_n$

交换前后的结果如下

i,...,k,...,j
j,...,k,...,i

现在考虑交换$w_i,w_j, i < j$后的结果，记

$\begin{aligned} S_i &=\{k| (i,k) \in G, i<k<j\}\\ S_j &=\{k| (k,j) \in G, i<k<j\}\ \end{aligned}$

交换前后分数和的变换量如下：

对于$i$，增加$|S_i|w_i$
对于$j$，减少$|S_j|w_j$
对于$S_i$，减少$\sum_{k\in S_i} w_k$
对于$S_j$，增加$\sum_{k\in S_j} w_k$

所以交换前后的增量为

$\begin{aligned} |S_i|w_i-|S_j|w_j-\sum_{k\in S_i} w_k + \sum_{k\in S_j} w_k &= \sum_{k\in S_i}(w_i-w_k) +\sum_{k\in S_i}(w_k-w_j)\\ &\le 0 + 0\\ &=0 \end{aligned}$

交换后得到更小的分数和，因此按照权重从大到小排列得到为最优序列。

(c)

考虑如下例子：

(2, -3)
(-3, -4)
(2, -4)

那么按照该算法得到的结果为：

$0+ 2 + (-1)=1$

但是显然最优解为（不包含-100）：

$2$

(d)

考虑如下例子：

(2, 1)
(1, -1)
(2, -1)

那么按照该方法得到的结果为：

$0+ 2 = 2$

但是显然最优解为

$0+2+ 3=6$

4. Tree Perfect Matching

从叶节点开始处理即可：

标记$\text{match}[v]=\text{null},v\in V$
while True:
- for $v\in$ leave nodes:
  - $e=(u, v)\in E$
  - if $\text{match}[v] !=\text{null}$:
    - return false
  - $\text{match}[u]=\text{match}[v]= e$
  - delete $e$
return match

时间复杂度显然为$O(|V|+|E|)=O(|V|)$。

显然该算法返回的match是正确的，只要说明不会在有解的情形返回无解即可：

对于叶节点$v$，假设其父节点为$u$，那么$u,v$对应的边必然是$e=(u,v)$；如果$u$还有另一个子节点$v’$，那么$u,v’$对应的边必然是$e=(u,v’)$，这就产生了矛盾（$u$对应两条边），此时应该返回false。

5. Steel Beams

(a)

(i)

对于任意$T\in \mathbb Z^{+}$，要使得

$i+2j+5k = T$

的解$(i,j,k)$最小化

$i+j+k$

应该取

$\begin{aligned} i&= T-2j-5k\\ j&= \lfloor (T- 5k)/2\rfloor\\ k&= \lfloor T/5\rfloor \end{aligned}$

显然贪心算法对应此解。

(ii)

反例如下：

1, 3, 4, T = 6

(b)

init $\text{dp}[0,\ldots,T]=\infty$
$\text{dp}[0]=0$
for $i=1,\ldots, T$:
- for $j=1,\ldots, k$:
  - if $c_j > i$:
    - break
  - $\text{dp}[i]= \min(\text{dp}[i], \text{dp}[i-c_j]+1)$
return $\text{dp}[T]$

6. Longest Increasing Subsequence

$O(n)$时间是显然的，但是算法不正确，反例如下：

1 2 1 2

算法计算的结果：

M[1]: 1
M[2]: 2
M[3]: 2
M[4]: 3

7. Propositional Parentheses

(a)

根据定义，$A$的长度为$2m-1$，其中奇数项为$T/F$（下标从$1$开始），偶数项为$\vee, \wedge$，定义如下算法：

$t[m][m]=0$（$t[i][j]$表示将$A[2i-1,\ldots,2j-1]$表示为$T$的个数）
$f[m][m]=0$（$f[i][j]$表示将$A[2i-1,\ldots,2j-1]$表示为$F$的个数）
for $i=1,\ldots, m$:
- if $A[2i - 1]= T$:
  - $t[i][i] = 1$
- else:
  - $f[i][i]=1$
for $l=2,\ldots, m $:
- for $i=1,\ldots, \min(m, i + l -1)$:
  - $j= i + l - 1$
  - for $k=i,\ldots,j - 1$:
    - if $A[2i] = \vee$:
      - $t[i][j] += (t[i][k] + f[i][k])\times (t[k+1][j] + f[k+1][j])-f[i][k]\times f[k+1][j] $
      - $f[i][j] += f[i][k]\times f[k+1][j]$
    - else:
      - $t[i][j] += t[i][k] \times t[k+1][j] $
      - $f[i][j] += (t[i][k] + f[i][k])\times (t[k+1][j] + f[k+1][j])-t[i][k] \times t[k+1][j]$
return $t[1][m]$

时间复杂度为$O(m^3)$。

(b)

根据之前的算法，可得概率为

$p=\frac{t[1][m]}{t[1][m] + f[1][m]}$