CS170 Efficient Algorithms and Intractable Problems Hw2

课程主页：

https://cs170.org/

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

课程视频：

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

这次回顾Hw2。

2.Counting inversions

• 算法：Counting inversions
• 输入：数组$A$，起点$\text{start}$，终点$\text{end}$
• 输出：逆序数

算法流程：

• 如果$\text{end}- \text{start}\le 0$，返回$0$
• $l=\text{Counting inversions}(A, \text{start}, [n/2] -1)$
• $r=\text{Counting inversions}(A, [n/2],\text{end})$
• $B=[],i=0,j=0, c = 0$
  • while $(i \le [n/2] -1- \text{start})$ and $(j \le \text{end}- [n/2])$:
    • if $A[\text{start}+i] < A[[n/2] + j]$:
      • $B.\text{append}(A[\text{start}+i])$
      • $i=i+1$
    • else:
      • $B.\text{append}(A[[n/2] + j])$
      • $c=c+[n/2] -1 - i+1$
      • $j=j+1$
  • while $(i \le [n/2] -1- \text{start})$:
    • $B.\text{append}(A[\text{start}+i])$
    • $i=i+1$
  • while $(j \le \text{end}- [n/2])$:
    • $B.\text{append}(A[[n/2] + j])$
    • $j=j+1$
• $A[l,\ldots, r] =B$
• return $l+r+c$

递归关系：

$$\begin{aligned} T(n)&= 2T\left(\frac n 2 \right) + \Theta(n)\\ T(n)&\in \Theta(n\log n) \end{aligned}$$

3.Two sorted arrays

• 算法：findIthOfTwoSortedArr
• 输入：两个单调递增数组$A,B$，数组范围$l_A,r_A,l_B,r_B$，次序统计量$i(1\le i \le r_A -l_A+1+r_B-l_B+1)$
• 输出：$A,B$中全体元素中第$i$大的值

算法流程：

• if $r_B<l_B $:
  • return $A[l_A + i - 1]$
• if $r_A < l_A$:
  • return $B[l_B + i-1]$
• $j= i /2$
• if $A[l_A + j -1] < B[l_B + j -1]$
  • return $\text{findIthOfTwoSortedArr}(A,B, l_A+j, r_A, l_B, r_B, i-j)$
• else:
  • return $\text{findIthOfTwoSortedArr}(A,B, l_A, r_A, l_B +j , r_B, i-j)$

我们的目标是求中位数，假设

• $n=\text{len}(A)$
• $m=\text{len}(B)$

那么返回

$$\text{findIthOfTwoSortedArr}(A,B, 0, n -1,0 , m - 1, [(n+m) /2])$$

正确性：

$A[l_A + j -1] < B[l_B + j -1]$，那么$A[l_A],\ldots, A[l_A + j -1]$必然不是第$i$大的元素，所以可以忽略，反之同理。

时间复杂度：

每次减少一半的搜索元素，所以时间复杂度为

$$\log (n+m)$$

实践练习：

4. 寻找两个正序数组的中位数

4.Majority Elements

(a)

• 算法：Majority Elements
• 输入：数组$A$，起点$\text{start}$，终点$\text{end}$
• 输出：主元素

算法流程：

• 如果$\text{end}- \text{start}\le 0$，返回$A[\text{start}]$
• $l=\text{Majority Elements}(A, \text{start}, [n/2] -1)$
• $r=\text{Majority Elements}(A, [n/2],\text{end})$
• if $l==r$:
  • return $l$
• else:
  • $c_1=0,c_2=0$
  • for $i=\text{start},\ldots,\text{end}$:
    • if $A[i]=l$:
      • $c_1=c_1+1$
    • else:
      • $c_2=c_2+1$
  • if $c_1\ge c_2$:
    • return $l$
  • else:
    • return $r$

正确性说明：

如果$d$是$A$的Majority Elements，那么$d$是$A[1,\ldots,[n/2] -1]$或$A[[n/2],\ldots,n]$的Majority Elements，这是因为如果上述结论不成立，那么$d$出现的次数$\le ([n/2]-1)/ 2+ (n-[n/2]+1)/2=n/2 $，这就与Majority Elements的定义矛盾。

在上述算法中，分别对$A$左右两段递归调用该算法，如果返回值相同，则显然是Majority Element；否则统计$l,r$的数量，最后返回数量较多的元素。

时间复杂度：

$$\begin{aligned} T(n)&=2T\left(\frac n 2\right) +\Theta(n)\\ T(n)&\in \Theta(n\log n) \end{aligned}$$

(b)

摩尔投票法：

• 算法：Majority Elements
• 输入：数组$A$，数组长度$n$
• 输出：主元素

算法流程：

• $a=A[1]$
• $c=1$
• for $i=2,\ldots, n$
  • if $A[i]!= a$:
    • $c=c-1$
    • if $c=0$:
      • $c=1$
      • $a=A[i]$
  • else:
    • $c=c+1$
• return $a,c$

命题：

$f(n)$：对于长度为$n$，存在majority element的数组$A[1,\ldots, n]$，记$l=\text{number of majority element}$，那么上述算法的输出$c\ge l-(n-l)=2l-n > 0$且$a$为majority element。

证明：

$n=1$时结论显然成立。

假设$n=m-1$时结论成立，现在证明$n=m$时结论成立。

首先记majority element为$d$，且出现次数为$l$。

如果$m=2k$，那么$d$的出现次数大于$k$，所以在前$m-1=2k-1$个元素中出现次数大于$k-1$，即$d$也是$A[1,\ldots,2k-1]=A[1,\ldots,m-1]$的majority element。

如果$m=2k-1$，那么$d$的出现次数大于$k-1$，所以在前$m-1=2k-2$个元素中出现次数大于$k-2$。

• 如果$d$的出现次数大于$k-1$，那么$d$也是$A[1,\ldots,2k-2]=A[1,\ldots,m-1]$的majority element。
• 否则，$d$的出现次数为$k-1$。
  • 如果其余$k-1$个元素不全相同，那么每个元素出现的次数小于$k-1$，从而$d$依然是majority element。
  • 如果其余$k-1$个元素都相同，那么$A[m]=d$（majority element的定义），并且第$m$轮循环前，$c=1$，从而最后一轮循环必然返回$A[m]=d$，即此时结论已证（情形a）。

综上，除了情形a，$d$都是$A[1,\ldots,2k-2]=A[1,\ldots,m-1]$的majority element。

如果$A[m]=d$，那么由归纳假设可得在第$m$轮循环前，$c\ge 2(l-1)-(m-1), a=d$；在第$m$轮循环后，

$$\begin{aligned} c&\ge 2(l-1)-(m-1) + 1=2l-m\\ a&=d \end{aligned}$$

如果$A[m]\neq d$，那么由归纳假设可得在第$m$轮循环前，$c\ge 2l-(m-1), a=d$；在第$m$轮循环后，

$$\begin{aligned} c&\ge 2l-(m-1) -1=2l-m\\ a&=d \end{aligned}$$

所以$T(n)$对$n=m$亦成立，从而原结论成立。

时间复杂度：

显然为$\Theta(n)$。

5.Merged Median

记$k$个排序数组为$A_i,i=1,\ldots,k$，记$A=A_1,\ldots, A_k$（$A_i$拼接而成）。

• 算法：Merged Median
• 输入：数组$A$，数组长度$n$，参数$k,l$
• 输出：排序后的数组$A$

算法流程：

• $B=[A_1[[l/2]],\ldots, A_k[[l/2]]]$
• $p=\text{DSelect}(B,k, [k/2])$
• Partition $A$ around $p$，记$p$的索引为$j$，$p$之前元素构成的数组为$A^l$，$p$之后元素构成的数组为$A^r$
• 如果$j= [n/2]$，返回$p$
• 如果$j> [n/2]$，返回$\text{DSelect}(A^l, j -1, [n/2])$
• 如果$j<[n/2]$，返回$\text{DSelect}(A^r, n-j, [n/2]-j)$

其中DSelect定义见如下链接：

https://doraemonzzz.com/2018/10/01/%E6%96%AF%E5%9D%A6%E7%A6%8F%E7%AE%97%E6%B3%95%E4%B8%93%E9%A1%B9%E8%AF%BE%E7%A8%8BCourse1%20week4%E5%86%85%E5%AE%B9%E5%9B%9E%E9%A1%BE/

6.Fourier Transform Basics

$$\begin{aligned} w&=i\\ M_4(w)&= \left[ \begin{matrix} 1 & 1 & 1 & 1 \\ 1 & w & w^2 & w^3 \\ 1 & w^2 & w^4 & w^6 \\ 1 & w^3 & w^ 6 & w^9 \end{matrix} \right]\\ &= \left[ \begin{matrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end{matrix} \right]\\ M_4(w)^{-1}&= \frac 1 4 M_4(w^{-1})\\ &= \frac 1 4\left[ \begin{matrix} 1 & 1 & 1 & 1 \\ 1 & w & w^2 & w^3 \\ 1 & w^2 & w^4 & w^6 \\ 1 & w^3 & w^ 6 & w^9 \end{matrix} \right]_{w=-i}\\ &= \frac 1 4\left[ \begin{matrix} 1 & 1 & 1 & 1 \\ 1 & -i & -1 & i \\ 1 & -1 & 1 & -1 \\ 1 & i & -1 & -i \end{matrix} \right] \end{aligned}$$

(a)

$$\begin{aligned} x&=\left[ \begin{matrix} 3\\i\\2\\4 \end{matrix} \right]\\ M_4(w)x &= \left[ \begin{matrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end{matrix} \right]\left[ \begin{matrix} 3\\i\\2\\4 \end{matrix} \right]\\ &= \left[ \begin{matrix} 9+i\\-4i\\1-i\\2+4i \end{matrix} \right] \end{aligned}$$

(b)

$$\begin{aligned} x&= M_4(w)^{-1}\text{FT}(x)\\ &= \frac 1 4\left[ \begin{matrix} 1 & 1 & 1 & 1 \\ 1 & -i & -1 & i \\ 1 & -1 & 1 & -1 \\ 1 & i & -1 & -i \end{matrix} \right]\left[ \begin{matrix} 5\\2\\1\\-i \end{matrix} \right]\\ &= \frac 1 4\left[ \begin{matrix} 8-i\\5-2i\\4+i\\3+2i \end{matrix} \right]\\ y&= M_4(w)^{-1}\text{FT}(y)\\ &= \frac 1 4\left[ \begin{matrix} 1 & 1 & 1 & 1 \\ 1 & -i & -1 & i \\ 1 & -1 & 1 & -1 \\ 1 & i & -1 & -i \end{matrix} \right]\left[ \begin{matrix} 4\\4\\i\\i \end{matrix} \right]\\ &= \frac 1 4\left[ \begin{matrix} 8+2i\\3-5i\\0\\5+3i \end{matrix} \right] \end{aligned}$$

(c)

$$\begin{aligned} z&= M_4(w)^{-1}\left(\text{FT}(z) \right)\\ &=M_4(w)^{-1}\left(\text{FT}(x)- \text{FT}(y) \right)\\ &=x-y\\ &=\frac 1 4\left(\left[ \begin{matrix} 8-i\\5-2i\\4+i\\3+2i \end{matrix} \right]-\left[ \begin{matrix} 8+2i\\3-5i\\0\\5+3i \end{matrix} \right]\right)\\ &=\frac 1 4 \left[ \begin{matrix} -3i\\2+3i\\4+i\\-2-i \end{matrix} \right] \end{aligned}$$

(d)

$$\begin{aligned} x &=\left[ \begin{matrix} 1\\ 0 \\ 2 \\ 0 \end{matrix} \right]\\ \text{FT}(x) &=M_4(w)x\\ &= \left[ \begin{matrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end{matrix} \right]\left[ \begin{matrix} 1\\0\\2\\0 \end{matrix} \right]\\ &= \left[ \begin{matrix} 3\\-1\\3\\-1 \end{matrix} \right]\\ y &=\left[ \begin{matrix} 4\\ 1\\ 0 \\ 0 \end{matrix} \right]\\ \text{FT}(y) &=M_4(w)y\\ &= \left[ \begin{matrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end{matrix} \right]\left[ \begin{matrix} 4\\1\\0\\0 \end{matrix} \right]\\ &= \left[ \begin{matrix} 5\\4+i\\3\\4-i \end{matrix} \right] \end{aligned}$$

那么

$$\begin{aligned} \text{FT}(x) \otimes \text{FT}(y) &=\left[ \begin{matrix} 15\\-4-i\\9\\-4+i \end{matrix} \right]\\ M_4(w)^{-1}\left( \text{FT}(x) \otimes \text{FT}(y)\right) &= \frac 1 4\left[ \begin{matrix} 1 & 1 & 1 & 1 \\ 1 & -i & -1 & i \\ 1 & -1 & 1 & -1 \\ 1 & i & -1 & -i \end{matrix} \right] \left[ \begin{matrix} 15\\-4-i\\9\\-4+i \end{matrix} \right]\\ &= \left[ \begin{matrix} 4\\1\\8\\2 \end{matrix} \right] \end{aligned}$$

对应的多项式为

$$2x^3 + 8x^2 + x+4$$

7.Modular Fourier Transform

参考资料：

https://www.cs.drexel.edu/~jjohnson/2010-11/fall/cs567/lectures/threeprimes.pdf

(a)

取

$$w=2$$

那么

$$\begin{aligned} w&\equiv 2 \mod 5\\ w^2&\equiv 4 \mod 5\\ w^3&\equiv 8\\ &\equiv 3 \mod 5\\ w^4&\equiv 3\times 2\\ &\equiv 1\mod 5\\ \end{aligned}$$

(b)

$$\begin{aligned} x&=\left[ \begin{matrix} 0\\1\\0\\2 \end{matrix} \right]\\ M_4(w)x &= \left[ \begin{matrix} 1 & 1& 1 & 1 \\ 1 & w& w^2 & w^3 \\ 1 & w^2 & w^4 & w^6 \\ 1 & w^3 & w^6 & w^{9} \end{matrix} \right]\\ &= \left[ \begin{matrix} 1 & 1 & 1 & 1 \\ 1 & 2 & 4 &3 \\ 1 & 4 & 1 &4 \\ 1 & 3& 4 & 2 \end{matrix} \right]\left[ \begin{matrix} 0\\1\\0\\2 \end{matrix} \right]\\ &= \left[ \begin{matrix} 3\\3\\2\\2 \end{matrix} \right] \end{aligned}$$

(c)

注意到

$$\begin{aligned} w.w^3 &\equiv 1 \mod 5\\ w^{-1} & =w^3=3 \mod 5 \\ 4^{-1} &= 4\mod 5 \end{aligned}$$

所以类比FFT可得

$$\begin{aligned} M_4(w)^{-1}&= 4\times M_4(w^{-1})\\ &= 4^{-1}\left[ \begin{matrix} 1 & 1& 1 & 1 \\ 1 & w^3& w^6 & w^9 \\ 1 & w^6 & w^{12} & w^{18} \\ 1 & w^9 & w^{18} & w^{27} \end{matrix} \right]\\ &= 4\left[ \begin{matrix} 1 & 1& 1 & 1 \\ 1 & 3& 4 & 2 \\ 1 & 4 &1 & 4\\ 1 &2 & 4 &3 \end{matrix} \right]\\ x&= M_4(w)^{-1}\text{FT}(x)\\ &= 4\left[ \begin{matrix} 1 & 1& 1 & 1 \\ 1 & 3& 4 & 2 \\ 1 & 4 &1 & 4\\ 1 &2 & 4 &3 \end{matrix} \right] \left[ \begin{matrix} 3\\3\\2\\2 \end{matrix} \right]\\ &= 4\left[ \begin{matrix} 10\\24\\25\\23 \end{matrix} \right]\\ &\equiv \left[ \begin{matrix} 40\\96\\100\\92 \end{matrix} \right] \mod 5\\ &\equiv \left[ \begin{matrix} 0\\1\\0\\2 \end{matrix} \right] \mod 5 \end{aligned}$$

(d)

$$\begin{aligned} x &=\left[ \begin{matrix} 3\\ 0 \\ 2 \\0 \end{matrix} \right]\\ \text{FT}(x) &=M_4(w)x\\ &= \left[ \begin{matrix} 1 & 1 & 1 & 1 \\ 1 & 2 & 4 &3 \\ 1 & 4 & 1 &4 \\ 1 & 3& 4 & 2 \end{matrix} \right]\left[ \begin{matrix} 3\\ 0 \\ 2 \\0 \end{matrix} \right]\\ &= \left[ \begin{matrix} 0\\1\\0\\1 \end{matrix} \right]\\ y &=\left[ \begin{matrix} 3\\ -1\\ 0 \\ 0 \end{matrix} \right]\\ \text{FT}(y) &=M_4(w)y\\ &= \left[ \begin{matrix} 1 & 1 & 1 & 1 \\ 1 & 2 & 4 &3 \\ 1 & 4 & 1 &4 \\ 1 & 3& 4 & 2 \end{matrix} \right]\left[ \begin{matrix} 3\\ -1\\ 0 \\ 0 \end{matrix} \right]\\ &= \left[ \begin{matrix} 2\\1\\4\\0 \end{matrix} \right] \end{aligned}$$

那么

$$\begin{aligned} \text{FT}(x) \otimes \text{FT}(y) &=\left[ \begin{matrix} 0\\1\\0\\0 \end{matrix} \right]\\ M_4(w)^{-1}\left( \text{FT}(x) \otimes \text{FT}(y)\right) &= 4\left[ \begin{matrix} 1 & 1& 1 & 1 \\ 1 & 3& 4 & 2 \\ 1 & 4 &1 & 4\\ 1 &2 & 4 &3 \end{matrix} \right]\left[ \begin{matrix} 0\\1\\0\\0 \end{matrix} \right]\\ &= 4\left[ \begin{matrix} 1\\3\\4\\2 \end{matrix} \right]\\ &= \left[ \begin{matrix} 4\\12\\16\\8 \end{matrix} \right]\\ &= \left[ \begin{matrix} 4\\2\\1\\3 \end{matrix} \right] \mod 5 \end{aligned}$$

对应的多项式为

$$3x^3 + x^2 + 2x+4$$

实际结果应该为

$$\begin{aligned} (2 x^{2}+3)(-x+3) &= -2x^3 +6x^2 -3x + 9\\ &\equiv 3x^3 + x^2 + 2x + 4 \mod 5 \end{aligned}$$

8.Polynomial from roots

• 算法：Polynomial from roots
• 输入：次数$n$，零点$r_1,\ldots,r_n$
• 输出：多项式的系数

算法流程：

• 如果$n=1$，返回$[-r_1]$
• $l=\text{Polynomial from roots}([n/2],[r_1,\ldots,r_{[n/2]}])$
• $r=\text{Polynomial from roots}(n-[n/2],[r_{[n/2]+1},\ldots,r_{n}])$
• $\text{res}= \text{FFT}_n^{-1}(\text{FFT}_n(l)\text{FFT}_n(r))$
• return res

正确性显然，时间复杂度的递推如下：

$$T(n)=2T\left( \frac n 2\right) +\Theta(n\log n)$$

利用递归树方法计算$T(n)$，在第$i$层的时间复杂度为

$$\Theta\left(2^i \times \frac n {2^i} \log \frac n {2^i} \right) =\Theta\left( n \log n - ni \right)$$

总时间复杂度为

$$\begin{aligned} \Theta\left(\sum_{i=1}^{\log n} n \log n - ni \right) &=\Theta\left( n \log^2 n - n\frac{(1+\log n)\log n}{2} \right)\\ &=\Theta(n \log^2 n) \end{aligned}$$