CS170 Efficient Algorithms and Intractable Problems Section2

课程主页：

https://cs170.org/

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

课程视频：

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

这次回顾Section 2。

1. Cubed Fourier

(a)

$$\begin{array}{l} \omega_{3}^{0}: \omega_{9}^{0}, \omega_9^3 ,\omega_9^6\\ \omega_{3}^{1}: \omega_{9}^{1}, \omega_9^4 ,\omega_9^7\\ \omega_{3}^{2}:\omega_{9}^{2}, \omega_9^5 ,\omega_9^8 \end{array}$$

(b)

$$\begin{aligned} P(x) &=a_{0}+a_{1} x+a_{2} x^{2}+\ldots+a_{8} x^{8}\\ &= (a_0 +a_3 x^3+a_6 x^6) + (a_1x +a_4 x^4+a_7 x^7) + (a_2x^2 +a_5 x^5+a_8 x^8) \\ &= A_1(x^3) + xA_2(x^3) +x^2 A_3(x^3) \end{aligned}$$

2. Vandermonde Matrices

记

$$M= \left[\begin{array}{ccccc} 1 & \alpha_{1} & \alpha_{1}^{2} & \ldots & \alpha_{1}^{n-1} \\ 1 & \alpha_{2} & \alpha_{2}^{2} & \ldots & \alpha_{2}^{n-1} \\ & & \ldots & & \\ 1 & \alpha_{n} & \alpha_{n}^{2} & \ldots & \alpha_{n}^{n-1} \end{array}\right]$$

那么

$$\begin{aligned} \left(MM^T \right)_{ij} &= \sum_{k=0}^{n-1} \alpha_i^k \alpha_j^k\\ &= \sum_{k=0}^{n-1} (\alpha_i \alpha_j)^k\\ &= \begin{cases} n & \alpha_i \alpha_j= 1\\ \frac{1-(\alpha_i \alpha_j)^n}{1-\alpha_i \alpha_j}& \alpha_i \alpha_j\neq 1 \end{cases} \end{aligned}$$

要使得$MM^T$为对角矩阵，必然有

$$1-(\alpha_i \alpha_j)^n = 0, i\neq j,\alpha_i \alpha_j\neq 1$$

因为$\alpha_i ,\alpha_j\in \mathbb R$，所以上式必然不可能成立。因此，对于$\alpha_i, \alpha_j\in \mathbb R$，$MM^T$不可能为对角阵，即$M^{-1}\neq c M^T$。

3. Graph Traversal

(a)

$$\begin{aligned} A&: \text{pre}= 1,\text{post} = 6\\ B&: \text{pre}= 2,\text{post} =3 \\ E&: \text{pre}= 4,\text{post} = 5\\ C&: \text{pre}= 7,\text{post} = 20\\ J&: \text{pre}= 8,\text{post} = 19\\ F&: \text{pre}=9 ,\text{post} = 18\\ D&: \text{pre}= 10,\text{post} = 11\\ H&: \text{pre}= 12,\text{post} =17 \\ I&: \text{pre}= 13,\text{post} =16 \\ G&: \text{pre}= 14,\text{post} =15 \end{aligned}$$

(b)

SCC:

• $A$
• $B$
• $E$
• $C,J,F,D$
• $H,I,G$

(c)

略。

4. Short Answer

(a)

正确，因为$(u,v)$是前向边。

(b)

错误，反例如下：

(s, u)
(u, s)
(s, v)

DFS的顺序为：$s, u, v$，并且$u$到$v$存在路径，但是$u$不是$v$的祖先。

(c)

正确，删除DFS搜索树的叶节点。

5. True Source

这部分参考了解答。

方法1

对于有向无环图，计算入度为$0$的节点的数量，如果数量$=1$，则返回true，否则返回false。

正确性说明：

如果只有一个入度为$0$的节点，不妨记为$s$，那么从$s$开始DFS，必然能访问全部节点。

利用反证法即可，假设结论不成立，记录$S$为$s$ DFS遍历的节点。

• 对于任意$v\in V-S$，如果不存在边$(u,v)$，其中$u\in S$，那么由于$G$是有向无环图，$V-S$顶点构成的图也是有向无环图，从而其中存在入度为$0$的点，这就与假设矛盾。
• 如果存在$v\in V-S$，以及边$(u,v ), u\in S$，这就与$v$无法被遍历相矛盾。

如果有大于一个入度为$0$的节点，不妨记为$s_1, s_2$，从$s_i$开始DFS遍历的节点集合为$S_i$，如果$V-(S_1 \cup S_2)\neq \varnothing$，这说明必然有节点无法访问；否则$S_1\cup S_2 = V$，但是从$S_1$中任意节点开始DFS都无法访问$s_2$，从$S_2$中任意节点开始DFS都无法访问$s_1$，这就说明结论成立。

对于有向有环图，首先计算SCC，然后将强联通部件作为节点，得到的新图必然为有向无环图，运行之前的算法即可。

时间复杂度为

$$O(V+E)$$

方法2

在原图上运行DFS，搜索树构成森林，记最后一颗搜索树的根节点为$v$，然后以$v$为起点调用DFS，如果能访问全部节点，则返回true，否则返回false。

正确性说明：

只要说明，如果以$v$为起点调用DFS无法访问全部节点，则不存在能访问全部节点的节点。

依然利用反证法，记$u\neq v$为能访问全部节点的节点，那么$u$必然能访问$v$，但是这显然不可能，因为

• $u$不可能是某棵搜索树的子节点，因为图是有向无环图，存在根节点至$u$的路径说明不存在$u$至根节点的路径。
• $u$同样不可能是第一轮DFS中某棵搜索树的根节点，因为如果$u$可达$v$，那么$v$必然不是某棵搜索树的根节点，这就与假设矛盾。

综上，结论成立。

6. Path Problems on DAGs

(a)

将$G$中节点拓扑排序得到$v_1,\ldots ,v_n$。

利用动态规划算法：构造数组$dp[n]$，其中$dp[i]$表示以$v_i$为终点的最长路径长度，那么可以得到如下算法：

• for $i=1,\ldots, n$
  • 如果$v_i$入度为$0$：
    • $dp[i]=0$
  • 否则：
    • $dp[i] =1+\max_{v_j\to v_i\in E} dp[j]$
• return $\max_{i=1,\ldots,n} dp[i]$

(b)

注意图是有向无环图，所以路径长度小于$n$。

依然使用动态规划算法，构造数组$dp[n][n]$，其中$dp[i][j]$表示，从$s$出发走$j$步到$i$的路径数量，实际上可以只申请一维数组$cnt[n]$，具体算法如下：

• 构造数组$cnt[n]$，初始化每个元素为$0$
• $cnt[s]=1$
• $res = 0$
• for $i=1,\ldots, n-1$:
  • 构造数组$tmp[n]$，初始化每个元素为$0$
  • for $j=1,\ldots, n$:
    • $tmp[j] = \sum_{v_k \to v_j\in E} cnt[k]$
  • $res= res+tmp[t]$
  • for $j=1,\ldots, n$:
    • $cnt[j]=tmp[j]$
• return $res$

时间复杂度：

$$O(|V|^2 |E|)$$

优化方法：

外部的循环可以用拓扑排序来取代。

将$G$中节点拓扑排序得到$v_1,\ldots ,v_n$。

• 构造数组$cnt[n]$，初始化每个元素为$0$
• for $i=1,\ldots, n$:
  • 如果$v_i =s$:
    • $cnt[i]= 1$
  • 否则:
    • $cnt[i] =\sum_{v_j\to v_i\in E} cnt[j]$
• return $cnt[t]$

时间复杂度：

$$O(|V|+ |E|)$$