2019

Question 7

To determine the order of $n(\ge 3)$ elements (different natural numbers) $a_1,\dots ,a_n$, we generate a binary tree starting from the root node by repeating the following step:

• At each node, if the order of all elements has been determined, let the node be a leaf and label it with the order of all elements. Otherwise, select a pair of elements $a_i,a_j(i<j)$ whose order has not yet been determined, and compare them. If $a_i<a_j$, go to the left child node; otherwise, go to the right child node.

We call such a binary tree a decision tree. A decision tree shows how a sorting algorithm compares elements.

Answer the following questions:

1. When $n$ is fixed, among all paths from the root to leaves in all decision trees, describe a shortest path and a longest path.
2. Prove that in any decision tree, any order of all elements appears in one leaf but does not appear in different leaves.
3. Let $h$ denote the height of a decision tree. Prove $cn\log n\le h$ for a constant $c$.

---

为了确定 $n(\ge 3)$ 个元素（不同的自然数）$a_1,\dots ,a_n$ 的顺序，我们通过重复以下步骤生成一棵二叉树：

• 在每个节点，如果所有元素的顺序已经确定，则让该节点成为叶子并标记为所有元素的顺序。否则，选择一对顺序尚未确定的元素 $a_i,a_j(i<j)$，并比较它们。如果 $a_i<a_j$，则转到左子节点；否则，转到右子节点。

我们将这种二叉树称为决策树。决策树显示了排序算法如何比较元素。

回答以下问题：

1. 当 $n$ 固定时，在所有决策树中从根到叶的所有路径中，描述最短路径和最长路径。
2. 证明在任何决策树中，所有元素的任何顺序出现在一个叶子中，但不会出现在不同的叶子中。
3. 令 $h$ 表示决策树的高度。证明 $cn\log n\le h$ 对于某个常数 $c$。

---

Question 8

If an $n\times n$ real symmetric matrix $\mathbf{A}$ satisfies condition ${\mathbf{v}}^T\mathbf{Av}>0$ for any non-zero $n$-dimensional real column vector $\mathbf{v}$, $\mathbf{A}$ is called a positive definite matrix (${\mathbf{v}}^T$ represents the transpose of $\mathbf{v}$). Answer the following questions.

1. Show the diagonal elements $A_{kk}(k=1,\dots ,n)$ of real positive definite matrix $\mathbf{A}$ are positive.
2. Show the eigenvalues of real symmetric matrix $\mathbf{A}$ are real.
3. Show the eigenvalues of positive definite matrix $\mathbf{A}$ are positive.
4. Let $S=\{\mathbf{v}\in {\mathbb{R}}^n\mid {\mathbf{v}}^T\mathbf{v}=1\}$ be the set of non-zero $n$-dimensional real column vectors $\mathbf{v}$ of unit length. Show ${\lambda }_1={\max }_{\mathbf{v}\in S}{\mathbf{v}}^T\mathbf{Av}$ is the largest eigenvalue of positive definite matrix $\mathbf{A}$.
5. Suppose the eigenvectors of positive definite matrix $\mathbf{A}$ are all different. Furthermore, suppose you know the largest eigenvalue ${\lambda }_1$ and its associated eigenvector ${\mathbf{v}}_1$. Explain how to compute the second largest eigenvalue ${\lambda }_2$ using ${\lambda }_1$ and ${\mathbf{v}}_1$ without computing the third largest or smaller eigenvalues.

---

如果一个 $n\times n$ 实对称矩阵 $\mathbf{A}$ 满足对于任意非零 $n$ 维实列向量 $\mathbf{v}$，有 ${\mathbf{v}}^T\mathbf{Av}>0$，则称 $\mathbf{A}$ 为正定矩阵 (${\mathbf{v}}^T$ 表示 $\mathbf{v}$ 的转置)。回答以下问题。

1. 证明实正定矩阵 $\mathbf{A}$ 的对角元素 $A_{kk}(k=1,\dots ,n)$ 是正的。
2. 证明实对称矩阵 $\mathbf{A}$ 的特征值是实数。
3. 证明正定矩阵 $\mathbf{A}$ 的特征值是正的。
4. 设 $S=\{\mathbf{v}\in {\mathbb{R}}^n\mid {\mathbf{v}}^T\mathbf{v}=1\}$ 为非零 $n$ 维实列向量 $\mathbf{v}$ 的单位长度集合。证明 ${\lambda }_1={\max }_{\mathbf{v}\in S}{\mathbf{v}}^T\mathbf{Av}$ 是正定矩阵 $\mathbf{A}$ 的最大特征值。
5. 假设正定矩阵 $\mathbf{A}$ 的特征向量都不相同。此外，假设你知道最大特征值 ${\lambda }_1$ 及其关联的特征向量 ${\mathbf{v}}_1$。解释如何在不计算第三大或更小的特征值的情况下，使用 ${\lambda }_1$ 和 ${\mathbf{v}}_1$ 计算第二大特征值 ${\lambda }_2$。

---

Question 9

We wish to sort an array of integers, $a_1,a_2,\dots ,a_{2^t}$ ($n$ is a natural number) in ascending order. Assume that loading/storing an integer and comparing two integers take unit time.

1. Let $n=1$. Show an algorithm that sorts the array, $a_1,a_2$.
2. Given two sorted arrays, $x_1,x_2,\dots ,x_p$ and $y_1,y_2,\dots ,y_q$, show an algorithm that merges the two arrays and calculates the sorted array $z_1,z_2,\dots ,z_{p+q}$ in $O(p+q)$ time.
3. Let $T(2^n)$ be the running time for sorting an array, $a_1,a_2,\dots ,a_{2^n}$. We sort the first half of the array in $T(2^{n-1})$ time, and sort the second half similarly. Then we obtain the full sorted array by merging the first and second half of the arrays using the algorithm we used in (2). Derive the recurrence for $T(2^n)$ in terms of $T(2^{n-1})$ and $n$, and then derive an explicit formula for $T(2^n)$.
4. Notice that in (2), the first half of the sorted array, $z_1,z_2,\dots ,z_{\lceil \frac{p+q}{2}\rceil }$, contains the first $t$ elements of $x_1,x_2,\dots ,x_p$ and the first $\lceil \frac{p+q}{2}\rceil -t$ elements of $y_1,y_2,\dots ,y_q$. Given two sorted arrays, $x_1,x_2,\dots ,x_p$ and $y_1,y_2,\dots ,y_q$, show an algorithm that finds $t$ in $O(\log (p+q))$ time. For simplicity, you may assume that $a_1,a_2,\dots ,a_{2^t}$ are distinct numbers.
5. Assume that we have $O(2^n)$ CPU cores, and assume that we can ignore the synchronization cost between CPU cores. Show the running time complexity of a parallel merge sort algorithm that uses the technique in (4).

---

我们希望按升序排序一个整数数组 $a_1,a_2,\dots ,a_{2^t}$ ($n$ 是一个自然数)。假设加载/存储一个整数和比较两个整数所需的时间是单位时间。

1. 令 $n=1$。展示一个排序数组 $a_1,a_2$ 的算法。
2. 给定两个已排序的数组 $x_1,x_2,\dots ,x_p$ 和 $y_1,y_2,\dots ,y_q$，展示一个算法，将这两个数组合并并计算排序后的数组 $z_1,z_2,\dots ,z_{p+q}$，时间复杂度为 $O(p+q)$。
3. 设 $T(2^n)$ 为排序数组 $a_1,a_2,\dots ,a_{2^n}$ 的运行时间。我们在 $T(2^{n-1})$ 时间内对数组的前半部分进行排序，并以类似方式对后半部分进行排序。然后我们通过使用 (2) 中的算法合并数组的前半部分和后半部分来获得完全排序的数组。推导 $T(2^n)$ 的递推关系，并得出 $T(2^n)$ 的显式公式。
4. 注意在 (2) 中，排序后的数组的前半部分 $z_1,z_2,\dots ,z_{\lceil \frac{p+q}{2}\rceil }$ 包含了 $x_1,x_2,\dots ,x_p$ 的前 $t$ 个元素和 $y_1,y_2,\dots ,y_q$ 的前 $\lceil \frac{p+q}{2}\rceil -t$ 个元素。给定两个已排序的数组 $x_1,x_2,\dots ,x_p$ 和 $y_1,y_2,\dots ,y_q$，展示一个在 $O(\log (p+q))$ 时间内找到 $t$ 的算法。为了简单起见，你可以假设 $a_1,a_2,\dots ,a_{2^t}$ 是不同的数字。
5. 假设我们有 $O(2^n)$ 个 CPU 核，并假设可以忽略 CPU 核之间的同步成本。展示使用 (4) 中技术的并行归并排序算法的运行时间复杂度。

---

Question 10

Answer the following questions regarding undirected graphs. A simple graph is a graph that does not contain any multi-edges or self-loops. A walk is defined as a connected sequence of edges.

1. Prove that, for any graph $\mathbf{G}$, the number of nodes whose degree is odd is always even.
2. Write the adjacency matrix $\mathbf{A}$ of the following graph, and show that the number of walks of length 2 between nodes 1 and 4 is equal to the $(1,4)$-element of ${\mathbf{A}}^2$.

  1 -- 2
  | \  |
  |  \ |
  3 -- 4

3. Prove that, for any simple graph $\mathbf{G}$ with some adjacency matrix $\mathbf{A}$, the number of walks of length $k$ between nodes $i,j$ is equal to the $(i,j)$ element of ${\mathbf{A}}^k$.
4. Assume that a simple connected graph $\mathbf{G}$ has two or more nodes. Prove that $\mathbf{G}$ has at least two nodes with identical degree.

---

回答以下关于无向图的问题。简单图是指不包含任何多重边或自环的图。行走被定义为边的连接序列。

1. 证明对于任何图 $\mathbf{G}$，度数为奇数的节点数总是偶数。
2. 写出以下图的邻接矩阵 $\mathbf{A}$，并证明节点 1 和 4 之间长度为 2 的路径数等于 ${\mathbf{A}}^2$ 的 $(1,4)$ 元素。

  1 -- 2
  | \  |
  |  \ |
  3 -- 4

3. 证明对于任何具有某个邻接矩阵 $\mathbf{A}$ 的简单图 $\mathbf{G}$，节点 $i,j$ 之间长度为 $k$ 的路径数等于 ${\mathbf{A}}^k$ 的 $(i,j)$ 元素。
4. 假设一个简单连通图 $\mathbf{G}$ 有两个或更多节点。证明 $\mathbf{G}$ 至少有两个度数相同的节点。

---

Question 11

Suppose that a sequence $\mathbf{x}=x_1{x}_2\cdots x_n$ is generated from a first-order stationary Markov model that has initial probabilities $\{{\pi }_k\}$ and transition probabilities $\{a_{ij}\}$ as follows.

Initial probabilities:

$$P(x_1=k)={\pi }_k,\text{for }k\in \{0,1\}$$

Transition probabilities:

$$P(x_t=j\mid x_{t-1}=i)=a_{ij},\text{for }i,j\in \{0,1\},t=2,\dots ,n$$

Note that $P(X)$ is the probability that $X$ is true, and $P(X\mid Y)$ is the conditional probability that $X$ is true when $Y$ is true.

Answer the following questions:

1. Assume $n=4$. Show the probability that $101$ is included as a continuous substring in $\mathbf{x}$. Show also the probability that $111$ is included as a continuous substring in $\mathbf{x}$.
2. Assume $n=4$. Show the expected number of 1s in $\mathbf{x}$ when $101$ is included as a continuous substring in $\mathbf{x}$.

In the following questions, use the following transition probabilities.

$$a_{00}=0.8,a_{01}=0.2,a_{10}=0.3,a_{11}=0.7$$

3. Calculate the expected proportion of 1s in $\mathbf{x}$ when $n\to \infty$.
4. Suppose that $n=2m$ ($m$ is a positive integer). When every two letters of $\mathbf{x}=x_1{x}_2\cdots x_{2m}$ is converted to a letter of $\mathbf{y}=y_1\cdots y_m$ using the following rule, calculate the expected proportions of $a,c,g,t$ in $\mathbf{y}$ when $m\to \infty$.

$$y_i=\{\begin{array}{ll}a,& \text{if }{x}_{2i-1}=0\text{ and }{x}_{2i}=0,\\ c,& \text{if }{x}_{2i-1}=0\text{ and }{x}_{2i}=1,\\ g,& \text{if }{x}_{2i-1}=1\text{ and }{x}_{2i}=0,\\ t,& \text{if }{x}_{2i-1}=1\text{ and }{x}_{2i}=1,\end{array}\text{for }i=1,\dots ,m$$

---

假设序列 $\mathbf{x}=x_1{x}_2\cdots x_n$ 是从一个一阶平稳马尔可夫模型生成的，该模型具有如下初始概率 $\{{\pi }_k\}$ 和转移概率 $\{a_{ij}\}$。

初始概率：

$$P(x_1=k)={\pi }_k,\text{对于 }k\in \{0,1\}$$

转移概率：

$$P(x_t=j\mid x_{t-1}=i)=a_{ij},\text{对于 }i,j\in \{0,1\},t=2,\dots ,n$$

注意 $P(X)$ 是 $X$ 为真的概率，$P(X\mid Y)$ 是 $X$ 在 $Y$ 为真时的条件概率。

回答以下问题：

1. 假设 $n=4$。证明在 $\mathbf{x}$ 中包含 $101$ 作为连续子串的概率。也证明在 $\mathbf{x}$ 中包含 $111$ 作为连续子串的概率。
2. 假设 $n=4$。证明在 $\mathbf{x}$ 中包含 $101$ 作为连续子串时 $\mathbf{x}$ 中 1 的期望数量。

在以下问题中，使用以下转移概率。

$$a_{00}=0.8,a_{01}=0.2,a_{10}=0.3,a_{11}=0.7$$

3. 计算当 $n\to \infty$ 时 $\mathbf{x}$ 中 1 的期望比例。
4. 假设 $n=2m$ ($m$ 是一个正整数)。当 $\mathbf{x}=x_1{x}_2\cdots x_{2m}$ 的每两个字母转换为 $\mathbf{y}=y_1\cdots y_m$ 的一个字母时，使用以下规则，计算 $\mathbf{y}$ 中 $a,c,g,t$ 的期望比例，当 $m\to \infty$ 时。

$$y_i=\{\begin{array}{ll}a,& \text{如果 }{x}_{2i-1}=0\text{ 且 }{x}_{2i}=0,\\ c,& \text{如果 }{x}_{2i-1}=0\text{ 且 }{x}_{2i}=1,\\ g,& \text{如果 }{x}_{2i-1}=1\text{ 且 }{x}_{2i}=0,\\ t,& \text{如果 }{x}_{2i-1}=1\text{ 且 }{x}_{2i}=1,\end{array}\text{对于 }i=1,\dots ,m$$

---

Question 12

Let $s_1,\dots ,s_n$ be a sequence of (possibly negative) integers. We wish to find $x$ and $y$ such that $1\le x\le y\le n$ and maximize

$$\sum _{k=x}^y{s}_k.$$

As a first step, we calculate

$$t_i=\underset{1\le j\le i}{\max }\left[\sum _{k=j}^i{s}_k\right].$$

1. Write a formula for $t_1$.
2. Write a formula for $t_{i+1}$ in terms of $t_i$.
3. Write an algorithm that calculates the following value and outputs a pair $(x,y)$ satisfying the requirements:

$$\underset{1\le x\le y\le n}{\max }\left[\sum _{k=x}^y{s}_k\right].$$

The running time of your algorithm should be $O(n)$. Assume that operations on two integers take unit time: $a+b$, $\max (a,b)$.

---

设 $s_1,\dots ,s_n$ 为一个（可能为负数）的整数序列。我们希望找到 $x$ 和 $y$ 使得 $1\le x\le y\le n$ 并且使

$$\sum _{k=x}^y{s}_k$$

最大化。

第一步，我们计算

$$t_i=\underset{1\le j\le i}{\max }\left[\sum _{k=j}^i{s}_k\right].$$

1. 写出 $t_1$ 的公式。
2. 写出 $t_{i+1}$ 的公式。
3. 写出一个算法计算以下值并输出满足要求的 $(x,y)$ 对：

$$\underset{1\le x\le y\le n}{\max }\left[\sum _{k=x}^y{s}_k\right].$$

算法的运行时间应为 $O(n)$。假设对两个整数的操作需要单位时间：$a+b$, $\max (a,b)$。