斯坦福算法专项课程Course1 Final Exam
这里回顾下第一门课的期末考试。
课程地址:https://www.coursera.org/specializations/algorithms
选择题 1
回想一下我们在QuickSort和RSelect中使用的Partition子例程。假设以下数组刚刚围绕某个pivot元素分区:3,1,2,4,5,8,7,6,9
哪些元素可能是pivot元素?(提示:检查所有适用的,可能有多种可能!)
- 3
- 5
- 4
- 2
- 9
pivot左边的元素要小于pivot,右边的元素要大于pivot,所以4,5,9均满足条件
选择题 2
这是一个十个整数的数组:5 3 8 9 1 7 0 2 6 4
假设我们在这个数组上运行MergeSort。在最外面的两个递归调用完成之后(即,在最后一个Merge步骤之前),部分排序数组的第7个位置的数字是多少?(当我们说“第7”位置时,我们是计算从1开始的位置;例如,输入数组在其第7位有一个“0”。)
- 1
- 3
- 4
- 2
最后一轮递归之前,数组的次序应该为1,3,5,8,9,0,2,4,6,7,所以第7个位置的元素为2
选择题 3
MergeSort的渐近最坏情况运行时间是什么,作为输入数组长度的函数$n$?
- $\theta(n^2)$
- $\theta(\log n)$
- $\theta(n)$
- $\theta(n\log n)$
显然答案为$\theta(n\log n)$
选择题 4
在长度为$n$的数组上数组使用Randomized QuickSort的期望运行时间以及最坏运行时间是多少?
- $\Theta(n)$(期望)和$\Theta(n\log n )$(最坏情形)
- $\Theta(n^2)$(期望)和$\Theta(n^2 )$(最坏情形)
- $\Theta(n\log n)$(期望)和$\Theta(n\log n )$(最坏情形)
- $\Theta(n\log n)$(期望)和$\Theta(n^2)$(最坏情形)
由第三周的内容可知,答案为第四项
选择题 5
两个非递减的正函数$f,g$满足$f= O(g(n))$,是否满足$2^{f(n)} = O(2^{g(n)})$
- 正确,如果$f(n) \le g(n)$对于所有足够大的$n$
- 有时正确
- 从不正确
- 总是正确
第一周选择题5,答案为第一项和第二项
选择题 6
令 $0<α<0.5 $是一个常数(与输入数组长度$n$无关)。回想一下QuickSort算法采用的Partition子程序,如讲座中所述。通过随机选择的pivot,Partition分割的两个子列中较小者的长度 $≥α$ 倍于原始数组的长度的概率?
- $ 1 - 2\alpha$
- $ \alpha$
- $1-\alpha$
- $2-2\alpha$
第三周选择题1,答案为第一项
选择题 7
假设随机算法成功(例如,正确地计算图的最小切割)的概率为$p$($ 0<p<1$)。令$\epsilon$是一个小的正数(小于1)。
需要运行算法多少次才能确保有大于等于 $1-\epsilon$的概率使得至少有一次试验成功?
- $\frac{\log (p)}{\log \epsilon}$
- $\frac{\log \epsilon }{\log (p)}$
- $\frac{\log (1-p)}{\log \epsilon}$
- $\frac{\log \epsilon }{\log (1-p)}$
运行算法$N$次,至少有一次算法成功的概率为$1-(1-p)^N$,令$1-(1-p)^N\ge 1- \epsilon$可得:
选择题 8
假设你得到了$k$个排好序的数组,每个都有个$n$元素,并且您希望将它们组合成有$kn$个元素的数组。考虑以下方法。把$k$个数组分成$k/2$对,并使用MergeSort讲座中讲授的Merge子例程来组合每一对。现在你有$k/2$个排好序的数组,每个都有$2n$个元素。重复此方法,合并为$kn$个元素的排好序的数组。这个程序的运行时间是多少?
- $\theta(nk\log n) $
- $\theta(n\log k) $
- $\theta(nk^2) $
- $\theta(nk\log k) $
第$i$轮要做$\frac k {2^{i}}$次merge,每次merge的数组长度为$2^{i-1} n$,所以每一轮需要的时间复杂度为
一共需要运行$\log_2 k$轮,所以总时间为
时间复杂度为
选择题 9
Strassen矩阵乘法算法的运行时间:假设算法的运行时间满足$ T(n)=7*T(n/2)+n^2$。$T(n)$为多少?
- $\theta(n^2)$
- $\theta(n^{\frac{\log 2}{\log 7}}) $
- $\theta(n^2\log n)$
- $\theta(n^{\log_2(7)})$
$a=7,b=2,d=2,a>b^d$,由主定理可得第四个选项正确。
选择题 10
回想一下Master Method及其三个参数$a,b,d$。以下哪项是对$b^d$最好的解释?
- 总工作量增长的速度(每个递归级别)。
- 子问题大小缩小的速率(每个递归级别)。
- 子问题数量增长的速率(每个递归级别)。
- 每个子工作问题的收缩率(每个递归级别)。
画出递归树,可以知道$b^d$是每个子问题额外需要的时间的收缩率,所以第四项正确。