课程主页:

https://cs170.org/

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

课程视频:

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

参考资料:

https://stackoverflow.com/questions/7938376/weighted-graph-problems-true-false-explanation

https://web.cs.dal.ca/~nauzerk/csci3110/Assignments/A5_Solution_F12.pdf

这次回顾HW4。

2. Maximum Subarray Sum

(a)
  • $s=0,res=-\infty$
  • for $i=0,\ldots, n - 1$:
    • $s = s + a[i]$
    • $res= \max(res, s)$
    • if $s < 0$:
      • $s= 0$
  • return $res$
(b)

$s$表示当前的子列和,如果$s<0$,那么包含这段会使得子列和更小,所以要利用$s=0$舍弃这部分的和。

(c)

时间复杂度显然为$O(n)$。

3. MST Basics

(a)

正确,利用反证法。

如果结论不成立,任取一棵MST $T$,那么$T\cup \{e\}$包含环,删除环中除了$e$以外的边$e’$依然构成MST,注意到$w(e) <w(e’)$,所以权重和更小,这就产生了矛盾。

(b)

正确,根据构造MST的过程即可得证。

(c)

参考资料:

https://stackoverflow.com/questions/7938376/weighted-graph-problems-true-false-explanation

考虑下图:

    1   1
  A---B---C
  |  / \  |
1 | /4 5\ | 1
  |/  6  \|
  D-------E

$BDE$为环,$BD$是唯一的最小权重边,但是MST $DABCE$中显然不包含边$BD$。

(d)

参考资料:

https://web.cs.dal.ca/~nauzerk/csci3110/Assignments/A5_Solution_F12.pdf

正确,利用反证法证明:

如果存在一棵MST $T$,使得$s\to t$的路径上有权重$>r$的边$e$,那么考虑删除$e$后构成的划分($s,t$在划分的两部分),那么由于$s\to$存在$ r$路径,所以存在割$e’ \le r$,那么$T\cup \{e’\} - \{e\}$是一棵权重更小的树,这就产生了矛盾。

4. Prim’s Algorithm

(a)

添加顺序:

B: (A, B)
E: (B, E)
D: (B, D)
C: (B, C)
F: (C, F)
(b)

考虑如下例子:

(A, B) : 3
(B, C) : 2
(C, D) : 1
(A, D) : 4

图示:

	  3
  A ----- B
  |       |
4 |       |  2
  |       |
  D ----- C
  	  1

从$A$开始运行Dijkstra,那么A->D的路径为A->D,但是这条边不会出现在MST中。

5. Divide and Conquer for MST?

不正确,反例依然使用之前的例子:

(A, B) : 3
(B, C) : 2
(C, D) : 1
(A, D) : 4

图示:

	  3
  A ----- B
  |       |
4 |       |  2
  |       |
  D ----- C
  	  1

显然MST为:

 3
A ----- B
        |
        |  2
        |
D ----- C
	  1

如果首先在$\{A,D\}, \{B, C\}$运行算法,那么必然会包括边$(A,D)$,这就产生了矛盾。