2024B

Question 7

Let $T(n)$ be the computation time in terms of the input size $n$. For each of the recurrences (1)-(3) shown below, write the complexity of $T(n)$ in terms of $n$. You may use Landau notations such as $O()$ if need be. Assume that $T(0)=1$. Note that $\lfloor x\rfloor$ is the maximum integer that is not larger than $x$.

1. $T(n)=T(n-1)+2n$
2. $T(n)=T(\lfloor n/3\rfloor )+1$
3. $T(n)=2T(\lfloor n/2\rfloor )+n+1$

Does the following proposition (4) hold true? State true or false first and prove it.

4. $T(n)\in O(2^n)$ if and only if $T(n)\in O(e^n)$.

Given the following recurrence (5), write the complexity of $T(n)$ in terms of $n$. $a$ is a positive constant.

5. $T(n)=aT(\lfloor n/2\rfloor )+\lfloor n{\log }_{2}n\rfloor$

---

设 $T(n)$ 为输入大小 $n$ 的计算时间。对于下列递推关系（1）-（3），写出 $T(n)$ 关于 $n$ 的复杂度。若有必要，可以使用朗道符号如 $O()$。假设 $T(0)=1$。注意，$\lfloor x\rfloor$ 是小于等于 $x$ 的最大整数。

1. $T(n)=T(n-1)+2n$
2. $T(n)=T(\lfloor n/3\rfloor )+1$
3. $T(n)=2T(\lfloor n/2\rfloor )+n+1$

以下命题（4）是否成立？首先陈述真伪并证明。

4. $T(n)\in O(2^n)$ 当且仅当 $T(n)\in O(e^n)$。

给定下列递推关系（5），写出 $T(n)$ 关于 $n$ 的复杂度。$a$ 是一个正常数。

5. $T(n)=aT(\lfloor n/2\rfloor )+\lfloor n{\log }_{2}n\rfloor$

---

Question 8

Suppose that the eigenvalues and the corresponding eigenvectors of an $n\times n$ square matrix $\mathbf{A}$ are ${\lambda }_1,\dots ,{\lambda }_n$ and ${\alpha }_1,\dots ,{\alpha }_n$ respectively.

Suppose that ${\mathbf{I}}_n$ is the $n\times n$ identity matrix, and the inverse matrix of an invertible matrix $\mathbf{C}$ is ${\mathbf{C}}^{-1}$.

Answer the following questions.

1. Show all the eigenvalues and the corresponding eigenvectors of ${\mathbf{A}}^2$.

2. If ${\lambda }_1,\dots ,{\lambda }_n$ are mutually different, show that ${\mathbf{P}}^{-1}\mathbf{AP}$ is a diagonal matrix, using $\mathbf{P}=({\alpha }_1,\dots ,{\alpha }_n)$ that is a matrix of concatenated eigenvectors.

3. Show all the eigenvalues and the corresponding eigenvectors of $\mathbf{B}$.

   3 & 0 & 0 \\ -2 & 3 & 2 \\ 0 & 0 & 1 \end{pmatrix}$$

4. Suppose that $\mu$ is the maximum eigenvalue of $\mathbf{B}$, and $\gamma =\left(\begin{array}{c}1\\ 0\\ 0\end{array}\right)$. Calculate $\delta =(\mathbf{B}-\mu {\mathbf{I}}_3)\gamma$.

5. Suppose that $\beta$ is the eigenvector of $\mathbf{B}$ corresponding to the minimum eigenvalue. Calculate ${\mathbf{Q}}^{-1}\mathbf{BQ}$ using $\mathbf{Q}=(\delta ,\gamma ,\beta )$ that is a matrix concatenating $\delta ,\gamma ,\beta$.

6. Suppose that $m$ is an arbitrary positive integer. Calculate ${\mathbf{B}}^m$.

---

假设 $n\times n$ 方阵 $\mathbf{A}$ 的特征值及相应的特征向量分别为 ${\lambda }_1,\dots ,{\lambda }_n$ 和 ${\alpha }_1,\dots ,{\alpha }_n$。

假设 ${\mathbf{I}}_n$ 是 $n\times n$ 的单位矩阵，并且可逆矩阵 $\mathbf{C}$ 的逆矩阵为 ${\mathbf{C}}^{-1}$。

回答以下问题。

1. 展示 ${\mathbf{A}}^2$ 的所有特征值及相应的特征向量。

2. 如果 ${\lambda }_1,\dots ,{\lambda }_n$ 是互不相同的，证明 ${\mathbf{P}}^{-1}\mathbf{AP}$ 是一个对角矩阵，其中 $\mathbf{P}=({\alpha }_1,\dots ,{\alpha }_n)$ 是由特征向量构成的矩阵。

3. 展示 $\mathbf{B}$ 的所有特征值及相应的特征向量。

3 & 0 & 0 \\ -2 & 3 & 2 \\ 0 & 0 & 1 \end{pmatrix}$$ 4. 假设 $\mu$ 是 $\mathbf{B}$ 的最大特征值，并且 $\mathbf{\gamma} = \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}$。 计算 $\mathbf{\delta} = (\mathbf{B} - \mu \mathbf{I}_3)\mathbf{\gamma}$。 5. 假设 $\beta$ 是 $\mathbf{B}$ 对应于最小特征值的特征向量。计算 $\mathbf{Q}^{-1}\mathbf{B}\mathbf{Q}$，其中 $\mathbf{Q} = (\mathbf{\delta}, \mathbf{\gamma}, \beta)$ 是由 $\mathbf{\delta}, \mathbf{\gamma}, \beta$ 构成的矩阵。 6. 假设 $m$ 是任意正整数。计算 $\mathbf{B}^m$。 --- ## Question 9 Answer the following problems regarding undirected graphs. 1. A complete tripartite graph $K_{r,s,t}$ consists of three vertex sets of size $r, s, t$. Every pair of vertices belonging to different sets is connected by an edge, and every pair of vertices belonging to the same set is not connected. Draw $K_{2,2,2}$. 2. Find the number of edges in $K_{r,s,t}$. 3. Let $n$ and $m$ denote the number of vertices and edges in a graph, respectively. A simple graph is a graph that does not contain any multi-edges or self-loops. Denote by $\binom{a}{b}$ the number of combinations of $b$ entities chosen from $a$ entities. Prove that a simple graph satisfying the following inequality is connected.

m > \left(\binom{n - 1}{2}\right)

4. An Eulerian graph is a graph with an Eulerian circuit. Show that the degree of every vertex of an Eulerian graph is even. 5. Show that a connected graph is an Eulerian graph, if the degree of every vertex is even. --- 解答以下关于无向图的问题。 1. 完全三分图 $K_{r,s,t}$ 由大小为 $r, s, t$ 的三个顶点集组成。每对属于不同集合的顶点由一条边连接，每对属于同一集合的顶点不连接。画出 $K_{2,2,2}$。 2. 找出 $K_{r,s,t}$ 中的边数。 3. 设 $n$ 和 $m$ 分别表示图中的顶点数和边数。简单图是指不包含任何多重边或自环的图。用 $\binom{a}{b}$ 表示从 $a$ 个实体中选取 $b$ 个实体的组合数。证明满足以下不等式的简单图是连通的。

m > \left(\binom{n - 1}{2}\right)

4. 欧拉图是具有欧拉回路的图。证明欧拉图的每个顶点的度数都是偶数。 5. 证明如果一个连通图的每个顶点的度数都是偶数，则该图是欧拉图。 --- ## Question 10 Suppose we have many DNA sequences. Each sequence has length $L$, and the number of sequences is $N$. The sequences are stored in an array $\mathbf{A}$, where $\mathbf{A}[i]$ holds the $i$-th sequence $(1 \leq i \leq N)$. Assume that copying one sequence from one memory location to another takes constant time. 1. We wish to sort the sequences in alphabetical order of their left-most base. Write pseudocode of an algorithm that puts the sorted sequences into another array $\mathbf{B}$. The running time of the algorithm should be linearly proportional to $N$. The sequences may contain any of the bases **a**, **c**, **g**, or **t**. Below this point, assume that the sequences only contain bases **a** and **c**, never **g** or **t**. 2. We wish to sort the sequences in alphabetical order of their $j$-th base $(1 \leq j \leq L)$, using less memory. The result should go in the array $\mathbf{A}$, and we are not allowed to use any other array. Write pseudocode of an algorithm to perform this sort. The running time should be linearly proportional to $N$. 3. We wish to sort the sequences in alphabetical order of the whole sequences. Write pseudocode of an algorithm to do this sort, using the answer to question (2) as a subroutine. The worst-case running time should be linearly proportional to $L \times N$. --- 假设我们有许多DNA序列。每个序列的长度为 $L$，序列的数量为 $N$。序列存储在数组 $\mathbf{A}$ 中，其中 $\mathbf{A}[i]$ 保存第 $i$ 个序列 $(1 \leq i \leq N)$。假设将一个序列从一个内存位置复制到另一个位置的时间是恒定的。 1. 我们希望按序列最左边的碱基的字母顺序排序。编写一个算法的伪代码，将排序后的序列放入另一个数组 $\mathbf{B}$。算法的运行时间应与 $N$ 成线性比例。序列可能包含 **a**、**c**、**g** 或 **t** 中的任意碱基。 以下假设序列仅包含碱基 **a** 和 **c**，不包含 **g** 或 **t**。 2. 我们希望按序列的第 $j$ 个碱基的字母顺序排序 $(1 \leq j \leq L)$，使用较少的内存。结果应存放在数组 $\mathbf{A}$ 中，不允许使用任何其他数组。编写一个算法的伪代码来执行此排序。运行时间应与 $N$ 成线性比例。 3. 我们希望按整个序列的字母顺序对序列进行排序。编写一个算法的伪代码来执行此排序，使用问题（2）的答案作为子例程。最坏情况下的运行时间应与 $L \times N$ 成线性比例。 --- ## Question 11 A quantum state of a 1-qubit quantum computer can be represented by a $2 \times 2$ complex matrix $\rho = \frac{1}{2} \begin{pmatrix} 1 + a & b - ic \\ b + ic & 1 - a \end{pmatrix}$ called a density matrix. Here, $i = \sqrt{-1}$ is the imaginary unit that satisfies $i^2 = -1$ and $a, b, c$ are real numbers that satisfy $a^2 + b^2 + c^2 \leq 1$. By measuring the qubit represented by matrix $\rho$ in the computational basis (also called the Z-basis), we observe state 0 or state 1 with probabilities $p_0 = \frac{1 + a}{2}$ and $p_1 = \frac{1 - a}{2}$, which are the diagonal elements of matrix $\rho$, respectively. Answer the following questions with mathematical derivation. 1. Show that all the eigenvalues of matrix $\rho$ are non-negative real numbers. 2. Answer the probability that state 0 is observed by measurement in the computational basis after applying quantum gate operation $H = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$ to quantum state $\rho$. 3. Answer the probability that state 0 is observed by measurement in the computational basis after applying quantum gate operation $Y = \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}$ to quantum state $\rho$. 4. Let $\rho' = \frac{1}{2} \begin{pmatrix} 1 + a' & b' - ic' \\ b' + ic' & 1 - a' \end{pmatrix}$ be the quantum state after applying quantum gate operation $U = \begin{pmatrix} u_{00}' + iu_{00}'' & u_{01}' + iu_{01}'' \\ u_{10}' + iu_{10}'' & u_{11}' + iu_{11}'' \end{pmatrix}$ to quantum state $\rho$. Compute $a'^2 + b'^2 + c'^2$. --- 1个量子比特量子计算机的量子态可以表示为一个 $2 \times 2$ 的复数矩阵 $\rho = \frac{1}{2} \begin{pmatrix} 1 + a & b - ic \\ b + ic & 1 - a \end{pmatrix}$，称为密度矩阵。这里，$i = \sqrt{-1}$ 是满足 $i^2 = -1$ 的虚数单位，$a, b, c$ 是满足 $a^2 + b^2 + c^2 \leq 1$ 的实数。通过在计算基（也称为Z基）中测量由矩阵 $\rho$ 表示的量子比特，我们以概率 $p_0 = \frac{1 + a}{2}$ 和 $p_1 = \frac{1 - a}{2}$ 观察到状态0或状态1，分别对应密度矩阵 $\rho$ 的对角元素。用数学推导回答以下问题。 1. 证明矩阵 $\rho$ 的所有特征值都是非负实数。 2. 在对量子态 $\rho$ 施加量子门操作 $H = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$ 后，在计算基中测量观察到状态0的概率是多少。 3. 在对量子态 $\rho$ 施加量子门操作 $Y = \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}$ 后，在计算基中测量观察到状态0的概率是多少。 4. 设 $\rho' = \frac{1}{2} \begin{pmatrix} 1 + a' & b' - ic' \\ b' + ic' & 1 - a' \end{pmatrix}$ 是施加量子门操作 $U = \begin{pmatrix} u_{00}' + iu_{00}'' & u_{01}' + iu_{01}'' \\ u_{10}' + iu_{10}'' & u_{11}' + iu_{11}'' \end{pmatrix}$ 后的量子态。计算 $a'^2 + b'^2 + c'^2$。 --- ## Question 12 Nanopore sequencers can read DNA sequences via electric current. The readout from a DNA sequence was a series of current values $\{A_t\}$ $(0 \leq A_t \leq 1)$ for time $t = 1, 2, \dots, n$. The DNA sequence is known to contain a reference sequence. The readout from the reference sequence was a series of current values $\{B_t\}$ $(0 \leq B_t \leq 1)$ for time $t = 1, 2, \dots, m$ (reference signal, hereafter). We wish to find the time interval in $\{A_t\}$ that corresponds to the reference sequence. The speed of reading DNA sequences may fluctuate during the run, and therefore we wish to look for the reference signal while allowing shifts in the time axis. To this end, we assume that there exist $1 \leq p_1 \leq p_2 \leq \dots \leq p_m \leq n$ $(p_{t+1} - p_t \leq W$ for $1 \leq t < m$; $W$ is a positive integer) such that $B_t$ corresponds to $A_{p_t}$. Without reading noise, we would have expected that $B_t = A_{p_t}$ holds, but however, we need to consider reading noise and lags in timing of reading current values. Here, we assume that, when the dissimilarity, $\sum_{t=1}^m (B_t - A_{p_t})^2$, is minimized, mapping $p_1, p_2, \dots, p_m$ represents the correspondence between the reference signal and the corresponding part of the nanopore sequencer output. 1. Assume $m = 1$. Show an algorithm to find a $p_1$ such that the dissimilarity is minimized. 2. Assume $m = 2$. Show an algorithm to find a pair $p_1, p_2$ such that the dissimilarity is minimized. 3. Explain in a single line what physical condition $W$ represents. 4. $D_{i,j}$ denotes the minimum dissimilarity of $\{A_{1, A_2, \dots, A_j}\}$ against a reference signal $\{B_1, B_2, \dots, B_i\}$ when $B_i$ corresponds to $A_j$. Find $D_{i,j}$ in terms of $D_{x,y}$ $(x < i, y \leq j)$. 5. Show an algorithm to calculate the minimum dissimilarity of $\{A_t\}$ against reference signal $\{B_t\}$. Also show the time complexity of the algorithm in terms of $n, m, W$. --- ![[Pasted image 20240804162643.png]] --- 纳米孔测序仪可以通过电流读取DNA序列。从DNA序列的读取结果是一系列电流值 $\{A_t\}$ $(0 \leq A_t \leq 1)$，对应时间 $t = 1, 2, \dots, n$。已知DNA序列包含一个参考序列。参考序列的读取结果是一系列电流值 $\{B_t\}$ $(0 \leq B_t \leq 1)$，对应时间 $t = 1, 2, \dots, m$（以下简称为参考信号）。我们希望找到 $\{A_t\}$ 中与参考序列对应的时间区间。 在运行过程中，读取DNA序列的速度可能会波动，因此我们希望在允许时间轴发生偏移的情况下寻找参考信号。为此，我们假设存在 $1 \leq p_1 \leq p_2 \leq \dots \leq p_m \leq n$ $(p_{t+1} - p_t \leq W$ 其中 $1 \leq t < m$；$W$ 是一个正整数) 使得 $B_t$ 对应于 $A_{p_t}$。在没有读取噪声的情况下，我们会期望 $B_t = A_{p_t}$ 成立，但由于读取噪声和读取电流值的时序滞后，我们假设当不相似度 $\sum_{t=1}^m (B_t - A_{p_t})^2$ 最小时，映射 $p_1, p_2, \dots, p_m$ 代表了参考信号和纳米孔测序仪输出的对应部分。 1. 假设 $m = 1$。给出一种算法找到 $p_1$ 使不相似度最小。 2. 假设 $m = 2$。给出一种算法找到 $p_1, p_2$ 使不相似度最小。 3. 用一句话解释物理条件 $W$ 代表什么。 4. $D_{i,j}$ 表示在 $B_i$ 对应于 $A_j$ 时 $\{A_{1, A_2, \dots, A_j}\}$ 与参考信号 $\{B_1, B_2, \dots, B_i\}$ 的最小不相似度。用 $D_{x,y}$ $(x < i, y \leq j)$ 表示 $D_{i,j}$。 5. 给出一种算法计算 $\{A_t\}$ 对参考信号 $\{B_t\}$ 的最小不相似度。并给出算法的时间复杂度（用 $n, m, W$ 表示）。