2023

Problem 7

Given a point set, $P=\{{\mathbf{v}}_1,\dots ,{\mathbf{v}}_{\mathbf{n}}\}({\mathbf{v}}_{\mathbf{i}}\in {\mathbb{R}}^2)$, the convex hull, $C_P$, is a convex polygon $\{{\mathbf{v}}_{{\mathbf{x}}_1},{\mathbf{v}}_{{\mathbf{x}}_2},\dots ,{\mathbf{v}}_{{\mathbf{x}}_{\mathbf{m}}}\}(m\le n)$ such that $\{{\mathbf{v}}_{{\mathbf{x}}_1},{\mathbf{v}}_{{\mathbf{x}}_2},\dots ,{\mathbf{v}}_{{\mathbf{x}}_{\mathbf{m}}}\}$ comprises a subset of $P$ arranged in a clockwise order and that all points in $P$ are included in or on the edge of the polygon. Below is an example.

$$P=\{{\mathbf{v}}_1,{\mathbf{v}}_2,{\mathbf{v}}_3,{\mathbf{v}}_4,{\mathbf{v}}_5,{\mathbf{v}}_6,{\mathbf{v}}_7,{\mathbf{v}}_8\}$$ $$C_P=\{{\mathbf{v}}_2,{\mathbf{v}}_5,{\mathbf{v}}_4,{\mathbf{v}}_7,{\mathbf{v}}_6,{\mathbf{v}}_3\}$$

1. The algorithm shown below computes $C_P$ from a given $P$. Show the complexity of line 4-7 in the $O()$ notation. Explain the reason. Arithmetic operations over real numbers have infinite precision and can be computed in a unit time. $\mathrm{cw}(a,b,c)$ returns true only if $\overrightarrow{ab}$ and $\overrightarrow{bc}$ turns clockwise (i.e., the cross product $\overrightarrow{ab}\times \overrightarrow{bc}$ is negative).

   1: Let $s$ be an empty stack. We denote by $s_i$ the $i$-th element from top of $s$.

   2: Take the bottommost point of the leftmost points in $P$, and let it be ${\mathbf{v}}_{\mathbf{s}}$.

   3: Leave out ${\mathbf{v}}_{\mathbf{s}}$ of $P$, sort in order of the slope of the line from ${\mathbf{v}}_{\mathbf{s}}$ to ${\mathbf{v}}_{\mathbf{i}}$. Let the result be $P^{\prime }$.

   4: for $\mathbf{v}$ in $P^{\prime }$:

   5: while the size of $s>1$ and not $\mathrm{cw}(s_2,s_1,v)$:

   6: pop an element from $s$

   7: push $\mathbf{v}$ to $s$

2. Suppose $X=\{x_1,\dots ,x_n\}(x_i\in \mathbb{R})$ is given. Let $y_i=(x_i,x_i^2)$, and we computed the convex hull $C_Y$ for $Y=\{y_1,\dots ,y_n\}(y_i\in {\mathbb{R}}^2)$. Given $C_Y$, prove that the sorted array of $X$ can be computed in linear time in terms of $n$.

3. Prove that the complexity of an algorithm that computes the convex hull of $n$ points (not necessarily the algorithm shown in (1)) is not smaller than the complexity of a sorting algorithm for $n$ elements.

4. Suppose we use a random function that returns true/false at 50% of probability, respectively. Prove that we need to call $r()$ at least ${\log }_{2}n!$ times to output one of all possible permutations of integers from 1 to $n$ with the equal probability.

5. Consider a computation model where the sorting algorithm with the smallest complexity is based on comparison between two numbers. Prove that the complexity of computing a convex hull is intrinsically $\Theta (n\log n)$. Use the Stirling’s approximation formula, $\ln (n!)=n\ln (n)-n+O(\log n)$, if need be.

---

给定一个点集 $P=\{{\mathbf{v}}_1,\dots ,{\mathbf{v}}_{\mathbf{n}}\}({\mathbf{v}}_{\mathbf{i}}\in {\mathbb{R}}^2)$，凸包 $C_P$ 是一个凸多边形 $\{{\mathbf{v}}_{{\mathbf{x}}_1},{\mathbf{v}}_{{\mathbf{x}}_2},\dots ,{\mathbf{v}}_{{\mathbf{x}}_{\mathbf{m}}}\}(m\le n)$，使得 $\{{\mathbf{v}}_{{\mathbf{x}}_1},{\mathbf{v}}_{{\mathbf{x}}_2},\dots ,{\mathbf{v}}_{{\mathbf{x}}_{\mathbf{m}}}\}$ 组成一个按顺时针顺序排列的 $P$ 的子集，并且 $P$ 中的所有点都包含在多边形的边上或边上。以下是一个例子。

$$P=\{{\mathbf{v}}_1,{\mathbf{v}}_2,{\mathbf{v}}_3,{\mathbf{v}}_4,{\mathbf{v}}_5,{\mathbf{v}}_6,{\mathbf{v}}_7,{\mathbf{v}}_8\}$$ $$C_P=\{{\mathbf{v}}_2,{\mathbf{v}}_5,{\mathbf{v}}_4,{\mathbf{v}}_7,{\mathbf{v}}_6,{\mathbf{v}}_3\}$$

1. 下列算法从给定的 $P$ 计算 $C_P$。展示 4-7 行的复杂度（用 $O()$ 表示）。解释原因。实数上的算术运算具有无限精度，可以在单位时间内完成。只有当 $\overrightarrow{ab}$ 和 $\overrightarrow{bc}$ 顺时针旋转时（即，叉积 $\overrightarrow{ab}\times \overrightarrow{bc}$ 为负时），$\mathrm{cw}(a,b,c)$ 才返回真。

   1: 令 $s$ 为一个空栈。我们用 $s_i$ 表示 $s$ 顶部的第 $i$ 个元素。

   2: 取 $P$ 中最左边点的最底部点，记为 ${\mathbf{v}}_{\mathbf{s}}$。

   3: 去掉 $P$ 中的 ${\mathbf{v}}_{\mathbf{s}}$，按从 ${\mathbf{v}}_{\mathbf{s}}$ 到 ${\mathbf{v}}_{\mathbf{i}}$ 的斜率排序。结果记为 $P^{\prime }$。

   4: 对 $P^{\prime }$ 中的每个 $\mathbf{v}$:

   5: 当 $s$ 的大小大于 1 且 $\mathrm{cw}(s_2,s_1,v)$ 不成立时：

   6: 从 $s$ 中弹出一个元素

   7: 将 $\mathbf{v}$ 推入 $s$

2. 假设给定 $X=\{x_1,\dots ,x_n\}(x_i\in \mathbb{R})$。令 $y_i=(x_i,x_i^2)$，我们计算出 $Y=\{y_1,\dots ,y_n\}(y_i\in {\mathbb{R}}^2)$ 的凸包 $C_Y$。给定 $C_Y$，证明 $X$ 的排序数组可以在线性时间内计算。

3. 证明计算 $n$ 个点的凸包（不一定是算法 (1) 中所示的算法）的复杂度不小于排序 $n$ 个元素的算法的复杂度。

4. 假设我们使用一个以 50% 的概率分别返回真/假的随机函数。证明我们至少需要调用 $r()$ ${\log }_{2}n!$ 次才能输出从 1 到 $n$ 的所有可能排列中的一个且概率相等。

5. 考虑一个基于两个数之间比较的最小复杂度排序算法的计算模型。证明计算凸包的复杂度本质上是 $\Theta (n\log n)$。如果需要，使用 Stirling 近似公式 $\ln (n!)=n\ln (n)-n+O(\log n)$。

---

Question 8

(1) Describe the eigenvalues and eigenvectors of the following matrix. ($\lambda$ is a real value.)

$${\mathbf{A}}_{\lambda }=\left(\begin{array}{ccc}\lambda & 1& 1\\ 1& \lambda & 1\\ 1& 1& \lambda \end{array}\right)$$

(2) What is the range of $\lambda$ such that ${\mathbf{A}}_{\lambda }$ is positive semidefinite.

(3) Consider an $n\times n$ symmetric matrix where all diagonal elements are $b$ and all non-diagonal elements are $a$. Show that this matrix is non-singular when $|b|>|(n-1)a|$.

---

(1) 描述下列矩阵的特征值和特征向量。（$\lambda$ 是一个实值。）

$${\mathbf{A}}_{\lambda }=\left(\begin{array}{ccc}\lambda & 1& 1\\ 1& \lambda & 1\\ 1& 1& \lambda \end{array}\right)$$

(2) 使 ${\mathbf{A}}_{\lambda }$ 是半正定矩阵的 $\lambda$ 的范围是什么。

(3) 考虑一个 $n\times n$ 的对称矩阵，其中所有对角线元素是 $b$，所有非对角线元素是 $a$。证明当 $|b|>|(n-1)a|$ 时，这个矩阵是非奇异的。

---

Question 9

Let $G=(V,E)$ be a directed acyclic graph such that $V$ is the set of integers from $1$ to $n(n\ge 3)$. We will consider the following sets of edges for $E$.

$$E_1=\{(1,i),(i,n)\mid i=2,\dots ,n-1\}$$ $$E_2=\{(i,i+1)\mid i=1,\dots ,n-1\}\cup \{(i,i+2)\mid i=1,\dots ,n-2\}$$

1. Consider a bijective function $f$ from $V$ to $V$ such that $f(u)<f(v)$ for any $(u,v)\in E$. For each of $E_1$ and $E_2$, answer the number of all different bijective functions and the rationale.

2. For each of $E_1$ and $E_2$, answer the number of all different paths from $1$ to $n$ (or a recurrence for computing the number), and the rationale.

3. For any directed acyclic graph $G=(V,E)$, design an algorithm that calculates the number of paths from $s$ to $t$ in $O(|V|+|E|)$ time for any $s,t\in V$, and explain the rationale.

---

令 $G=(V,E)$ 为一个有向无环图，其中 $V$ 是从 $1$ 到 $n$ 的整数集合 $(n\ge 3)$。我们将考虑以下边集 $E$。

$$E_1=\{(1,i),(i,n)\mid i=2,\dots ,n-1\}$$ $$E_2=\{(i,i+1)\mid i=1,\dots ,n-1\}\cup \{(i,i+2)\mid i=1,\dots ,n-2\}$$

1. 考虑从 $V$ 到 $V$ 的一个双射函数 $f$ 使得对任何 $(u,v)\in E$，有 $f(u)<f(v)$。对于 $E_1$ 和 $E_2$，回答所有不同双射函数的数量和理由。

2. 对于 $E_1$ 和 $E_2$，回答从 $1$ 到 $n$ 的所有不同路径的数量（或用于计算数量的递推关系），并说明理由。

3. 对于任意有向无环图 $G=(V,E)$，设计一个算法，该算法在 $O(|V|+|E|)$ 时间内计算从 $s$ 到 $t$ 的路径数量（对于任意 $s,t\in V$），并解释理由。

---

Question 10

There are two points $A$, $B$ and $2^n$ data points $P_1,\cdots ,P_{2^n}$ in a 2-dimensional Euclidean plane. Assume that the distance $ϵ$ between $A$ and $B$, and the distances $a_1,\cdots ,a_{2^n}$ between $A$ and the data points are given. The distances $b_1,\cdots ,b_{2^n}$ between $B$ and the data points are not given, but a function $f(P_i,P_j)$ defined below can be used to identify the sign of $b_i-b_j$ for $1\le i<j\le 2^n$.

$$f(P_i,P_j)=\mathrm{sgn}(b_i-b_j)=\{\begin{array}{ll}1& \text{if }{b}_i-b_j>0\\ 0& \text{if }{b}_i-b_j=0\\ -1& \text{if }{b}_i-b_j<0\end{array}$$

Assume that $|a_i-a_j|>ϵ$ for any $a_i,a_j$ $(1\le i\le j\le 2^n)$.

1. Show the pseudo-code of an algorithm to sort $P_1,\cdots ,P_{2^n}$ by ascending order of the distances from $A$ in $O(n{2}^n)$ worst computational time.
2. Explain why the worst computational time of the algorithm shown in (1) is $O(n{2}^n)$.
3. Prove that if $a_i-a_j>2ϵ$ then $b_i>b_j$.
4. When $P_1,\cdots ,P_{2^n}$ are already sorted by ascending order of the distances from $A$, show an algorithm to sort by ascending order of the distances from $B$ that calls function $f$ the minimum number of times, and evaluate that number of times.

---

在二维欧几里得平面上有两个点 $A$ 和 $B$ 以及 $2^n$ 个数据点 $P_1,\cdots ,P_{2^n}$。假设点 $A$ 和 $B$ 之间的距离为 $ϵ$，并且给出了点 $A$ 和数据点之间的距离 $a_1,\cdots ,a_{2^n}$。点 $B$ 和数据点之间的距离 $b_1,\cdots ,b_{2^n}$ 未知，但可以使用以下定义的函数 $f(P_i,P_j)$ 来确定 $b_i-b_j$ 的符号，对于 $1\le i<j\le 2^n$。

$$f(P_i,P_j)=\mathrm{sgn}(b_i-b_j)=\{\begin{array}{ll}1& \text{if }{b}_i-b_j>0\\ 0& \text{if }{b}_i-b_j=0\\ -1& \text{if }{b}_i-b_j<0\end{array}$$

假设对于任何 $a_i,a_j$ $(1\le i\le j\le 2^n)$，$|a_i-a_j|>ϵ$。

1. 给出一个伪代码算法，将 $P_1,\cdots ,P_{2^n}$ 按距离 $A$ 的升序排序，最坏计算时间为 $O(n{2}^n)$。
2. 解释为什么 (1) 中所示算法的最坏计算时间为 $O(n{2}^n)$。
3. 证明如果 $a_i-a_j>2ϵ$ 则 $b_i>b_j$。
4. 当 $P_1,\cdots ,P_{2^n}$ 已经按距离 $A$ 的升序排序时，给出一个算法按距离 $B$ 的升序排序，该算法调用函数 $f$ 的次数最少，并评估调用次数。

---

Question 11

Let $\{x_t|t=0,1,2,\dots \}$ be a random sequence of non-negative integers generated by the following rules.

(i) If $x_t>0$, $x_{t+1}=x_t+1$ with probability $p$, and $x_{t+1}=x_t-1$ with probability $q=(1-p)$.

(ii) If $x_t=0$, $x_{t+1}=0$ with probability 1.

In the following, $p\ne q$ is assumed. Further, we define $u_k^{(T)}$ as the probability that $x_T=0$ at time $t=T$ with initial value $x_0=k$ ($k$: a nonnegative integer). Answer the following questions.

1. Answer the probability that $x_3=2$ given $x_0=1$.
2. Answer the probability that $x_4=0$ given $x_0=2$.
3. Express $u_k^{(T)}$ using $u_{k+1}^{(T-1)}$ and $u_{k-1}^{(T-1)}$ ($k>0$, $T\ge 1$).
4. Let $u_k={\lim }_{T\to \infty }{u}_k^{(T)}$. Derive the equations that the $u_k$s satisfy using (3).
5. Answer the condition for $p$ that the equations of (4) have a solution $u_k$ with ${\lim }_{k\to \infty }{u}_k=0$, as well as the solution $u_k$ (Examine the case: $u_k=z^k$).

---

设 $\{x_t|t=0,1,2,\dots \}$ 为通过以下规则生成的非负整数随机序列。

(i) 如果 $x_t>0$，则 $x_{t+1}=x_t+1$，概率为 $p$；$x_{t+1}=x_t-1$，概率为 $q=(1-p)$。

(ii) 如果 $x_t=0$，则 $x_{t+1}=0$，概率为 1。

在下文中，假设 $p\ne q$。此外，我们定义 $u_k^{(T)}$ 为在初始值 $x_0=k$ ($k$：非负整数) 时，$t=T$ 时 $x_T=0$ 的概率。回答以下问题。

1. 回答在 $x_0=1$ 时 $x_3=2$ 的概率。
2. 回答在 $x_0=2$ 时 $x_4=0$ 的概率。
3. 使用 $u_{k+1}^{(T-1)}$ 和 $u_{k-1}^{(T-1)}$ 表示 $u_k^{(T)}$ ($k>0$, $T\ge 1$)。
4. 令 $u_k={\lim }_{T\to \infty }{u}_k^{(T)}$。推导出 $u_k$ 满足的方程（使用 (3)）。
5. 回答 $p$ 的条件，使得 (4) 中的方程有解 $u_k$，且 ${\lim }_{k\to \infty }{u}_k=0$，以及解 $u_k$（检查情况：$u_k=z^k$）。

---

Question 12

We would like to know the probability that the string $\text{FRED}$ appears in a random protein sequence. Assume the sequence has random independent letters from the protein alphabet $A$, and letter $a\in A$ has probability $p(a)$. Define $Q(i,X)$ to be the probability that $\text{FRED}$ appears in a random sequence of length $i$, given that the sequence ends with $X$, where $X$ is a length-4 string.

1. What is $Q(4,X)$ when $X\ne \text{FRED}$?

2. What is $Q(4,X)$ when $X=\text{FRED}$?

Define $X^{\prime }$ to be $X$ without its final letter. Define $a\cdot X$ to be $X$ with letter $a$ prepended to it. These definitions may be useful to answer the following questions.

3. What is $Q(i+1,X)$, in terms of $Q(i,Y)$, where $Y$ is any length-4 string, when $X\ne \text{FRED}$?

4. What is $Q(i+1,X)$ when $X=\text{FRED}$?

Define $P(X)$ to be the product of the probabilities of the letters in $X$. Define $A^4$ to be the set of all possible length-4 strings. These definitions may be useful to answer the following question.

5. What is the probability that $\text{FRED}$ appears in a random sequence of length $n$, in terms of $Q(n,X)$?

---

我们想知道字符串 $\text{FRED}$ 出现在随机蛋白质序列中的概率。假设序列中的字母是蛋白质字母表 $A$ 中的随机独立字母，并且字母 $a\in A$ 的概率为 $p(a)$。定义 $Q(i,X)$ 为 $\text{FRED}$ 出现在长度为 $i$ 的随机序列中的概率，前提是序列以长度为 4 的字符串 $X$ 结尾。

1. 当 $X\ne \text{FRED}$ 时， $Q(4,X)$ 是多少？

2. 当 $X=\text{FRED}$ 时， $Q(4,X)$ 是多少？

定义 $X^{\prime }$ 为去掉最后一个字母后的 $X$。定义 $a\cdot X$ 为在 $X$ 前添加字母 $a$ 后的 $X$。这些定义可能对回答以下问题有用。

3. 当 $X\ne \text{FRED}$ 时， $Q(i+1,X)$ 以 $Q(i,Y)$ 表示，其中 $Y$ 是任意长度为 4 的字符串？

4. 当 $X=\text{FRED}$ 时， $Q(i+1,X)$ 是多少？

定义 $P(X)$ 为 $X$ 中字母概率的乘积。定义 $A^4$ 为所有可能的长度为 4 的字符串的集合。这些定义可能对回答以下问题有用。

5. 在 $Q(n,X)$ 的基础上，$\text{FRED}$ 出现在长度为 $n$ 的随机序列中的概率是多少？