CS170 Efficient Algorithms and Intractable Problems Section1

课程主页：

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

课程视频：

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

这次回顾Section 1。

1.Squaring vs multiplying: matrices

(a)

$\begin{aligned} A& = \left[ \begin{matrix} a & b\\ c & d \end{matrix} \right]\\ A^2 &=\left[ \begin{matrix} a & b\\ c & d \end{matrix} \right]\left[ \begin{matrix} a & b\\ c & d \end{matrix} \right]\\ &= \left[ \begin{matrix} a^2 + bc & ab + bd\\ ca+dc & cb + d^2 \end{matrix} \right]\\ &=\left[ \begin{matrix} a^2 + bc & b(a+d)\\ c(a+d) & bc + d^2 \end{matrix} \right] \end{aligned}$

所以计算如下$5$个量即可

$\begin{aligned} a^2, d^2,bc, b(a+d), c(a+d) \end{aligned}$

(b)

不正确，因为对于矩阵$a,b,c,d$，

$\begin{aligned} ab+bd &\neq b(a+d)\\ ca+dc & \neq c(a+d)\\ bc&\neq cb \end{aligned}$

所以一般情形无法分解为$5$个子问题。

(c)

此解法参考了官方解答：

对于矩阵$X,Y\in \mathbb R^{n\times n}$，构造矩阵

$A= \left[ \begin{matrix} 0 & X\\ Y & 0 \end{matrix} \right] \in \mathbb R^{2n\times 2n}$

那么

$\begin{aligned} A^2&= \left[ \begin{matrix} 0 & X\\ Y & 0 \end{matrix} \right]\left[ \begin{matrix} 0 & X\\ Y & 0 \end{matrix} \right]\\ &=\left[ \begin{matrix} XY & 0\\ 0 & YX \end{matrix} \right] \end{aligned}$

所以可以在$\Theta ((2n)^c)= \Theta(n^c)$时间内计算$XY$。

2.Find the missing integer

首先讨论$N=2^{k}-1$的情形，注意到$[0, 2^{k} - 1]$中所有数每位的$0,1$数量和相等，所以可以按照如下方法计算，其中第$i$位是指从右往左数的序号，从$0$开始：

记当前集合为$A$
记比特数组为$b[k]$
for $i = 0,…,k - 1$
- $A_0$表示$A$中第$i$位为$0$的数构成的集合，$A_1$表示$A$中第$i$位为1的数构成的集合
- 如果$|A_0| <|A_1|$，那么$A=A_0,b[i]= 0$
- 否则$A=A_1,b[i] =1$

解释：

以最低位为例，如果$|A_0| <|A_1|$，说明缺少了第$i$位为$0$的数；反之说明缺少了第$i$位为$1$的数。

时间复杂度：每次将规模减少一半，每次要遍历全部数字的某一位，所以：

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

如果$N\neq 2^{k} -1$，不妨假设$2^{k-1}\le N < 2^{k}-1$，那么补充$N+1,\ldots , 2^{k}- 1$，记$N_1= 2^{k}-1$，然后调用之前的算法即可，注意$N< N_1< 2N$，所以时间复杂度为

$\Theta (N_1)= \Theta (N)$

3.Complex numbers review

(a)

(i)

$\begin{aligned} -\sqrt 3 + i=2 \left(\cos \frac{5\pi}{6} + i\sin \frac{5\pi}{6}\right) \end{aligned}$

(ii)

$\cos \frac{2k\pi}{3} +i \sin \frac{2k\pi}{3}, k=0,1,2$

(iii)

利用韦达定理可得和为

$0$

(b)

$\begin{aligned} \sqrt{-1}&=\pm i\\ \text{sqrt}({i})& =\pm\frac{1+ i}{\sqrt 2}\\ \text{sqrt}({-i})& =\pm\frac{1- i}{\sqrt 2} \end{aligned}$