斯坦福算法专项课程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$是每个子问题额外需要的时间的收缩率,所以第四项正确。