#### 选择题

##### 选择题 1

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

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

##### 选择题 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)$

##### 选择题 3

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

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

##### 选择题 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}$

##### 选择题 5

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

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

#### 思考题

##### 思考题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.)

##### 思考题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?

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

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

##### 思考题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.

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

##### 思考题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.

##### 思考题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.