CS170 Efficient Algorithms and Intractable Problems Hw1

课程主页:

https://cs170.org/

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

课程视频:

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

这次回顾Hw 1。

2.Analyze the running time

(a)
(b)

总时间复杂度为

(c)

第$k$轮的$i$为

所以

(d)

3.Asymptotic Complexity Comparisons

(a)

那么排序为

(b)

(i)

因为

(ii)

(iii)

(iv)

(v)

所以

(vi)

(vii)

所以

4.Bit Counter

考虑flip过程

1
2
3
4
5
6
7
8
9
00...00
00...01
...
01...11
10...00
10...01
...
11...11
00...00

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

从而

5.Recurrence Relations

回顾主定理:

如果

那么

(a)

所以

(b)

所以

(c)

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

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

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

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

这里使用了结论

(d)

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

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

6.Computing Factorials

(a)

注意到

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

所以

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

所以

(b)

伪代码:

1
2
3
4
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)$,所以总时间复杂度为

注意到

因此

7.Four-subpart Algorithm Practice

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

Main idea:

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

Psuedocode:

1
2
3
4
5
6
7
8
9
10
11
12
13
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:

8.Hadamard matrices

(a)
(b)
(c)
(d)
(e)

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

//