课程主页:

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

这次回顾HW5。

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)

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

交换前后的结果如下

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

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

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

  • 对于$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$

所以交换前后的增量为

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

(c)

考虑如下例子:

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

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

但是显然最优解为(不包含-100):

(d)

考虑如下例子:

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

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

但是显然最优解为

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,j,k)$最小化

应该取

显然贪心算法对应此解。

(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)

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