CS170 Efficient Algorithms and Intractable Problems Hw1

课程主页：

https://cs170.org/

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

课程视频：

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

这次回顾Hw1。

2.Analyze the running time

(a)

$$T(n) \in \Theta(n^2)$$

(b)

总时间复杂度为

$$\begin{aligned} T(n) &= \sum_{i=0}^{ \log n} 2^i\\ &=2^{\log n + 1} - 1\\ &=2n - 1 \\ &\in \Theta(n) \end{aligned}$$

(c)

第$k$轮的$i$为

$$i = 2^{2^{k}}$$

令

$$2^{2^{k}} = n$$

得

$$k = \log \log n$$

所以

$$T(n) \in \Theta(\log \log n)$$

(d)

$$\begin{aligned} T(n) & =\sum_{i=1}^n \sum_{j=i^2} ^ n 1\\ &= \sum_{i=1}^{[\sqrt n]} \sum_{j=i^2} ^n 1\\ &= \sum_{i=1}^{[\sqrt n]} (n - i^2 + 1)\\ &= n [\sqrt n] - \frac{[\sqrt n]([\sqrt n]+1) ( 2[\sqrt n] + 1)}{6} +[\sqrt n]\\ &\in \Theta ((\sqrt n)^3) \end{aligned}$$

3.Asymptotic Complexity Comparisons

(a)

记

$$f_i \le f_j \Leftrightarrow f_i = O(f_j)$$

那么排序为

$$f_3 \le f_7\le f_2 \le f_5 \le f_4 \le f_9 \le f_8 \le f_6\le f_1$$

(b)

(i)

$$f(n) =\Theta(g (n))$$

因为

$$\frac{f(n)} {g(n)}= \frac{\log_3 n}{\log_4 n}= \log_3 4$$

(ii)

$$\begin{aligned} f(n) & = 4n \log n\\ g(n)&= 3n^2 \log n\\ f &= O(g) \end{aligned}$$

(iii)

$$f= \Omega(g)$$

(iv)

$$f=\Theta( g)$$

(v)

$$\begin{aligned} f(n) & = 2^\left( \log n \right)\\ g(n) & = 2^\left( (\log \log n)^2 \right) \end{aligned}$$

所以

$$f= \Omega (g)$$

(vi)

$$f=\Theta(g)$$

(vii)

$$\begin{aligned} f(n) & = \log (n !)\\ &=\sum_{i=1}^ n \log i\\ &\le n \log n \\ &\ge n \log \frac {n+1}{2} (由凸性) \end{aligned}$$

所以

$$f=\Theta(g)$$

4.Bit Counter

考虑flip过程

00...00
00...01
...
01...11
10...00
10...01
...
11...11
00...00

$n$位的flip可以看成2轮$n-1$位的flip，加上两次对第$n$位的flip，所以

$$\begin{aligned} T(n) &= T(n-1) + 1+T(n-1)+1\\ T(n)&=2T(n- 1) +2\\ T(n)+ 2 &= 2(T(n- 1)+2)\\ &= 2^{n-1}(T(1) +2)\\ T(n) &= 2^{n+1} - 2 \end{aligned}$$

从而

$$T(n)=\Theta(2^n)$$

5.Recurrence Relations

回顾主定理：

如果

$$T(n) = aT\left(\frac n b \right) +\Theta(n^d)$$

那么

$$T(n)=\begin{cases} \Theta(n^d), &a<b^d\\ \Theta(n^d\log n), &a=b^d\\ \Theta(n^{\log_b a }), & a>b^d \end{cases}$$

(a)

$$\begin{aligned} a& =4\\ b&= 2\\ d&= 1\\ 2=\log_b a & > d =1 \end{aligned}$$

所以

$$T(n) \in \Theta (n^2)$$

(b)

$$\begin{aligned} a& =4\\ b&= 3\\ d&= 2\\ \log_3 4=\log_b a & < d =2 \end{aligned}$$

所以

$$T(n) \in \Theta (n^2)$$

(c)

利用递归树分析，在第$i$层中，有$3^i$个节点，将如下形式的项合并后共有$i +1$项：

$$T\left( \frac {2^j} {3^ i} n\right)$$

该项的系数为$2^j$，每一项的时间复杂度为

$$\frac {4^j} {9^ i} n^2$$

所以第$i$层的时间复杂度为

$$\begin{aligned} \sum_{j =0 }^i \frac {8^j} {9^ i} n^2 &=\frac{n^2}{9^ i} \times \frac{8^{i+1} - 1}{7}\\ &= \frac 8 7 \left(\frac 8 9\right)^i n^2 -\frac 1 7 \left(\frac 1 9\right)^i n^2 \end{aligned}$$

注意递归树的层数是$\Theta(\log n)$数量级的，所以总时间复杂度为

$$\begin{aligned} T(n) &=\sum_{i=1}^{\log n}\left( \frac 8 7 \left(\frac 8 9\right)^i n^2 -\frac 1 7 \left(\frac 1 9\right)^i n^2 \right)\\ & \in \Theta(n^2) \end{aligned}$$

这里使用了结论

$$\sum_{i=0}^n c^i =\Theta(1), 0<c<1$$

(d)

利用递归树分析，在第$i$层中，有$3^i$个节点，每个节点的规模为$n / 4^i$，所以第$i$层的总时间复杂度为

$$3^i \frac{n}{4^i} \log \frac{n}{4^i} =\left(\frac 3 4 \right) ^i n\log n - \left(\frac 3 4 \right) ^i i \times \log 4\times n$$

注意层数为$\Theta(\log n)$层，所以总时间复杂度为

$$\begin{aligned} T(n) &= \sum_{i=1}^{\log n} \left(\frac 3 4 \right) ^i n\log n - \left(\frac 3 4 \right) ^i i \times \log 4\times n\\ &\in \Theta(n\log n) \end{aligned}$$

6.Computing Factorials

(a)

注意到

$$N!= (N-1)!\times N$$

记$N!$对应的比特长为$L(N)$，那么

$$L(N) = L(N- 1) +\Theta(\log N)$$

所以

$$\begin{aligned} L(N) &= L(1) +\sum_{i=1}^N \log i\\ &\le L(1) + N\log N\\ &\ge L(1) + N \log \frac {N+1}{2}\\ L(N)&\in \Theta (N\log N) \end{aligned}$$

注意$N$为$n$比特，即

$$L(N) \in \Theta (n\log N)$$

所以

$$L(N) \in \Theta(n N)$$

(b)

伪代码：

s = 1
for i = 1, 2, ..., N
	s = s * i
return i

注意$i$的比特数为$\Theta(\log i)$，以及在第$i$步中，$s$的长度为$\Theta(i\log i)$，从而乘法的时间复杂度为$\Theta(i \log^2 i)$，所以总时间复杂度为

$$T(n) = \Theta \left( \sum_{i=1}^N i\log^2 i\right)$$

注意到

$$\begin{aligned} \sum_{i=1}^N i\log^2 i &\le N\times N \log^2 N\\ &= N^2 \log^2 N\\ \sum_{i=1}^N i\log^2 i & \ge \sum_{i=N/ 2}^N i\log^2 i\\ & \ge \frac N 2 \times \frac N 2 \log^2 \frac{N}{2} \end{aligned}$$

因此

$$T(n) = \Theta \left( N^2\log^2 N\right)$$

7.Four-subpart Algorithm Practice

只考虑数组单调递增的情形（单调递减的情形类似）。

Main idea:

因为是有序的数组，所以采用二分法。

Psuedocode:

l = 0
r = n - 1
while (l < r):
	m = (l + r) / 2
	if A[m] < k:
        l = m + 1
     else:
        r = m

if (A[l] != k):
    return -1
else:
	return l

Proof of correctness:

如果A[m] < k，那么位置必然大于m；如果A[m] >= k，那么位置必然小于等于m。

Running time analysis:

$$T(n) =\Theta(\log n)$$

8.Hadamard matrices

(a)

$$\begin{aligned} H_0 &= \left[ \begin{matrix} 1 \end{matrix} \right]\\ H_1 &= \left[ \begin{matrix} 1 & 1\\ 1 & -1 \end{matrix} \right]\\ H_2 & = \left[ \begin{matrix} 1 & 1 & 1 & 1\\ 1 & -1 & 1 & -1\\ 1 & 1 & -1 & - 1\\ 1 & -1 & -1 & 1 \end{matrix} \right] \end{aligned}$$

(b)

$$\begin{aligned} H_2 v& = \left[ \begin{matrix} 1 & 1 & 1 & 1\\ 1 & -1 & 1 & -1\\ 1 & 1 & -1 & - 1\\ 1 & -1 & -1 & 1 \end{matrix} \right] \left[ \begin{matrix} 1\\ -1\\ - 1\\ 1 \end{matrix} \right]\\ &=\left[ \begin{matrix} 0\\ 0\\ 0\\ 4 \end{matrix} \right] \end{aligned}$$

(c)

$$\begin{aligned} u_{1}&=H_{1}\left(v_{1}+v_{2}\right)\\ &=\left[ \begin{matrix} 1 & 1\\ 1 & -1 \end{matrix} \right] \left[ \begin{matrix} 0 \\ 0 \end{matrix} \right]\\ &=\left[ \begin{matrix} 0 \\ 0 \end{matrix} \right]\\ u_2&=H_{1}\left(v_{1}-v_{2}\right)\\ &=\left[ \begin{matrix} 1 & 1\\ 1 & -1 \end{matrix} \right] \left[ \begin{matrix} 2 \\ -2 \end{matrix} \right]\\ &=\left[ \begin{matrix} 0 \\ 4 \end{matrix} \right]\\ u&= \left[ \begin{matrix} 0 \\ 0\\ 0\\ 4 \end{matrix} \right]\\ &= H_2 v \end{aligned}$$

(d)

$$\begin{aligned} H_k v &=\left[\begin{array}{c|c} H_{k-1} & H_{k-1} \\ \hline H_{k-1} & -H_{k-1} \end{array}\right] \left[\begin{array}{l} v_{1} \\ v_{2} \end{array}\right]\\ &= \left[ \begin{matrix} H_{k-1} (v_1 +v_2)\\ H_{k-1} (v_1 -v_2) \end{matrix} \right] \end{aligned}$$

(e)

利用(d)，不难得到递推算法，时间复杂度满足如下条件：

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