Exercise 1

设 $n$ 是 $2$ 的幂，$n = 2^m$。递归树的高度为 $\log_2 n$（根为第 $0$ 层，叶子为第 $\log_2 n$ 层）。

在第 $k$ 层有 $2^k$ 个子问题，每个子问题的大小为 $n / 2^k$。每个子问题对应的非递归代价为 $O\bigl( \frac{n}{2^k} \log \frac{n}{2^k} \bigr)$。因此，第 $k$ 层的总代价为

$$2^k \cdot O\Bigl( \frac{n}{2^k} \log \frac{n}{2^k} \Bigr) = O\Bigl( n \log \frac{n}{2^k} \Bigr) = O\bigl( n (\log n - k) \bigr).$$

将所有层的代价求和（忽略基例常数）：

$$T(n) = \sum_{k=0}^{\log_2 n - 1} O\bigl( n (\log n - k) \bigr) = O\Bigl( n \sum_{k=0}^{\log_2 n - 1} (\log n - k) \Bigr).$$

令 $m = \log_2 n$，则

$$\sum_{k=0}^{m-1} (m - k) = \sum_{j=1}^{m} j = \frac{m(m+1)}{2} = O(m^2) = O\bigl((\log n)^2\bigr).$$

因此

$$T(n) = O\bigl( n (\log n)^2 \bigr).$$

Exercise 2

(1)

$count \gets 0$
for $i \gets 1$ to $n-2$ do
for $j \gets i+1$ to $n-1$ do
for $k \gets j+1$ to $n$ do
if $\{i,j\} \in E$ and $\{j,k\} \in E$ and $\{k,i\} \in E$ then
$count \gets count + 1$
end if
end for
end for
end for
return $count$

(2)

Let $A$ be the $n \times n$ adjacency matrix of $G$:
$A_{ij} = 1$ if $\{i,j\} \in E$, else $A_{ij} = 0$ (and $A_{ii}=0$).
Compute $B = A \times A$ using Strassen's matrix multiplication algorithm.
Compute $C = B \times A$ using Strassen's matrix multiplication algorithm.
$trace \gets 0$
for $i \gets 1$ to $n$ do
$trace \gets trace + C_{ii}$
end for
return $trace / 6$

Exercise 3

$s \gets \lceil k/3 \rceil$
Partition $V$ into three nearly equal subsets $V_1, V_2, V_3$
for all $(a,b,c)\in \mathbb{N}^3$ with $a+b+c=k$, $a,b,c\le s$ do
$\mathcal{C}_a \gets$ all $a$-cliques in $V_1$ (if $a=0$, $\mathcal{C}_a=\{\emptyset\}$)
$\mathcal{C}_b \gets$ all $b$-cliques in $V_2$ (if $b=0$, $\mathcal{C}_b=\{\emptyset\}$)
$\mathcal{C}_c \gets$ all $c$-cliques in $V_3$ (if $c=0$, $\mathcal{C}_c=\{\emptyset\}$)
$n_a \gets |\mathcal{C}_a|$, $n_b \gets |\mathcal{C}_b|$, $n_c \gets |\mathcal{C}_c|$
Define $M_{ab}\in\{0,1\}^{n_a\times n_b}$:
$M_{ab}[i][j]=1$ iff $\forall u\in\mathcal{C}_a[i], v\in\mathcal{C}_b[j]: \{u,v\}\in E$
Define $M_{bc}\in\{0,1\}^{n_b\times n_c}$ analogously
Define $M_{ac}\in\{0,1\}^{n_a\times n_c}$ analogously
\State
$P \gets \text{StrassenMultiply}(M_{ab}, M_{bc})$
$Q \gets \text{StrassenMultiply}(P, M_{ac}^{\mathsf{T}})$
for $i\gets 1$ to $n_a$ do
if $Q[i][i] > 0$ then
return $1$
end if
end for
end for
return $0$

Exercise 4

(a)

$\omega = 3$

$$ 3^1=3,\; 3^2=2,\; 3^3=6,\; 3^4=4,\; 3^5=5,\; 3^6=1 \pmod{7}, $$

求和：

$$ \omega + \omega^2 + \omega^3 + \omega^4 + \omega^5 + \omega^6 = 3+2+6+4+5+1 = 21 \equiv 0 \pmod{7}. $$

(b)

$y_j = \sum_{k=0}^{5} x_k \omega^{jk} \pmod{7}$

$$ \begin{aligned} y_0 &= 0+1+1+1+5+2 = 10 \equiv 3,\\ y_1 &= 0\cdot1 +1\cdot3 +1\cdot2 +1\cdot6 +5\cdot4 +2\cdot5 = 3+2+6+20+10 = 41 \equiv 6,\\ y_2 &= 0\cdot1 +1\cdot2 +1\cdot4 +1\cdot1 +5\cdot2 +2\cdot4 = 2+4+1+10+8 = 25 \equiv 4,\\ y_3 &= 0\cdot1 +1\cdot6 +1\cdot1 +1\cdot6 +5\cdot1 +2\cdot6 = 6+1+6+5+12 = 30 \equiv 2,\\ y_4 &= 0\cdot1 +1\cdot4 +1\cdot2 +1\cdot1 +5\cdot4 +2\cdot2 = 4+2+1+20+4 = 31 \equiv 3,\\ y_5 &= 0\cdot1 +1\cdot5 +1\cdot4 +1\cdot6 +5\cdot2 +2\cdot3 = 5+4+6+10+6 = 31 \equiv 3. \end{aligned} $$

故变换结果为 $(3,6,4,2,3,3)$

(c)

逆傅里叶变换矩阵为 $\frac{1}{n} M_n(\omega^{-1})$，其中 $n=6$，模 $7$ 下 $6^{-1}=6$（因为 $6\times6=36\equiv1$），且 $\omega^{-1}=3^{-1}=5$。因此逆矩阵为

$$ M_6^{-1} = 6 \cdot M_6(5), $$

即 $(M_6^{-1})_{jk} = 6 \cdot 5^{jk} \pmod{7}$。
验证：对任意 $\mathbf{x}$，有

$$ x_k = \frac{1}{6}\sum_{j=0}^{5} y_j \omega^{-jk} \pmod{7}, $$

其中 $y_j = \sum_{k'} x_{k'} \omega^{jk'}$。代入得

$$ \frac{1}{6}\sum_j \sum_{k'} x_{k'} \omega^{j(k'-k)} = \frac{1}{6}\sum_{k'} x_{k'} \sum_{j=0}^{5} \omega^{j(k'-k)} = \frac{1}{6}\cdot 6 \cdot x_k = x_k, $$

因为 $\sum_{j=0}^{5} \omega^{jm} = 0$ 当 $m\not\equiv 0\pmod{6}$，且等于 $6$ 当 $m\equiv0$。模 $7$ 下 $6/6=1$。

(d)

将系数按低次到高次（长度 $n=6$）写为：

$$ \mathbf{p} = (1, 1, 1, 0, 0, 0), \qquad \mathbf{q} = (6, 2, 0, 1, 0, 0). $$

1. 计算 DFT：$\mathbf{P} = \text{DFT}(\mathbf{p})$，$\mathbf{Q} = \text{DFT}(\mathbf{q})$

DFT 公式：

$$ P_j = \sum_{k=0}^{5} p_k \cdot \omega^{j k} \pmod{7}, \quad j = 0,\dots,5, $$

其中 $\omega = 3$。
先计算 $\omega$ 的各次幂（模 7）：

$$ \omega^0=1,\; \omega^1=3,\; \omega^2=2,\; \omega^3=6,\; \omega^4=4,\; \omega^5=5,\; \omega^6=1. $$

计算 $P_j$：

故

$$ \mathbf{P} = (3,\; 6,\; 0,\; 1,\; 0,\; 3). $$

计算 $Q_j$：

故

$$ \mathbf{Q} = (2,\; 4,\; 4,\; 3,\; 1,\; 1). $$

2. 逐点相乘：$R_j = P_j \cdot Q_j \pmod{7}$

$$ \begin{aligned} R_0 &= 3 \times 2 = 6, \\ R_1 &= 6 \times 4 = 24 \equiv 3, \\ R_2 &= 0 \times 4 = 0, \\ R_3 &= 1 \times 3 = 3, \\ R_4 &= 0 \times 1 = 0, \\ R_5 &= 3 \times 1 = 3. \end{aligned} $$

所以

$$ \mathbf{R} = (6,\; 3,\; 0,\; 3,\; 0,\; 3). $$

3. 逆 DFT：$r_k = \frac{1}{6} \sum_{j=0}^{5} R_j \cdot \omega^{-j k} \pmod{7}$

模 7 下，$6^{-1} = 6$（因为 $6\times6=36\equiv1$），且 $\omega^{-1}=3^{-1}=5$。
逆变换公式：

$$ r_k = 6 \sum_{j=0}^{5} R_j \cdot (5)^{j k} \pmod{7}, \quad k=0,\dots,5. $$ $$ 5^0=1,\; 5^1=5,\; 5^2=4,\; 5^3=6,\; 5^4=2,\; 5^5=3,\; 5^6=1. $$

对每个 $k$，计算 $S_k = \sum_{j=0}^{5} R_j \cdot (5^k)^j$，然后 $r_k = 6 S_k \bmod 7$。

$j=0:6\times1=6$，$j=1:3\times5=15\equiv1$，$j=2:0$，$j=3:3\times5^3=3\times6=18\equiv4$，$j=4:0$，$j=5:3\times5^5=3\times3=9\equiv2$，
和 $6+1+4+2=13\equiv6$，$r_1=6\times6=36\equiv1$。

$j=0:6$，$j=1:3\times4=12\equiv5$，$j=2:0$，$j=3:3\times1=3$，$j=4:0$，$j=5:3\times2=6$，
和 $6+5+3+6=20\equiv6$，$r_2=6\times6=36\equiv1$。

$j=0:6$，$j=1:3\times6=18\equiv4$，$j=2:0$，$j=3:3\times6=18\equiv4$，$j=4:0$，$j=5:3\times6=18\equiv4$，
和 $6+4+4+4=18\equiv4$，$r_3=6\times4=24\equiv3$。

$j=0:6$，$j=1:3\times2=6$，$j=2:0$，$j=3:3\times1=3$，$j=4:0$，$j=5:3\times4=12\equiv5$，
和 $6+6+3+5=20\equiv6$，$r_4=6\times6=36\equiv1$。

$j=0:6$，$j=1:3\times3=9\equiv2$，$j=2:0$，$j=3:3\times6=18\equiv4$，$j=4:0$，$j=5:3\times5=15\equiv1$，
和 $6+2+4+1=13\equiv6$，$r_5=6\times6=36\equiv1$。

因此乘积系数（低次到高次）为：

$$ (r_0, r_1, r_2, r_3, r_4, r_5) = (6, 1, 1, 3, 1, 1). $$

即多项式

$$ R(x) = x^5 + x^4 + 3x^3 + x^2 + x + 6 \equiv x^5 + x^4 + 3x^3 + x^2 + x - 1 \pmod{7}, $$

与直接卷积结果一致。

Exercise 5

建模为决策树。每个内部节点对应一次形如“$A[i] \leq z$?”的比较。比较的结果为“是”或“否”，分别导向左右子树。每个叶子节点对应算法输出一个结果，即 $x$ 在数组中的位置（或输出“不存在”）。
$x$ 可以取 $n+1$ 种可能：$x < A[1]$，$x = A[1]$，$x = A[2]$，…，$x = A[n]$，或 $x > A[n]$。因此，决策树必须至少有 $n+1$ 个不同的叶子。
决策树是一棵二叉树，深度为 $d$ 的二叉树最多有 $2^d$ 个叶子。因此，为了区分 $n+1$ 种结果，必须有

$$2^d \ge n+1 \quad\Longrightarrow\quad d \ge \log_2 (n+1).$$

由于每一步比较对应树中的一层，最坏情况下的比较次数至少为 $d$，故任何确定性算法在最坏情况下至少需要 $\log_2(n+1) = \Omega(\log n)$ 次比较。