2020

Question 7

Let $A=\{a_1,a_2,\dots ,a_N\}$ $(1\le a_1,a_2,\dots ,a_N\le W,a_i\ne a_j\text{ if }i\ne j,1\le N\le W)$ be an array of size $N$, whose elements are different integers ranging from $1$ to $W$. Let $S(A)$ be the number of all possible distinct arrays each of which can be created by iteratively applying the following operation to $A$, $0$ or more times.

Operation: choose arbitrary $i$ that satisfies $1\le i\le N-1$ and $a_i+a_{i+1}<W$, and swap the values of $a_i$ and $a_{i+1}$.

We denote the largest number in array $A$ by $a_h$, and the smallest number by $a_l$.

1. Let $A=\{4,1,10,3,2\}$. Show $S(A)$ for $W=11,12$, respectively.

2. When $a_h+a_l<W$, prove $S(A)=N\cdot S(A-a_l)$. Here, $A-a_l$ denotes an array that is array $A$ with element $a_l$ removed.

3. When $a_h+a_l\ge W$, prove $S(A)=S(\{a_1,a_2,\dots ,a_{h-1}\})\cdot S(\{a_{h+1},a_{h+2},\dots ,a_N\})$. Here, we define $S(\varnothing )=1$.

4. Show an algorithm that computes $S(A)$ from $A$ using (2) and (3).

5. Let $W=N$. We define $T(A)$ as the worst time complexity of the algorithm you showed in (4). Write $T(A)$ in terms of $N$, and prove it. You can assume that addition, comparison, copy of two elements take unit time.

6. Let $W=N$. Assuming that the $N!$ possible permutations have equal probability of being generated as the input array, write the average time complexity of the algorithm you showed in (4).

---

设 $A=\{a_1,a_2,\dots ,a_N\}$ $(1\le a_1,a_2,\dots ,a_N\le W,a_i\ne a_j\text{ 当 }i\ne j,1\le N\le W)$ 为一个大小为 $N$ 的数组，其元素为 $1$ 到 $W$ 范围内的不同整数。设 $S(A)$ 为可以通过对 $A$ 进行 $0$ 次或多次以下操作创建的所有可能不同数组的数量。

操作：选择满足 $1\le i\le N-1$ 且 $a_i+a_{i+1}<W$ 的任意 $i$，交换 $a_i$ 和 $a_{i+1}$ 的值。

我们将数组 $A$ 中的最大数记为 $a_h$，最小数记为 $a_l$。

1. 设 $A=\{4,1,10,3,2\}$。分别显示 $W=11,12$ 时的 $S(A)$。

2. 当 $a_h+a_l<W$ 时，证明 $S(A)=N\cdot S(A-a_l)$。这里，$A-a_l$ 表示从数组 $A$ 中移除元素 $a_l$ 后的数组。

3. 当 $a_h+a_l\ge W$ 时，证明 $S(A)=S(\{a_1,a_2,\dots ,a_{h-1}\})\cdot S(\{a_{h+1},a_{h+2},\dots ,a_N\})$。这里，我们定义 $S(\varnothing )=1$。

4. 使用 (2) 和 (3) 展示一个从 $A$ 计算 $S(A)$ 的算法。

5. 设 $W=N$。我们定义 $T(A)$ 为你在 (4) 中展示的算法的最坏时间复杂度。用 $N$ 表示 $T(A)$，并证明它。你可以假设两个元素的加法、比较、复制操作的时间为一个单位时间。

6. 设 $W=N$。假设 $N!$ 个可能的排列作为输入数组被生成的概率相等，写出你在 (4) 中展示的算法的平均时间复杂度。

---

Question 8

Assume that the following equation holds for $n\times n$ square matrices, $A=\{a_{ij}\}$, $P=\{p_{ij}\}$ and $\mathbf{\Lambda }=\{{\lambda }_{ij}\}$:

$$P^{-1}AP=\mathbf{\Lambda }$$

Assume that $n\ge 2$, $P^{-1}$ is the inverse matrix of $P$, ${\lambda }_{ii}\ne 0$, and ${\lambda }_{ij}=0$ if $i\ne j$.

Solve the following problems.

1. Show the inverse matrix for each of $\mathbf{\Lambda }$ and $A$.

2. Show that ${\lambda }_{ii}$ is one of the eigenvalues of $A$, and show one of the corresponding eigenvectors of $A$.

3. Suppose that $k$ is a positive integer. Show every pair of eigenvalue and corresponding eigenvector of $A^k$.

---

假设对于 $n\times n$ 的方阵 $A=\{a_{ij}\}$、$P=\{p_{ij}\}$ 和 $\mathbf{\Lambda }=\{{\lambda }_{ij}\}$，以下等式成立：

$$P^{-1}AP=\mathbf{\Lambda }$$

假设 $n\ge 2$，$P^{-1}$ 是 $P$ 的逆矩阵，${\lambda }_{ii}\ne 0$，且当 $i\ne j$ 时 ${\lambda }_{ij}=0$。

解决以下问题。

1. 展示 $\mathbf{\Lambda }$ 和 $A$ 的逆矩阵。

2. 证明 ${\lambda }_{ii}$ 是 $A$ 的一个特征值，并展示 $A$ 的一个对应特征向量。

3. 假设 $k$ 是一个正整数。展示 $A^k$ 的每对特征值和对应特征向量。

---

Question 9

Answer the following problems about undirected graphs.

1. Prove that the sum of degrees of all vertices of an undirected graph is even.

2. Chemical formula $C_5{H}_{12}$ corresponds to several structural isomers. Show all isomers as graphs. The following graph represents $C{H}_4$.

	H
	|
H - C - H
    |
    H

3. Three servers are connected as in the graph below. The network is functional when the graph is connected. Each edge disconnects independently with probability $p$. Find the probability of the network being functional as a function of $p$.

O
|\
| \
|  \
O---O

---

回答以下关于无向图的问题。

1. 证明无向图中所有顶点度数之和是偶数。

2. 化学式 $C_5{H}_{12}$ 对应于几种结构异构体。将所有异构体表示为图。以下图表示 $C{H}_4$。

	H
	|
H - C - H
    |
    H

3. 三台服务器按下图连接。当图是连通时，网络是功能性的。每条边以概率 $p$ 独立断开。找到网络作为 $p$ 的函数是功能性的概率。

O
|\
| \
|  \
O---O

---

Question 10

Let $H[1,\dots ,n]$ be an array of $n$ real numbers. We call $H[1,\dots ,n]$ a heap if $H\left[\lfloor \frac{i}{2}\rfloor \right]\ge H[i]$ for $2\le i\le n$, where $\lfloor \frac{i}{2}\rfloor$ is the integer quotient of $i$ divided by 2. Answer the following questions.

1. Give an algorithm that makes $H[1,\dots ,n]$ a heap in $O(n)$ worst-case time.

2. If $H[1,\dots ,n]$ is a heap, prove that $H[1]$ is the maximum element.

3. Using the notion of heap, describe an algorithm that sorts an arbitrary array $H[1,\dots ,n]$ in $O(n\log n)$ worst-case time.

---

设 $H[1,\dots ,n]$ 为一个包含 $n$ 个实数的数组。如果 $H[1,\dots ,n]$ 满足 $H\left[\lfloor \frac{i}{2}\rfloor \right]\ge H[i]$，其中 $2\le i\le n$，且 $\lfloor \frac{i}{2}\rfloor$ 为 $i$ 除以 2 的整数商，则称 $H[1,\dots ,n]$ 为堆。回答以下问题。

1. 给出一个使 $H[1,\dots ,n]$ 在最坏情况下时间复杂度为 $O(n)$ 的堆化算法。

2. 如果 $H[1,\dots ,n]$ 是一个堆，证明 $H[1]$ 是最大元素。

3. 使用堆的概念，描述一个在最坏情况下时间复杂度为 $O(n\log n)$ 的排序任意数组 $H[1,\dots ,n]$ 的算法。

---

Question 11

Machine A produces a sequence $x=x_1{x}_2\cdots x_n$ with the following output probability $\{{\beta }_k\}$.

Output probabilities: $P(x_s=k)={\beta }_k$ for $k\in \{a,c,g,t\}$, $s=1,2,\dots ,n$.

Machine B produces a sequence $x=x_1{x}_2\cdots x_n$ by a stationary first-order Markov model with the following initial probabilities $\{{\pi }_k\}$ and transition probabilities $\{{\lambda }_{ij}\}$.

Initial Probabilities: $P(x_1=k)={\pi }_k$ for $k\in \{a,c,g,t\}$.

Transition Probabilities: $P(x_s=j\mid x_{s-1}=i)={\lambda }_{ij}$ for $i,j\in \{a,c,g,t\}$, $s=2,\dots ,n$.

Machine C converts each occurrence of ac in an input sequence independently to gt with probability $ϵ$.

Assume that $P(X)$ is the probability that $X$ is true, and that $P(X\mid Y)$ is the conditional probability that $X$ is true when $Y$ is true. Assume also that $P_A(x)$ is the probability that Machine A outputs a sequence $x$, and $P_B(x)$ is the probability that Machine B outputs a sequence $x$.

Solve the following problems. For (2) to (4), you can use $P_A(x)$ and $P_B(x)$ by substituting $x$ with any concrete sequence ($P_A(\text{actgt})$, for example) as they are.

1. When $n=5$, show the four probabilities, $P_A(\text{actgt})$, $P_A(\text{actac})$, $P_B(\text{actgt})$, $P_B(\text{actac})$.
2. When $n=5$, three sequences from Machine A and two sequences from Machine B were produced. When a sequence is selected randomly from those five sequences, it was actgt. Show the probability that this sequence was one of the three sequences produced from Machine A.
3. When $n=5$, show the probability that the output sequence of Machine C is actgt when the input of Machine C was an output of Machine A.
4. Five sequences were produced in the same manner as (2), and two sequences were randomly selected from the five sequences. When one of the selected two sequences was used as the input of Machine C, both the output sequence of Machine C and the remaining sequence were actgt. Show the probability that those two sequences were originally produced from the same machine (Machine A or Machine B).

---

机器 A 产生一个序列 $x=x_1{x}_2\cdots x_n$，其输出概率为 $\{{\beta }_k\}$。

输出概率：$P(x_s=k)={\beta }_k$，其中 $k\in \{a,c,g,t\}$，$s=1,2,\dots ,n$。

机器 B 通过一个固定的一阶马尔可夫模型产生一个序列 $x=x_1{x}_2\cdots x_n$，其初始概率 $\{{\pi }_k\}$ 和转移概率 $\{{\lambda }_{ij}\}$ 如下。

初始概率：$P(x_1=k)={\pi }_k$，其中 $k\in \{a,c,g,t\}$。

转移概率：$P(x_s=j\mid x_{s-1}=i)={\lambda }_{ij}$，其中 $i,j\in \{a,c,g,t\}$，$s=2,\dots ,n$。

机器 C 将输入序列中的每次出现的 ac 独立地以概率 $ϵ$ 转换为 gt。

假设 $P(X)$ 是 $X$ 为真的概率，$P(X\mid Y)$ 是 $Y$ 为真时 $X$ 为真的条件概率。同样假设 $P_A(x)$ 是机器 A 输出序列 $x$ 的概率，$P_B(x)$ 是机器 B 输出序列 $x$ 的概率。

解决以下问题。从 (2) 到 (4)，你可以直接使用 $P_A(x)$ 和 $P_B(x)$，用任何具体序列（例如 $P_A(\text{actgt})$）代替 $x$。

1. 当 $n=5$ 时，展示四个概率 $P_A(\text{actgt})$，$P_A(\text{actac})$，$P_B(\text{actgt})$，$P_B(\text{actac})$。
2. 当 $n=5$ 时，机器 A 产生三个序列，机器 B 产生两个序列。当从这五个序列中随机选择一个序列时，它是 actgt。展示该序列是从机器 A 产生的三个序列之一的概率。
3. 当 $n=5$ 时，展示当机器 C 的输入是机器 A 的输出时，机器 C 的输出序列是 actgt 的概率。
4. 按照 (2) 的方式产生五个序列，随机从这五个序列中选择两个序列。当选定的两个序列之一被用作机器 C 的输入时，机器 C 的输出序列和剩余的序列都是 actgt。展示这两个序列最初是由同一台机器（机器 A 或机器 B）产生的概率。

---

Question 12

For a mouse aging experiment, we need to pair male and female mice, with these rules:

• Each mouse can match at most one other mouse.
• Each match must be between opposite genders.
• A female can only match a younger male.

Assume that no two mice have exactly the same age. We have a list of $n$ mice, numbered from 1 to $n$ in order of increasing age.

$$F[i]=\{\begin{array}{ll}0& \text{if the i-th mouse is male}\\ 1& \text{if the i-th mouse is female}\end{array}$$

$G[i]$ is the number of males among the first $i$ mice.

$C[i,j]$ is the number of ways of making $j$ matches among the first $i$ mice.

Let $C[i,0]=1$ (i $\ge$ 1).

1. What is $C[1,j]$ when $j>0$?
2. Suppose we have already made $j$ matches among the first $i$ mice, and $F[i+1]=1$. How many remaining ways are there of matching the $(i+1)$-th mouse?
3. Write a formula for $C[i+1,j+1]$ in terms of $C[i,j+1]$ and $C[i,j]$.

---

在一项小鼠衰老实验中，我们需要为雄性和雌性小鼠配对，规则如下：

• 每只小鼠最多只能与另一只小鼠匹配。
• 每次匹配必须是异性之间的匹配。
• 雌性只能与比自己年轻的雄性匹配。

假设没有两只小鼠年龄完全相同。我们有一个编号为 1 到 $n$ 的小鼠列表，按年龄递增顺序排列。

$$F[i]=\{\begin{array}{ll}0& \text{如果第 i 只小鼠是雄性}\\ 1& \text{如果第 i 只小鼠是雌性}\end{array}$$

$G[i]$ 是前 $i$ 只小鼠中雄性的数量。

$C[i,j]$ 是前 $i$ 只小鼠中进行 $j$ 次匹配的方法数量。

设 $C[i,0]=1$ (i $\ge$ 1)。

1. 当 $j>0$ 时，$C[1,j]$ 是多少？
2. 假设我们已经在前 $i$ 只小鼠中进行了 $j$ 次匹配，且 $F[i+1]=1$。匹配第 $(i+1)$ 只小鼠还有多少剩余的方法？
3. 用 $C[i,j+1]$ 和 $C[i,j]$ 表示 $C[i+1,j+1]$ 的公式。