这一部分将带来Course1 week4的习题解析。

选择题

选择题 1

$n$个节点的树最多有多少个不同的minimum cuts?

  • $n$
  • $C_n^2$
  • $2^n -2$
  • $n-1$

树中minimum cuts对应的边的数量为$1$条，$n$个节点的树有$n-1$条边，每条边对应一个minimum cuts，所以一共有$n-1$个不同的minimum cuts

选择题 2

让“output”表示Karger的min cut算法在给定$n$个点连通图上的结果，并令$p = \frac{1}{\binom n 2}$。

以下哪项陈述属实？

  • 对于每个有$n$个顶点的图$G$和每个min cut $(A,B)$

  • 对于每个有$n$个顶点的图$G$，存在一个min cut $(A,B)$使得

  • 对于每个有$n$个顶点的图$G$，存在一个min cut $(A,B)$使得

  • 对于每个有$n$个顶点的图$G$和每个min cut $(A,B)$

  • 存在一个$n$个顶点的图$G$和一个min cut $(A,B)$

回顾讲义可知，第2，4个选项肯定正确，除此之外，第5个选项也正确，只要取课件中的圆环作为图即可。

选择题 3

$0.5<α<1$。假设您正在使用RANDOMIZED SELECT查找数组中的中间元素（如讲座中所述）。

在第一次迭代之后，您正在寻找的元素所在的子数组的大小 $≤α $倍于原始数组的大小的概率是多少？

  • $\alpha -\frac 1 2 $
  • $2\alpha -1$
  • $1-\frac \alpha 2 $
  • $1-\alpha$

只要我们选择次序位于$1-\alpha$到$\alpha$倍原数组长度的元素即可，所以概率为$\alpha -(1-\alpha) =2\alpha -1$

选择题 4

$0.5<α<1$并且独立于$n$。考虑执行RSelect，你总能抛弃至少$1- α$ 倍剩余元素。在终止之前，您将进行的最大递归调用次数是多少？

  • $-\frac{\log(n)}{\alpha}$
  • $-\frac{\log(n)}{\log(1-\alpha)}$
  • $-\frac{\log(n)}{\log(\frac 12 +\alpha)}$
  • $-\frac{\log(n)}{\log \alpha}$

每一轮至少丢弃$(1-\alpha)$倍的元素，所以$i$轮后剩余元素个数小于等于：

令$\alpha^i n=1$可得

所以第4项正确

选择题 5

minimum s-t cut 问题如下。输入是无向图，图的两个不同顶点标记为“s”和“t”。目标是计算满足s,t在切割的不同侧上的最小切割（即，最少数量的交叉边缘）。

假设有人通过API为您提供了这个minimum s-t cut问题的子程序。你的工作就是解决最初的minimum cut（讲座中讨论的问题），当你所能做的就是调用给定的minimum s-t cut子程序。（也就是说，目标是将minimum cut问题减少到minimum s-t cut问题。）

现在假设给出了一个minimum cut问题的实例 - 也就是说，给出了一个无向图（没有特殊标记的顶点）并且需要计算minimum cut。

您需要调用给定的minimum s-t cut子程序以确保您找到给定图形的minimum cut的最小次数是多少？

  • $2^n$
  • $n-1$
  • $\binom n 2$
  • $n$

对于minimum cut问题，任意一个顶点必然属于cut的某一边，所以我们任取一个顶点$s$，对其余$n-1$个点分别求出minimum s-t cut，然后取其中最小值即可得出minimum cut，所以这题的答案为$n-1$

编程题

实现Random Contraction Algorithm算法：

import numpy as np
import copy

V = {}
with open("kargerMinCut.txt") as f:
    for i in f.readlines():
        data = list(map(int, i.strip().split('\t')))
        #邻接表
        V[data[0]] = np.array(data[1:])

def Contraction(Vertex):
    while len(Vertex) > 2:
        #选择节点
        u = np.random.choice(list(Vertex.keys()))
        v = np.random.choice(Vertex[u])
        #更新u, v
        adj_v = Vertex[v]
        #合并相邻节点
        adj_u = np.append(Vertex[u], Vertex[v])
        adj_u = adj_u[(adj_u != v) & (adj_u != u)]
        Vertex[u] = adj_u
        #删除v
        Vertex.pop(v)
        #更新其余元素
        for i in adj_v:
            if i != u:
                vec = Vertex[i]
                #替换
                vec[vec == v] = u
                Vertex[i] = vec
    
    n = []
    for i in Vertex:
        n.append(len(Vertex[i]))
    return np.min(n)

n = len(V)
N = int(n ** 2 * np.log(n))
N = 100
Res = []
for i in range(N):
    #深复制
    Vertex = copy.deepcopy(V)
    #计算结果
    num = Contraction(Vertex)
    Res.append(num)
    
print(np.min(Res))
17

思考题

思考题1

Prove that the worst-case expected running time of every randomized comparison-based sorting algorithm is $\Omega(n \log n)$. (Here the worst-case is over inputs, and the expectation is over the random coin flips made by the algorithm.)

参考资料：https://www.cs.cmu.edu/~avrim/451f11/lectures/lect0913.pdf

这题我主要不是很理解随机排序算法是如何定义的，参考资料中写到可以把随机排序算法看成确定排序算法的一个概率分布。设任意随机排序算法为$A$，确定排序算法族记为$\lbrace A_k\rbrace $，所以随机排序算法的比较次数$N$为

所以

注意确定性排序算法的比较次数大于等于$ \log_2 n!$，因此

因此结论成立。

思考题2

Suppose we modify the deterministic linear-time selection algorithm by grouping the elements into groups of 7, rather than groups of 5. (Use the “median-of-medians” as the pivot, as before.) Does the algorithm still run in $O(n)$ time? What if we use groups of 3?

回顾算法

将5改为7或3后，步骤1,2,4,5时间都没变，步骤3变为$T(\frac{n}{7})$或$T(\frac{n}{3})$，接着看步骤6,7

其中

  • $k =$组数
  • 令$x_i=k$个“middle elements”中第$i$小的元素，所以pivot$= x_{\frac k 2}$

如果改为$7$，那么$k =\frac {n}{7}$，从而大于$x_{\frac k 2}$的元素数量至少为

小于$x_{\frac k 2}$的元素数量至少为

所以$x_{\frac k 2}$一直位于$\frac 2 {7}n$到$\frac 5{7}n$的位置，所以步骤6,7的运行时间小于等于$T(\frac 5{7}n)$，从而有如下递推式

下面证明$T(n) \le 7cn$。

$n=1$时显然成立，假设$n< k$时，$T(n) \le 7cn$，那么$n=k$时

所以$n=k$时结论也成立，从而$T(n) \le 7cn$。

如果改为3，那么$k =\frac {n}{3}$，从而大于$x_{\frac k 2}$的元素数量至少为

小于$x_{\frac k 2}$的元素数量至少为

所以$x_{\frac k 2}$一直位于$\frac 1 {3}n$到$\frac 2{3}n$的位置，所以步骤6,7的运行时间小于等于$T(\frac 2{3}n)$，从而有如下递推式

对这个式子再递推一轮可得

归纳法可得（利用二项式定理）

当$\frac{2^k}{3^k} n <1$，即$ k\ge \log_{\frac 2 3} n$时，后一项全为0，所以

从而$T(n) =O(n\log n)$，所以这时候第6,7步的运行时间不再为$O(n)$，所以无法保证deterministic linear-time selection算法的时间复杂度仍然为$O(n)$

思考题3

Given an array of $n$ distinct (but unsorted) elements $x_1,x_2,\ldots,x_n$ with positive weights $w_1,w_2,\ldots,w_n$ such that $\sum_{i=1}^n w_i = W$, a weighted median is an element $x_k$ for which the total weight of all elements with value less than $x_k$(i.e., $\sum_{x_i \lt x_k} w_i$) is at most $W/2$, and also the total weight of elements with value larger than $x_k$ (i.e., $\sum_{x_i \gt x_k} w_i$) is at most $W/2$. Observe that there are at most two weighted medians. Show how to compute all weighted medians in $O(n)$ worst-case time.

利用partion的思路，首先找到$x_1,x_2,\ldots,x_n$的中位数$x_{i}$，将数组分为小于$x_i$以及大于$x_i$的两部分，分别求和，记为$S_1,S_2$，接着分为两种情形：

  • $S_1\le W/2$且$S_2 \le W/2$
    • 返回$x_i$
  • $S_1> W/2$
    • 在小于$x_i$的数组中递归使用该算法。
  • $S_2> W/2$
    • 在大于$x_i$的数组中递归使用该算法。

注意这个算法递归调用部分是对当前部分求中位数，求和部分依旧是对全数组。

由第四周的内容可知，找到中位数以及partion的时间都为$O(n)$，所以算法时间复杂度为：

此时

思考题4

We showed in an optional video lecture that every undirected graph has only polynomially (in the number $n$ of vertices) different minimum cuts. Is this also true for directed graphs? Prove it or give a counterexample.

我认为和无向图情形没有变化，因为之前的证明中主要是利用了如下事实（证明参考另一篇博客）

利用这个可以推出different minimum cuts的数量$\le \frac{n(n-1)}{2}$

思考题5

For a parameter $\alpha \ge 1$, an $\alpha$-minimum cut is one for which the number of crossing edges is at most $\alpha$ times that of a minimum cut. How many $\alpha$-minimum cuts can an undirected graph have, as a function of $\alpha$ and the number $n$ of vertices? Prove the best upper bound that you can.

这里假设$\alpha $为整数，下述记号同课件内容，对老师介绍的方法稍作修改：一共迭代$n-2\alpha $次。现在计算

记minimum cut的crossing edge的数量为$k_0$，$\alpha$-minimum cut的crossing edge的数量为$k$，那么

定义度(degree)为每个节点连接的边的数量，显然我们有如下等式：

所以

同理可得

从而

注意

由于$2\alpha-i \ge 1$，所以上式成立，从而

由课件中最后一点可知，假设有$t$个$\alpha$-minimum cut，那么