CS170 Efficient Algorithms and Intractable Problems Hw3

距离上次更新已经 1488 天了，文章内容可能已经过时。

课程主页：

https://cs170.org/

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

课程视频：

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

这次回顾Hw3。

2. Disrupting a Network of Spies

(a)

$$f(r)=r\mathrm{的}\mathrm{子}\mathrm{节}\mathrm{点}\mathrm{个}\mathrm{数}$$

假设$r$的子节点为$r_i,i=1,\dots ,l$，那么只要说明$\mathrm{\forall }i\ne j$，不存在$r_i$的后代到$r_j$的后代的路径即可。

证明：

如果存在$r_i$的后代$r_i^{\prime }$到$r_j$的后代$r_j^{\prime }$的路径，那么$r_j^{\prime }$必然是$r_i^{\prime }$的后代，这就与$r_j^{\prime }$是$r_j$的后代矛盾，所以结论成立。

(b)

假设$v$的子节点为$\{v_i\}$，父节点为$v_p$，现在对树进行旋转，以$v$为根节点，子节点为$\{v_i\}\cup \{v_p\}$。

由条件可得，不存在$\{v_i\}$及其后代到$v_p$及其后代的横跨边，所以这是一棵合理的搜索树，因此

$$f(r)=r\mathrm{的}\mathrm{子}\mathrm{节}\mathrm{点}\mathrm{个}\mathrm{数}+1$$

(c)

注意到如果存在和$v$的后代相关的回边，那么回边的另一个节点必然在$v$到根节点的路径上，否则会产生矛盾（类似a中讨论）。

和(c)类似，依然是使用旋转的方式，所以只要判断是否会增加$1$即可，而这和$v$的后代的邻居是是否在搜索树中的深度小于$v$有关，具体如下：

$$f(r)=r\mathrm{的}\mathrm{子}\mathrm{节}\mathrm{点}\mathrm{个}\mathrm{数}+1-[[{\cup }_{i=1}^k{\mathrm{up}}_T\left(w_i\right)<{\mathrm{depth}}_T(v)]]$$

(d)

注意到

$${\mathrm{up}}_T(u)=min(\underset{v\mathrm{是}u\mathrm{的}\mathrm{子}\mathrm{节}\mathrm{点}}{min}{\mathrm{up}}_T(v),\underset{(u,v)\in E}{min}{\mathrm{depth}}_T(v))$$

以及如果$u$是叶节点（注意此时$u$没有后代），那么

$${\mathrm{up}}_T(u)=\underset{(u,v)\in E}{min}{\mathrm{depth}}_T(v)$$

所以可以分两轮计算$\mathrm{up}$：

• 层序遍历计算$\text{depth}$

• $\mathrm{initUp}()$:

  • 初始化${\mathrm{up}}_T(u)={\mathrm{depth}}_T(u)$

  • for $(u,v)\in E$:

    • $$\begin{array}{rl}{\mathrm{up}}_T(u)& =min({\mathrm{up}}_T(u),{\mathrm{depth}}_T(v))\\ {\mathrm{up}}_T(v)& =min({\mathrm{up}}_T(v),{\mathrm{depth}}_T(u))\end{array}$$

  • $\mathrm{getUp}(u)$:

    • 如果$u$是叶节点，

      • continue

    • 否则，

      • for $v$ in $u$的子节点：

        • $\mathrm{getUp}(\mathrm{v})$
      • $${\mathrm{up}}_T(u)=\underset{v\mathrm{是}u\mathrm{的}\mathrm{子}\mathrm{节}\mathrm{点}}{min}{\mathrm{up}}_T(v)$$

  • $\mathrm{initUp}()$

  • $\mathrm{getUp}(\mathrm{root})$

时间复杂度:

• 层序遍历：$O(|V|+|E|)$

• $\mathrm{initUp}(),\mathrm{getUp}(\mathrm{root})$对每个节点和边各遍历一次，所以时间复杂度为$O(|V|+|E|)$

(e)

• 初始化$f[n]=\{0\}$。
• 选择节点$r$，对$v$调用dfs得到搜索树$T$时间复杂度$O(|V|+|E|)$。
• $f[r]=r$的子节点个数。
• 利用(d)部分的算法计算其余$f[v]$，这步时间复杂度为$O(|V|+|E|)$。

总时间复杂度为$O(|V|+|E|)$。

3. Inverse FFT

(a)

记矩阵$M$的第$i$行为$M[i,:]$，第$j$列为$M[:,j]$，那么

$$\begin{array}{rl}{M}_n(\omega )[:,j]& ={\left[\begin{array}{ccccc}1& {\omega }^j& {\omega }^{2j}& \dots & {\omega }^{(n-1)j}\end{array}\right]}^T\\ M_n({\omega }^{-1})[i,:]& =\left[\begin{array}{ccccc}1& {\omega }^{-i}& {\omega }^{-2j}& \dots & {\omega }^{-(n-1)j}\end{array}\right]\end{array}$$

那么

$$\begin{array}{rl}{M}_n({\omega }^{-1})[i,:]M_n(\omega )[:,j]& =\sum _{k=0}^{n-1}{\omega }^{k(j-i)}\\ & =\{\begin{array}{ll}n& i=j\\ \frac{1-{\omega }^{n(j-i)}}{1-\omega }=0& i\ne j\end{array}\end{array}$$

注意到

$$\frac{1}{n}{M}_n\left({\omega }^{-1}\right)M_n(\omega )=\frac{1}{n}{[M_n({\omega }^{-1})[i,:]M_n(\omega )[:,j]]}_{n\times n}$$

因此

$$\frac{1}{n}{M}_n\left(\omega \right)M_n(\omega )=I_n$$

(b)

$$\begin{array}{rl}{M}_n(\omega )[i,j]& ={\omega }^{(i-1)(j-1)}\\ M_n({\omega }^{-1})[i,j]& ={\omega }^{-(i-1)(j-1)}\end{array}$$

那么

$$\begin{array}{rl}{M}_n^{†}(\omega )[i,j]& ={\omega }^{-(j-1)(i-1)}\\ & =M_n({\omega }^{-1})[i,j]\\ \frac{1}{\sqrt{n}}{M}_n(\omega )\frac{1}{\sqrt{n}}{M}_n^{†}(\omega )& =\frac{1}{n}{M}_n(\omega )M_n({\omega }^{-1})\\ & =I_n\end{array}$$

结论成立。

(c)

由多项式的定义可得

$$\begin{array}{rl}\left[\begin{array}{c}C\left(1\right)\\ C\left(\omega \right)\\ ⋮\\ C\left({\omega }_{n-1}\right)\end{array}\right]& =\left[\begin{array}{ccccc}1& 1& 1& \dots & 1\\ 1& \omega & {\omega }^2& \dots & {\omega }^{n-1}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 1& {\omega }^{n-1}& {\omega }^{2(n-1)}& \dots & {\omega }^{(n-1)(n-1)}\end{array}\right]\left[\begin{array}{c}{c}_0\\ c_1\\ ⋮\\ c_{n-1}\end{array}\right]\\ & =M_n(w)\left[\begin{array}{c}{c}_0\\ c_1\\ ⋮\\ c_{n-1}\end{array}\right]\\ \left[\begin{array}{c}{c}_0\\ c_1\\ ⋮\\ c_{n-1}\end{array}\right]& =M_n^{-1}(w)\left[\begin{array}{c}C\left(1\right)\\ C\left(\omega \right)\\ ⋮\\ C\left({\omega }_{n-1}\right)\end{array}\right]\\ & =\frac{1}{n}{M}_n\left({\omega }^{-1}\right)\left[\begin{array}{c}C\left(1\right)\\ C\left(\omega \right)\\ ⋮\\ C\left({\omega }_{n-1}\right)\end{array}\right]\end{array}$$

(d)

推导同课程笔记，只要将$\omega$替换为${\omega }^{-1}$即可：

https://doraemonzzz.com/2021/02/21/%E7%AE%97%E6%B3%95%E6%A6%82%E8%AE%BA(DPV)%E7%AC%AC2%E7%AB%A0%20%E5%88%86%E6%B2%BB%E7%AE%97%E6%B3%95%20%E6%80%BB%E7%BB%93/#toc-heading-9第2章 分治算法 总结/#toc-heading-9)

4. Vandermonde matrix

(a)

注意到

$$\begin{array}{rl}\left[\begin{array}{c}p(0)\\ p(1)\\ p(4)\\ p(7)\end{array}\right]& =V_4(0,1,4,7)\left[\begin{array}{c}1\\ 2\\ 0\\ 1\end{array}\right]\\ & =\left[\begin{array}{cccc}1& 0& 0& 0\\ 1& 1& 1& 1\\ 1& 4& 16& 64\\ 1& 7& 49& 343\end{array}\right]\left[\begin{array}{c}1\\ 2\\ 0\\ 1\end{array}\right]\\ & =\left[\begin{array}{c}1\\ 4\\ 73\\ 358\end{array}\right]\end{array}$$

(b)

$$\begin{array}{rl}\left[\begin{array}{c}p(0)\\ p(1)\\ p(4)\\ p(7)\end{array}\right]& =V_4(0,1,4,7)\left[\begin{array}{c}{p}_0\\ p_1\\ p_2\\ p_3\end{array}\right]\\ & =\left[\begin{array}{cccc}1& 0& 0& 0\\ 1& 1& 1& 1\\ 1& 4& 16& 64\\ 1& 7& 49& 343\end{array}\right]\left[\begin{array}{c}{p}_0\\ p_1\\ p_2\\ p_3\end{array}\right]\\ \left[\begin{array}{c}{p}_0\\ p_1\\ p_2\\ p_3\end{array}\right]& ={\left[\begin{array}{cccc}1& 0& 0& 0\\ 1& 1& 1& 1\\ 1& 4& 16& 64\\ 1& 7& 49& 343\end{array}\right]}^{-1}\left[\begin{array}{c}p(0)\\ p(1)\\ p(4)\\ p(7)\end{array}\right]\\ & ={\left[\begin{array}{cccc}1& 0& 0& 0\\ 1& 1& 1& 1\\ 1& 4& 16& 64\\ 1& 7& 49& 343\end{array}\right]}^{-1}\left[\begin{array}{c}2\\ 0\\ 6\\ 30\end{array}\right]\\ & =\left[\begin{array}{c}2\\ -3\\ 1\\ 0\end{array}\right]\end{array}$$

所以

$$q(x)=x^2-3x+2$$

(c)

取

$$x_i=w^{i-1}$$

5. Connectivity vs Strong Connectivity

(a)

因为是连通图，所以DFS得到一颗搜索树，那么删除搜索树任意叶节点即可。

(b)

a -> b -> c -> d -> a

那么删除任意一个节点都不够成强连通图。

(c)

反证法，如果存在节点对$u,v,(u,v)\notin E$，只有一条$u-v$路径，考虑$u-v$路径中一点$v_0$，那么删除该节点后，不存在$u-v$路径，于是图不连通，这就与假设矛盾。

6. Finding Clusters

• 初始化$m[n]=\{0\}$

• 计算$(V,E)$的SCC，得到每个节点的强连通分量编号$a[n]$以及图元$(V_1,E_1)$，图元的节点数量为$m$，初始化

  $$\begin{array}{rl}& m[i]=m_1[j]=min\{j|a[i]=j\}\\ & j=1,\dots ,m\end{array}$$

• 线性化图元，顺序为$i_1,\dots ,i_m$。

• for $j=m,\dots ,1$：

  • $m_1[i_j]=\underset{i_j\to k}{min}{m}_1[k]$

• for $i=1,\dots ,n$：

  • $m[i]=m_1[a[i]]$

时间复杂度：

• 计算$(V,E)$的SCC：$O(|V|+|E|)$
• 线性化图元：$O(|V_1|+|E_1|)$
• 循环1：每个节点和每个边各访问一次，$O(|V_1|+|E_1|)$
• 循环2：$O(|V|)$

所以时间复杂度为

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

7. Arbitrage

(a)

$i,j$之间边的权重为$\log r_{i,j}$，所以我们的目标是找到路径$s-t$，使得

$$\text{minimize}\sum _{j=0}^{n-1}\log r_{i_j,i_{j+1}},i_0=s,i_n=t$$

(b)

可以转化为单源最短路径问题，利用Bellman-Ford算法即可。

8. Bounded Bellman-Ford

返回Bellman-Ford算法的第$i$轮循环结果：

• procedure $\mathrm{update}((u,v)\in E)$
  • $\mathrm{dist}(v)=min\{\mathrm{dist}(v),\mathrm{dist}(u)+l(u,v)\}$

BF

• procedure shortest-paths$(G,l,s,k)$
• for all $u\in V$:
  • $\mathrm{dist}(u)=\mathrm{\infty }$
  • $\mathrm{prev}(u)=\mathrm{nil}$
• $\mathrm{dist}(s)=0$
• repeat $k$ times:
  • for all $e\in E$:
    • $\mathrm{update}(e)$

解释：

考虑最短路径树，那么BF算法第$i$轮计算出第$i$层的最短距离，这点利用数学归纳法即可证明。

9. Matrix Filling

将第$i$列视为一个节点，那么节点为$1,2,\dots ,n$，考虑如下算法：

• 选择未访问的节点$i,j$。

• 合并$v_i,v_j$，当且仅当存在$k$，使得$v_i[k]\ne \star$并且$v_j[k]\ne \star$，记

  $$\alpha =\frac{v_i[k]}{v_j[k]}$$

• for $k=1,\dots ,n$：

  • 如果$v_j[k]\ne \star$：
    • 如果$v_i[k]=\star$：
      • $v_i[k]=\alpha v_j[k]$
    • 如果$v_i[k]\ne \alpha v_j[k]$：
      • return false
  • 如果$v_i[k]\ne \star$：
    • 如果$v_j[k]=\star$：
      • $v_j[k]=v_i[k]/\alpha$
    • 如果$v_j[k]\ne v_i[k]/\alpha$：
      • return false

• 标记$j$为访问过。

重复上述操作，最后剩下$k$个节点$i_1,\dots ,i_k$，这些节点满足，任取$\mathrm{\forall }s\ne t，v_{i_s}[k],v_{i_t}[k]$不同时为值，即满足类似如下形式：

000111000
110000001
001000010
......
111111011

上图中，标记为$0$的地方表示该位置的值为$\star$，标记为$1$的地方表示填了值，最后为合并后的结果，剩余为$\star$的地方可以填任意值，完成后，根据比例在矩阵中填值即可。

时间复杂度：

每次合并的时间复杂度为$O(n)$，最多合并$n-1$次，最后处理的时间复杂度为$O(kn)$，所以总的时间复杂度为$O(n^2)$。