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

#### 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$

#### 3. Graph Game

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

##### (b)

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

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

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

#### 5. Steel Beams

##### (a)

(i)

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

• $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]$