CS170 Efficient Algorithms and Intractable Problems Hw3
课程主页：
https://inst.eecs.berkeley.edu/~cs170/fa18/
课程视频：
https://www.bilibili.com/video/BV1wK411g7ck
这次回顾Hw3。
2. Disrupting a Network of Spies
(a)
假设$r$的子节点为$r_i, i=1,\ldots,l$，那么只要说明$\forall i\neq j$，不存在$r_i$的后代到$r_j$的后代的路径即可。
证明：
如果存在$r_i$的后代$r_i’$到$r_j$的后代$r_j’$的路径，那么$r_j’$必然是$r_i’$的后代，这就与$r_{j}’$是$r_j$的后代矛盾，所以结论成立。
(b)
假设$v$的子节点为$\{v_i\}$，父节点为$v_p$，现在对树进行旋转，以$v$为根节点，子节点为$\{v_i\}\cup \{v_p\}$。
由条件可得，不存在$\{v_i\}$及其后代到$v_p$及其后代的横跨边，所以这是一棵合理的搜索树，因此
(c)
注意到如果存在和$v$的后代相关的回边，那么回边的另一个节点必然在$v$到根节点的路径上，否则会产生矛盾（类似a中讨论）。
和(c)类似，依然是使用旋转的方式，所以只要判断是否会增加$1$即可，而这和$v$的后代的邻居是是否在搜索树中的深度小于$v$有关，具体如下：
(d)
注意到
以及如果$u$是叶节点（注意此时$u$没有后代），那么
所以可以分两轮计算$\mathrm {up}$：
层序遍历计算$\text{depth}$
$\mathrm{initUp ()}$:
初始化$\mathrm{up}_{T}(u)=\mathrm{depth}_{T}(u) $
for $(u,v)\in E$:
$\mathrm{getUp } (u)$:
如果$u$是叶节点，
- continue
否则，
for $v$ in $u$的子节点：
- $\mathrm{getUp (v)}$
$\mathrm{initUp ()}$
$\mathrm {getUp(root)}$
时间复杂度:
层序遍历：$O(|V| +|E|)$
$\mathrm{initUp ()},\mathrm {getUp(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]$，那么
那么
注意到
因此
(b)
那么
结论成立。
(c)
由多项式的定义可得
(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)
注意到
(b)
所以
(c)
取
5. Connectivity vs Strong Connectivity
(a)
因为是连通图，所以DFS得到一颗搜索树，那么删除搜索树任意叶节点即可。
(b)
a -> b -> c -> d -> a那么删除任意一个节点都不够成强连通图。
(c)
反证法，如果存在节点对$u,v,(u,v)\not\in 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$，初始化
线性化图元，顺序为$i_1,\ldots,i_m$。
for $j=m,\ldots, 1$：
- $m_1[i_j] = \min_{i_j \to k} m_1[k]$
for $i= 1,\ldots,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|)$
所以时间复杂度为
7. Arbitrage
(a)
$i,j$之间边的权重为$\log r_{i,j}$，所以我们的目标是找到路径$s-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)=\infty$
- $\mathrm{prev}(u) = \mathrm{nil}$
- $\mathrm{dist}(s) = 0$
- repeat $k$ times:
- for all $e \in E$:
- $\mathrm{update}(e)$
- for all $e \in E$:
解释：
考虑最短路径树，那么BF算法第$i$轮计算出第$i$层的最短距离，这点利用数学归纳法即可证明。
9. Matrix Filling
将第$i$列视为一个节点，那么节点为$1,2,\ldots, n$，考虑如下算法：
选择未访问的节点$i,j$。
合并$v_i, v_j$，当且仅当存在$k$，使得$v_i[k]\neq \star$并且$v_j[k]\neq \star$，记
for $k=1,\ldots, n$：
- 如果$v_j[k]\neq \star$：
- 如果$v_i[k]=\star$：
- $v_i[k]= \alpha v_j[k]$
- 如果$v_i[k]\neq \alpha v_j[k]$：
- return false
- 如果$v_i[k]=\star$：
- 如果$v_i[k]\neq \star$：
- 如果$v_j[k]=\star$：
- $v_j[k]= v_i[k] /\alpha$
- 如果$v_j[k]\neq v_i[k] /\alpha$：
- return false
- 如果$v_j[k]=\star$：
- 如果$v_j[k]\neq \star$：
标记$j$为访问过。
重复上述操作，最后剩下$k$个节点$i_1,\ldots,i_k$，这些节点满足，任取$\forall s\neq 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)$。