2015

Question 7

When we analyze the worst time complexity of an algorithm, it is worth observing how the computation time $T(n)$ increases as $n$ $(1<n)$, the size of input data, increases. The Landau’s $O$ notation, which is often used for representing an asymptotic upper bound of $T(n)$ ignoring the constant factor, is defined as the following. For a positive function $f(n)$, if there exists a positive constant $c$, and

$$\underset{n\to \infty }{\lim }\frac{T(n)}{f(n)}<c$$

holds, then

$$T(n)\in O(f(n))$$

is defined to hold.

1. $O(f(n))$ and $O(g(n))$ are defined to be equal if $T(n)\in O(f(n))$ and $T(n)\in O(g(n))$ are equivalent for any $T(n)$. For each of (A) to (C), find all formulae in the box below that are equal to it. If there is no such formula, just write “none”.

   (A) $O(n^3)$ (B) $O(n\log n)$ (C) $O(n!)$

$$\begin{array}{cccc}O(1),& O(n+1),& O(n^2+n+1),& O(n^3+n^2+n+1),\\ O(n^4+n^3),& O(\log n),& O({\log }_e{n}^2),& O(({\log }_{e}n{)}^n),\\ O(2n{\log }_{2}n),& O(e^n),& O\left({\left(\frac{n}{e}\right)}^n\right),& O(2^n),\\ O(n^n)& & & \end{array}$$

2. For each proposition below, determine with proof whether it holds or not. Note that $f(n)$ and $g(n)$ are positive functions.

(A) $O(f(n)+g(n))$ and $O(\max (f(n),g(n)))$ are equal.

(B) If $f(n)\in O(g(n))$ holds, then $e^{f(n)}\in O(e^{g(n)})$.

---

当我们分析一个算法的最坏时间复杂度时，观察计算时间 $T(n)$ 随输入数据大小 $n$ $(1<n)$ 的增加而增加是很有价值的。Landau 的 $O$ 表示法，通常用于表示忽略常数因子的 $T(n)$ 的渐近上界，定义如下。对于一个正函数 $f(n)$，如果存在一个正常数 $c$，且

$$\underset{n\to \infty }{\lim }\frac{T(n)}{f(n)}<c$$

成立，则定义

$$T(n)\in O(f(n))$$

成立。

1. 如果 $T(n)\in O(f(n))$ 和 $T(n)\in O(g(n))$ 对任何 $T(n)$ 都等价，则定义 $O(f(n))$ 和 $O(g(n))$ 是相等的。对于 (A) 到 (C) 的每一个，找到下面框中等于它的所有公式。如果没有这样的公式，只写“none”。

   (A) $O(n^3)$ (B) $O(n\log n)$ (C) $O(n!)$

$$\begin{array}{cccc}O(1),& O(n+1),& O(n^2+n+1),& O(n^3+n^2+n+1),\\ O(n^4+n^3),& O(\log n),& O({\log }_e{n}^2),& O(({\log }_{e}n{)}^n),\\ O(2n{\log }_{2}n),& O(e^n),& O\left({\left(\frac{n}{e}\right)}^n\right),& O(2^n),\\ O(n^n)& & & \end{array}$$

2. 对于下面的每个命题，确定是否成立，并提供证明。注意 $f(n)$ 和 $g(n)$ 是正函数。

• (A) $O(f(n)+g(n))$ 和 $O(\max (f(n),g(n)))$ 是相等的。

• (B) 如果 $f(n)\in O(g(n))$ 成立，则 $e^{f(n)}\in O(e^{g(n)})$。

---

Question 8

Let $Z^{\ast }=\left\{\left(\begin{array}{c}{z}_1\\ z_2\end{array}\right):\text{complex number},|z_1{|}^2+|z_2{|}^2\ne 0\right\}$ be the set of non-zero complex two-dimensional vectors. Let $M=\left(\begin{array}{cc}a& b\\ b& d\end{array}\right)$ be a 2 by 2 real symmetric matrix, and $I=\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)$ be the unit matrix.

1. Find all the eigenvalues ${\lambda }_1,{\lambda }_2$ of $M$.

2. Under the assumption of ${\lambda }_1\ne {\lambda }_2$, answer i) and ii).

   i) Let $U=(v_1,v_2)$ be the matrix whose first and second columns consist of the eigenvectors $v_1$ and $v_2$ for the eigenvalues ${\lambda }_1$ and ${\lambda }_2$, respectively. Show that $U$ is invertible and satisfies $M=U\left(\begin{array}{cc}{\lambda }_1& 0\\ 0& {\lambda }_2\end{array}\right)U^{-1}$.

   ii) Prove that the set $\{U^{-1}x|x\in Z^{\ast }\}$ and $Z^{\ast }$ are equal.

3. For each of the statements A), B), and C), answer the conditions on matrix elements $a,b,d$ for the statement to hold.

   A) Every $y\in Z^{\ast }$ can be expressed as $y=Mx$ with some $x\in Z^{\ast }$.

   B) No $y\in Z^{\ast }$ can be expressed as $y=Mx$ with some $x\in Z^{\ast }$.

   C) At least one $y\in Z^{\ast }$ can be expressed as $y=(M-{\lambda }_{1}I)x$ with some $x\in Z^{\ast }$.

---

设 $Z^{\ast }=\left\{\left(\begin{array}{c}{z}_1\\ z_2\end{array}\right):\text{复数},|z_1{|}^2+|z_2{|}^2\ne 0\right\}$ 为非零复二维向量的集合。设 $M=\left(\begin{array}{cc}a& b\\ b& d\end{array}\right)$ 为一个 2×2 的实对称矩阵，$I=\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)$ 为单位矩阵。

1. 找出 $M$ 的所有特征值 ${\lambda }_1,{\lambda }_2$。

2. 在假设 ${\lambda }_1\ne {\lambda }_2$ 的条件下，回答 i) 和 ii)。

   i) 设 $U=(v_1,v_2)$ 为一个矩阵，其第一列和第二列分别由特征值 ${\lambda }_1$ 和 ${\lambda }_2$ 的特征向量 $v_1$ 和 $v_2$ 组成。证明 $U$ 是可逆的，并且满足 $M=U\left(\begin{array}{cc}{\lambda }_1& 0\\ 0& {\lambda }_2\end{array}\right)U^{-1}$。

   ii) 证明集合 $\{U^{-1}x|x\in Z^{\ast }\}$ 和 $Z^{\ast }$ 是相等的。

3. 对于每个陈述 A), B), 和 C)，回答矩阵元素 $a,b,d$ 的条件使该陈述成立。

   A) 每个 $y\in Z^{\ast }$ 都可以表示为 $y=Mx$，其中 $x\in Z^{\ast }$。

   B) 没有 $y\in Z^{\ast }$ 可以表示为 $y=Mx$，其中 $x\in Z^{\ast }$。

   C) 至少有一个 $y\in Z^{\ast }$ 可以表示为 $y=(M-{\lambda }_{1}I)x$，其中 $x\in Z^{\ast }$。

---

Question 9

An array of $n$ real numbers, $H[1,\dots ,n]$, is called a heap if $H[\lfloor i/2\rfloor ]\ge H[i]$ for $1<i\le n$, where $\lfloor i/2\rfloor$ is the quotient of integer $i$ divided by 2 (e.g., $\lfloor 4/2\rfloor =\lfloor 5/2\rfloor =2$). A heap can be treated as a binary tree such that $H[1]$ is the root node and $H[\lfloor i/2\rfloor ]$ is the parent node of $H[i]$. Answer the following questions.

1. Explain whether array $[6,3,4,1,0,3,4,2]$ is a heap or not.
2. Show that if $H[1,\dots ,n]$ is a heap, $H[1,\dots ,j]$ is also a heap for any $j$ $(1\le j<n)$.
3. Suppose that $H[1,\dots ,n]$ is a heap but $H[1,\dots ,n+1]$ is not. Describe a procedure that exchanges elements in $H[1,\dots ,n+1]$ to make it a heap in $O(\log n)$ worst-case time.
4. Suppose that $H[1,\dots ,n]$ is a heap. Prove that $H[1]$ is maximum among all elements in $H[1,\dots ,n]$. Suppose that after replacing $H[1]$ with $H[n]$, $H[1,\dots ,n-1]$ is not a heap. Describe a procedure that exchanges elements in $H[1,\dots ,n-1]$ to make it a heap in $O(\log n)$ worst-case time.
5. Describe an algorithm that exchanges elements in $H[1,\dots ,n]$ to make it a heap in $O(n)$ worst-case time.
6. Using the procedures defined above, describe an algorithm that sorts array $H[1,\dots ,n]$ in $O(n\log n)$ worst-case time.

---

一个包含 $n$ 个实数的数组 $H[1,\dots ,n]$，如果满足 $H[\lfloor i/2\rfloor ]\ge H[i]$ 对于 $1<i\le n$，其中 $\lfloor i/2\rfloor$ 是整数 $i$ 除以 2 的商（例如，$\lfloor 4/2\rfloor =\lfloor 5/2\rfloor =2$），则称其为堆。堆可以被看作是一个二叉树，其中 $H[1]$ 是根节点，$H[\lfloor i/2\rfloor ]$ 是 $H[i]$ 的父节点。回答以下问题。

1. 解释数组 $[6,3,4,1,0,3,4,2]$ 是否是一个堆。
2. 证明如果 $H[1,\dots ,n]$ 是一个堆，那么 $H[1,\dots ,j]$ 也是一个堆，对于任何 $j$ $(1\le j<n)$。
3. 假设 $H[1,\dots ,n]$ 是一个堆，但 $H[1,\dots ,n+1]$ 不是。描述一种在 $O(\log n)$ 最坏情况下，将 $H[1,\dots ,n+1]$ 中的元素交换使其成为堆的方法。
4. 假设 $H[1,\dots ,n]$ 是一个堆。证明 $H[1]$ 是 $H[1,\dots ,n]$ 中最大的元素。假设在用 $H[n]$ 替换 $H[1]$ 后，$H[1,\dots ,n-1]$ 不是一个堆。描述一种在 $O(\log n)$ 最坏情况下，将 $H[1,\dots ,n-1]$ 中的元素交换使其成为堆的方法。
5. 描述一种在 $O(n)$ 最坏情况下，将 $H[1,\dots ,n]$ 中的元素交换使其成为堆的算法。
6. 使用上述定义的方法，描述一种在 $O(n\log n)$ 最坏情况下，对数组 $H[1,\dots ,n]$ 进行排序的算法。

---

Question 10

A bipartite graph is an undirected graph whose nodes can be divided into two groups such that any two nodes in a group are not connected by an edge. Answer the following questions about bipartite graphs.

1. Write the incidence matrix of the following graph $G$.

graph TB
	subgraph BLACK_NODES
		v1
		v2
		v3
		v4
	end

	subgraph WHITE_NODES
		v5
		v6
		v7
		v8
	end
	
	v1 --- v6
	v1 --- v8
	v2 --- v5
	v2 --- v6
	v3 --- v7
	v3 --- v8
	v4 --- v5
	v4 --- v8

2. A matching in a graph is a set of edges without common nodes. A perfect matching is a matching that covers all nodes of the graph. List all perfect matchings of $G$.

3. Prove that a tree is always a bipartite graph.

4. Prove that a bipartite graph does not contain a circuit with an odd number of edges.

---

二分图是一个无向图，其节点可以分为两组，使得组内的任意两个节点不通过边连接。回答以下关于二分图的问题。

1. 写出以下图 $G$ 的关联矩阵。

graph TB
	subgraph BLACK_NODES
		v1
		v2
		v3
		v4
	end

	subgraph WHITE_NODES
		v5
		v6
		v7
		v8
	end
	
	v1 --- v6
	v1 --- v8
	v2 --- v5
	v2 --- v6
	v3 --- v7
	v3 --- v8
	v4 --- v5
	v4 --- v8

2. 图中的一个匹配是一组没有公共节点的边。完美匹配是覆盖图中所有节点的匹配。列出图 $G$ 的所有完美匹配。

3. 证明树总是一个二分图。

4. 证明二分图不包含奇数条边的回路。

---

Question 11

For an arbitrary random variable $X$ that takes values in non-negative integers, we define the probability generating function ${\phi }_X(s)$ of $X$ as ${\phi }_X(s)=E\{s^X\}={\sum }_{k=0}^{\infty }{s}^k\mathrm{Pr}\{X=k\}$. Here, $E\{A\}$ denotes the expected value of $A$, $\mathrm{Pr}\{X=k\}$ denotes the probability that $X$ assumes value $k$, and $s$ represents a real number.

1. Show the following equalities (a), (b). (a) ${\phi }_X(1)=1$ (b) $\frac{d{\phi }_X}{ds}(1)=E\{X\}$

In the following, $N$ and $U_i$ $(i=1,2,\dots )$ are mutually independent, identically distributed random variables that take values in non-negative integers.

2. For a positive integer $n$, we define a random variable $Y_n=Y_n(U_1,U_2,\dots )={\sum }_{i=1}^n{U}_i$. Show ${\phi }_{Y_n}(s)={\phi }_N(s{)}^n$.

3. We define a random variable $W=W(N,Y_1,Y_2,\dots )={\sum }_{n=1}^{\infty }{Y}_{n}I(N=n)$. Here,

$$I(N=n)=\{\begin{array}{ll}1& \text{if }N=n\\ 0& \text{if }N\ne n\end{array}$$

Show ${\phi }_W(s)={\phi }_N({\phi }_N(s))$.

(Hint: $\mathrm{Pr}\{W=k\}={\sum }_{n=1}^{\infty }\mathrm{Pr}\{Y_n=k\}\mathrm{Pr}\{N=n\}$ for a positive integer $k$)

4. For $\mathrm{Pr}\{N=k\}=q^k(1-q)$, $(0<q<1)$, calculate $E\{N\}$ and $E\{W\}$.

---

对于一个取非负整数值的任意随机变量 $X$，我们定义 $X$ 的概率生成函数 ${\phi }_X(s)$ 为 ${\phi }_X(s)=E\{s^X\}={\sum }_{k=0}^{\infty }{s}^k\mathrm{Pr}\{X=k\}$。其中，$E\{A\}$ 表示 $A$ 的期望值，$\mathrm{Pr}\{X=k\}$ 表示 $X$ 取值为 $k$ 的概率，$s$ 表示一个实数。

1. 证明以下等式 (a), (b)。 (a) ${\phi }_X(1)=1$ (b) $\frac{d{\phi }_X}{ds}(1)=E\{X\}$

在下列情形中，$N$ 和 $U_i$ $(i=1,2,\dots )$ 是相互独立的同分布随机变量，取非负整数值。

2. 对于一个正整数 $n$，我们定义一个随机变量 $Y_n=Y_n(U_1,U_2,\dots )={\sum }_{i=1}^n{U}_i$。证明 ${\phi }_{Y_n}(s)={\phi }_N(s{)}^n$。

3. 我们定义一个随机变量 $W=W(N,Y_1,Y_2,\dots )={\sum }_{n=1}^{\infty }{Y}_{n}I(N=n)$。 其中，

$$I(N=n)=\{\begin{array}{ll}1& \text{如果 }N=n\\ 0& \text{如果 }N\ne n\end{array}$$

证明 ${\phi }_W(s)={\phi }_N({\phi }_N(s))$。

（提示：$\mathrm{Pr}\{W=k\}={\sum }_{n=1}^{\infty }\mathrm{Pr}\{Y_n=k\}\mathrm{Pr}\{N=n\}$ 对于一个正整数 $k$）

4. 对于 $\mathrm{Pr}\{N=k\}=q^k(1-q)$, $(0<q<1)$，计算 $E\{N\}$ 和 $E\{W\}$。

---

Question 12

Suppose that the maximum score of the global alignment of the two sequences, $x=x_1,\dots ,x_m$ and $y=y_1,\dots ,y_n$, is calculated by a dynamic programming using the following iterations (A).

$$\begin{array}{rl}M(i,j)& =\max [M(i-1,j-1),X(i-1,j-1),Y(i-1,j-1)]+s(x_i,y_j),\\ X(i,j)& =\max [M(i-1,j)-d,X(i-1,j)-e],\\ Y(i,j)& =\max [M(i,j-1)-d,Y(i,j-1)-e].\end{array}\text{\hspace{1em}(A)}$$

Here we assume that $d>0$, $e>0$ and that $s(x_i,y_j)$ is the score of alignment of $x_i$ and $y_j$.

We also assume that the same score of $g(k)$ is given to any gap of length $k$.

Answer the following problems.

1. Show the general form of $g(k)$.

2. In order to get the maximum score of the alignment as $\max [M(m,n),X(m,n),Y(m,n)]$ after iterations using (A) for $i=1,\dots ,m$ and $j=1,\dots ,n$, answer what initial values should be assigned to the following variables.

   • $X(i,0)$ for $i=1,\dots ,m$
   • $Y(0,j)$ for $j=1,\dots ,n$

   You may suppose that

   $$\begin{array}{rl}M(0,0)& =0,\\ X(0,0)& =Y(0,0)=-\infty ,\\ M(i,0)& =Y(i,0)=-\infty (i=1,\dots ,m),\\ M(0,j)& =X(0,j)=-\infty (j=1,\dots ,n).\end{array}$$

3. For the alignment of biological sequences, usually we set $d > e$. Describe the reason briefly. 4. In order to treat the score of long gaps more accurately, let us consider alignments using the following iterations. Show the general form of the gap score of length $k$, when $d_2 > d_1$, $e_2 > e_1$ holds. Note that classification on the value of $k$ is necessary.

\begin{aligned}

M(i, j) &= \max[M(i-1, j-1), X_1(i-1, j-1), Y_1(i-1, j-1),X_2(i-1, j-1), Y_2(i-1, j-1)] + s(x_i, y_j), \

X_1(i, j) &= \max[M(i-1, j) - d_1, X_1(i-1, j) - e_1], \

Y_1(i, j) &= \max[M(i, j-1) - d_1, Y_1(i, j-1) - e_1], \

X_2(i, j) &= \max[M(i-1, j) - d_2, X_2(i-1, j) - e_2], \

Y_2(i, j) &= \max[M(i, j-1) - d_2, Y_2(i, j-1) - e_2].

\end{aligned}

--- 假设通过使用以下迭代 (A) 计算两个序列 $x = x_1, \ldots, x_m$ 和 $y = y_1, \ldots, y_n$ 的全局比对的最大得分。

\begin{aligned}

M(i, j) &= \max[M(i-1, j-1), X(i-1, j-1), Y(i-1, j-1)] + s(x_i, y_j), \

X(i, j) &= \max[M(i-1, j) - d, X(i-1, j) - e], \

Y(i, j) &= \max[M(i, j-1) - d, Y(i, j-1) - e].

\end{aligned} \tag{A}

这里我们假设 $d > 0$，$e > 0$ 并且 $s(x_i, y_j)$ 是 $x_i$ 和 $y_j$ 的比对得分。 我们还假设对于任意长度为 $k$ 的间隙给出了相同的得分 $g(k)$。 回答以下问题。 1. 展示 $g(k)$ 的一般形式。 2. 为了在使用 (A) 迭代后获得最大比对得分 $\max[M(m, n), X(m, n), Y(m, n)]$，回答应为以下变量分配什么初始值。 - $X(i, 0)$ 对于 $i = 1, \ldots, m$ - $Y(0, j)$ 对于 $j = 1, \ldots, n$ 你可以假设

\begin{aligned}

M(0, 0) &= 0, \

X(0, 0) &= Y(0, 0) = -\infty, \

M(i, 0) &= Y(i, 0) = -\infty \quad (i = 1, \ldots, m), \

M(0, j) &= X(0, j) = -\infty \quad (j = 1, \ldots, n).

\end{aligned}

3. 对于生物序列的比对，通常我们设置 $d > e$。简要描述原因。 4. 为了更准确地处理长间隙的得分，让我们考虑使用以下迭代进行比对。展示当 $d_2 > d_1$，$e_2 > e_1$ 时长度为 $k$ 的间隙得分的一般形式。注意对 $k$ 值的分类是必要的。

\begin{aligned}

M(i, j) &= \max[M(i-1, j-1), X_1(i-1, j-1), Y_1(i-1, j-1), X_2(i-1, j-1), Y_2(i-1, j-1)] + s(x_i, y_j), \

X_1(i, j) &= \max[M(i-1, j) - d_1, X_1(i-1, j) - e_1], \

Y_1(i, j) &= \max[M(i, j-1) - d_1, Y_1(i, j-1) - e_1], \

X_2(i, j) &= \max[M(i-1, j) - d_2, X_2(i-1, j) - e_2], \

Y_2(i, j) &= \max[M(i, j-1) - d_2, Y_2(i, j-1) - e_2].

\end{aligned}