2019S2

Problem 1

Assume that we have a sequence of 2-dimensional vertices $\mathbf{V}=[{\mathbf{v}}^1,{\mathbf{v}}^2,\dots ,{\mathbf{v}}^n](n\ge 3),{\mathbf{v}}^i=(v_{xi}^i,v_{yi}^i)$ in an orthogonal coordinate system. Let $\mathbf{M}$ be the polygon surrounded by the edges constructed by connecting the adjacent vertices ${\mathbf{v}}^i,{\mathbf{v}}^{i+1}(1\le i\le n-1)$ as well as the last and first vertices ${\mathbf{v}}^n,{\mathbf{v}}^1$. The polygon $\mathbf{M}$ may not be convex. Assume that the edges meet only at their endpoints, and that ${\mathbf{v}}^i\ne {\mathbf{v}}^j$ holds for all $i,j(1\le i<j\le n)$. Assume also that no three vertices among ${\mathbf{v}}^1,{\mathbf{v}}^2,\dots ,{\mathbf{v}}^n$ lie on the same line. Answer the following questions.

1. Explain a method to judge whether the orientation of the vertex sequence is clockwise or counterclockwise. We call the orientation of a vertex sequence $[(1,0),(0,1),(-1,0),(0,-1)]$ counterclockwise.

2. Give the area of the polygon $\mathbf{M}$ as an expression of $\mathbf{V}$‘s coordinates ${\mathbf{v}}^i=(v_{xi}^i,v_{yi}^i)(1\le i\le n)$.

3. Assume that a new vertex $\mathbf{p}=(p_x,p_y)$ is given. Explain a method to judge whether the vertex $\mathbf{p}$ is inside the polygon $\mathbf{M}$ or not. You need not consider the case where the vertex $\mathbf{p}$ is on the boundary of the polygon $\mathbf{M}$.

4. Consider a process of dividing the interior of the polygon $\mathbf{M}$ into triangles by adding edges between some of the vertices of the polygon $\mathbf{M}$ so that the new edges are inside the polygon $\mathbf{M}$, and do not intersect. Give the number of triangles as an expression of $n$. Prove that the expression is valid for any $n\ge 3$.

5. Assume that two vertex sequences $\mathbf{V}$ and $\mathbf{U}$ with equal length are given. We apply a linear transformation $\mathbf{A}$ to $\mathbf{V}$ so that the distance between the resulting $\tilde{\mathbf{V}}$ and $\mathbf{U}$ is minimum. Here, the distance between $\tilde{\mathbf{V}}$ and $\mathbf{U}$ is defined as ${\sum }_{i=1}^n(({\tilde{\mathbf{v}}}_{xi}^i-{\mathbf{u}}_{xi}^i{)}^2+({\tilde{\mathbf{v}}}_{yi}^i-{\mathbf{u}}_{yi}^i{)}^2)$, where $\mathbf{A}({\mathbf{v}}^i)=({\tilde{\mathbf{v}}}_{xi}^i,{\tilde{\mathbf{v}}}_{yi}^i),{\mathbf{u}}^i=(u_{xi}^i,u_{yi}^i)(1\le i\le n)$. Give such a linear transformation $\mathbf{A}$ as an expression of $\mathbf{V}$ and $\mathbf{U}$‘s coordinates ${\mathbf{v}}^i=(v_{xi}^i,v_{yi}^i),{\mathbf{u}}^i=(u_{xi}^i,u_{yi}^i)(1\le i\le n)$.

---

假设我们有一个二维顶点序列 $\mathbf{V}=[{\mathbf{v}}^1,{\mathbf{v}}^2,\dots ,{\mathbf{v}}^n](n\ge 3),{\mathbf{v}}^i=(v_{xi}^i,v_{yi}^i)$ 在一个正交坐标系中。 设 $\mathbf{M}$ 为多边形，由连接相邻顶点 ${\mathbf{v}}^i,{\mathbf{v}}^{i+1}(1\le i\le n-1)$ 的边以及最后一个和第一个顶点 ${\mathbf{v}}^n,{\mathbf{v}}^1$ 围成的多边形。 多边形 $\mathbf{M}$ 可能不是凸的。 假设边缘仅在端点相交，并且 ${\mathbf{v}}^i\ne {\mathbf{v}}^j$ 对于所有 $i,j(1\le i<j\le n)$ 成立。 还假设没有三个顶点 ${\mathbf{v}}^1,{\mathbf{v}}^2,\dots ,{\mathbf{v}}^n$ 在同一条直线上。 回答以下问题。

1. 解释一种判断顶点序列的方向是顺时针还是逆时针的方法。 我们称顶点序列 $[(1,0),(0,1),(-1,0),(0,-1)]$ 的方向为逆时针。

2. 以 $\mathbf{V}$ 的坐标 ${\mathbf{v}}^i=(v_{xi}^i,v_{yi}^i)(1\le i\le n)$ 表示多边形 $\mathbf{M}$ 的面积。

3. 假设给定一个新顶点 $\mathbf{p}=(p_x,p_y)$。 解释一种判断顶点 $\mathbf{p}$ 是否在多边形 $\mathbf{M}$ 内的方法。 您不需要考虑顶点 $\mathbf{p}$ 在多边形 $\mathbf{M}$ 边界上的情况。

4. 考虑一种通过在多边形 $\mathbf{M}$ 的一些顶点之间添加边，将多边形 $\mathbf{M}$ 的内部分割成三角形的过程，使得新边在多边形 $\mathbf{M}$ 内部，并且不相交。 以 $n$ 的表达式给出三角形的数量。 证明该表达式对任何 $n\ge 3$ 都有效。

5. 假设给定两个长度相等的顶点序列 $\mathbf{V}$ 和 $\mathbf{U}$。 我们应用线性变换 $\mathbf{A}$ 到 $\mathbf{V}$ 使得得到的 $\tilde{\mathbf{V}}$ 和 $\mathbf{U}$ 之间的距离最小。 这里，$\tilde{\mathbf{V}}$ 和 $\mathbf{U}$ 之间的距离定义为 ${\sum }_{i=1}^n(({\tilde{\mathbf{v}}}_{xi}^i-{\mathbf{u}}_{xi}^i{)}^2+({\tilde{\mathbf{v}}}_{yi}^i-{\mathbf{u}}_{yi}^i{)}^2)$，其中 $\mathbf{A}({\mathbf{v}}^i)=({\tilde{\mathbf{v}}}_{xi}^i,{\tilde{\mathbf{v}}}_{yi}^i),{\mathbf{u}}^i=(u_{xi}^i,u_{yi}^i)(1\le i\le n)$。给出这样的线性变换 $\mathbf{A}$ 作为 $\mathbf{V}$ 和 $\mathbf{U}$ 坐标的表达式 ${\mathbf{v}}^i=(v_{xi}^i,v_{yi}^i),{\mathbf{u}}^i=(u_{xi}^i,u_{yi}^i)(1\le i\le n)$。

---

Problem 2

The probability density function of the normal distribution with mean $\mu \in \mathbb{R}$ and variance $\nu >0$ is given by

$$f(x)=\frac{1}{\sqrt{2\pi \nu }}\exp \left(-\frac{(x-\mu {)}^2}{2\nu }\right).$$

Let $X_1,X_2,\dots ,X_n$ be random variables that independently follow this distribution, where $n$ is an integer no less than 2. Consider the estimation of $(\mu ,\nu )$ based on loss function $L(\mu ,\nu )$ given by

$$L(\mu ,\nu )=\sum _{i=1}^n\left(\frac{(X_i-\mu {)}^2}{\nu }+\log \nu \right)+\frac{\lambda }{\nu },$$

where log is the natural logarithm and the regularization parameter $\lambda$ is a positive real number. Let $(\hat{\mu },\hat{\nu })$ be the value minimizing the loss function $L(\mu ,\nu )$. Answer the following questions.

1. Express $(\hat{\mu },\hat{\nu })$ using $n,X_1,X_2,\dots ,X_n,\text{ and }\lambda$.

2. Obtain the expectations of $\hat{\mu }$ and $\hat{\nu }$.

3. Let $n=3$ and consider an orthogonal matrix $A$ and a random variable $\mathbf{Y}=(Y_1,Y_2,Y_3{)}^{\top }$ that are expressed as

$$A=\left(\begin{array}{ccc}\frac{1}{\sqrt{3}}& \frac{1}{\sqrt{3}}& \frac{1}{\sqrt{3}}\\ \frac{1}{\sqrt{2}}& 0& a\\ \frac{1}{\sqrt{6}}& b& c\end{array}\right),\mathbf{Y}=\left(\begin{array}{c}{Y}_1\\ Y_2\\ Y_3\end{array}\right)=A\left(\begin{array}{c}{X}_1\\ X_2\\ X_3\end{array}\right),$$

for some real numbers $a,b\text{ and }c$.

(i) Obtain the values of $a,b\text{ and }c$.

(ii) Express ${\sum }_{i=1}^3{X}_i$ and ${\sum }_{i=1}^3{X}_i^2$ using $Y_1,Y_2\text{ and }{Y}_3$.

(iii) Show that $\hat{\nu }\text{ and }\hat{\mu }$ are independent of each other. You may use the following facts.

• $\mathbf{Y}$ follows a trivariate normal distribution with mean vector ${\mu }_{\mathbf{Y}}=A(\mu ,\mu ,\mu {)}^{\top }$ and covariance matrix ${\mathbf{V}}_{\mathbf{Y}}=\nu A{A}^{\top }$.
• The probability density function of $\mathbf{Y}$ for $\mathbf{y}=(y_1,y_2,y_3{)}^{\top }\in {\mathbb{R}}^3$ is given by

$$g(\mathbf{y})=\frac{1}{\sqrt{(2\pi {)}^3\det {\mathbf{V}}_{\mathbf{Y}}}}\exp \left(-\frac{1}{2}(\mathbf{y}-{\mu }_{\mathbf{Y}}{)}^{\top }{\mathbf{V}}_{\mathbf{Y}}^{-1}(\mathbf{y}-{\mu }_{\mathbf{Y}})\right),$$

where $\det {\mathbf{V}}_{\mathbf{Y}}$ is the determinant of ${\mathbf{V}}_{\mathbf{Y}}$.

---

平均值 $\mu \in \mathbb{R}$ 和方差 $\nu >0$ 的正态分布的概率密度函数由下式给出

$$f(x)=\frac{1}{\sqrt{2\pi \nu }}\exp \left(-\frac{(x-\mu {)}^2}{2\nu }\right).$$

设 $X_1,X_2,\dots ,X_n$ 为独立服从此分布的随机变量，其中 $n$ 为不小于 2 的整数。考虑基于损失函数 $L(\mu ,\nu )$ 的 $(\mu ,\nu )$ 估计，定义损失函数 $L(\mu ,\nu )$ 为

$$L(\mu ,\nu )=\sum _{i=1}^n\left(\frac{(X_i-\mu {)}^2}{\nu }+\log \nu \right)+\frac{\lambda }{\nu },$$

其中对数为自然对数，正则化参数 $\lambda$ 为正实数。令 $(\hat{\mu },\hat{\nu })$ 为使损失函数 $L(\mu ,\nu )$ 最小的值。回答以下问题。

1. 使用 $n,X_1,X_2,\dots ,X_n,\text{ 和 }\lambda$ 表示 $(\hat{\mu },\hat{\nu })$。

2. 求 $\hat{\mu }$ 和 $\hat{\nu }$ 的期望。

3. 设 $n=3$ 并考虑一个正交矩阵 $A$ 和一个随机变量 $\mathbf{Y}=(Y_1,Y_2,Y_3{)}^{\top }$，它们表示为

$$A=\left(\begin{array}{ccc}\frac{1}{\sqrt{3}}& \frac{1}{\sqrt{3}}& \frac{1}{\sqrt{3}}\\ \frac{1}{\sqrt{2}}& 0& a\\ \frac{1}{\sqrt{6}}& b& c\end{array}\right),\mathbf{Y}=\left(\begin{array}{c}{Y}_1\\ Y_2\\ Y_3\end{array}\right)=A\left(\begin{array}{c}{X}_1\\ X_2\\ X_3\end{array}\right),$$

其中 $a,b\text{ 和 }c$ 为一些实数。

(i) 求 $a,b\text{ 和 }c$ 的值。

(ii) 使用 $Y_1,Y_2\text{ 和 }{Y}_3$ 表示 ${\sum }_{i=1}^3{X}_i$ 和 ${\sum }_{i=1}^3{X}_i^2$。

(iii) 证明 $\hat{\nu }\text{ 和 }\hat{\mu }$ 彼此独立。你可以使用以下事实。

• $\mathbf{Y}$ 服从三元正态分布，均值向量 ${\mu }_{\mathbf{Y}}=A(\mu ,\mu ,\mu {)}^{\top }$ 和协方差矩阵 ${\mathbf{V}}_{\mathbf{Y}}=\nu A{A}^{\top }$。
• 对于 $\mathbf{y}=(y_1,y_2,y_3{)}^{\top }\in {\mathbb{R}}^3$ 的 $\mathbf{Y}$ 的概率密度函数由下式给出

$$g(\mathbf{y})=\frac{1}{\sqrt{(2\pi {)}^3\det {\mathbf{V}}_{\mathbf{Y}}}}\exp \left(-\frac{1}{2}(\mathbf{y}-{\mu }_{\mathbf{Y}}{)}^{\top }{\mathbf{V}}_{\mathbf{Y}}^{-1}(\mathbf{y}-{\mu }_{\mathbf{Y}})\right),$$

其中 $\det {\mathbf{V}}_{\mathbf{Y}}$ 是 ${\mathbf{V}}_{\mathbf{Y}}$ 的行列式。

---

Problem 3

Let $x$ be a non-negative real number, and let $f$ be a recursive function (i.e., computable function) from natural numbers (i.e., non-negative integers) to natural numbers. The expression $f\downarrow x$ means that $f$ is total and $|x-f(n)/2^n|<1/2^n$ holds for any natural number $n$. A non-negative real number $x$ is called computable if there exists a recursive function $f$ that satisfies $f\downarrow x$. Answer the following questions.

1. Show that $\sqrt{2}$ is computable.

2. Show that there exists a non-negative real number that is not computable.

3. Show that if there exists a recursive function $f$ that satisfies $f\downarrow x$, then there exists a recursive function $g$ that satisfies $g\downarrow x^2$.

4. For a unary function parameter $\phi$, a function $h$ is called a $\phi$-recursive function if $h$ can be defined by function composition, minimization and primitive recursion with $\phi$ as a basic function in addition to constants $0$ and $1$, addition $(+)$ and projection functions $(p_{\beta }^{\alpha }(n_1,\dots ,n_{\alpha })=n_{\beta },\alpha \text{ and }\beta$ are natural numbers and $1\le \beta \le \alpha )$. The expression $h_f$ denotes the recursive function obtained by replacing $\phi$ with a unary recursive function $f$ in the definition of $h$. The function $H$ from non-negative real numbers to non-negative real numbers is defined as follows.

$$H(x)=\{\begin{array}{ll}0& (x=0)\\ 1& (x>0)\end{array}$$

Show that there exists no $\phi$-recursive function $h$ that satisfies the following condition.

For any $f$ and $x$, $f\downarrow x$ implies $h\downarrow H(x)$.

---

设 $x$ 为非负实数，$f$ 为从自然数（即非负整数）到自然数的递归函数（即可计算函数）。 表达式 $f\downarrow x$ 表示 $f$ 是全函数并且 $|x-f(n)/2^n|<1/2^n$ 对于任意自然数 $n$ 成立。 一个非负实数 $x$ 称为可计算的，如果存在满足 $f\downarrow x$ 的递归函数 $f$。 回答以下问题。

1. 证明 $\sqrt{2}$ 是可计算的。

2. 证明存在不可计算的非负实数。

3. 证明如果存在满足 $f\downarrow x$ 的递归函数 $f$，则存在满足 $g\downarrow x^2$ 的递归函数 $g$。

4. 对于一元函数参数 $\phi$，函数 $h$ 称为 $\phi$-递归函数，如果 $h$ 可以通过函数组合、最小化和基本递归定义，其中 $\phi$ 作为基本函数，另外还包括常数 $0$ 和 $1$，加法 $(+)$ 和投影函数 $(p_{\beta }^{\alpha }(n_1,\dots ,n_{\alpha })=n_{\beta },\alpha \text{ 和 }\beta$ 为自然数且 $1\le \beta \le \alpha )$。表达式 $h_f$ 表示在 $h$ 的定义中用一元递归函数 $f$ 替换 $\phi$ 所得到的递归函数。从非负实数到非负实数的函数 $H$ 定义如下。

$$H(x)=\{\begin{array}{ll}0& (x=0)\\ 1& (x>0)\end{array}$$

证明不存在满足以下条件的 $\phi$-递归函数 $h$。

对于任何 $f$ 和 $x$，$f\downarrow x$ 蕴含 $h\downarrow H(x)$。

---

Problem 4

Consider a microprocessor that processes each instruction in the following four stages.

Stage	Description
Fetch	Fetch an instruction from memory.
Decode	Decode the instruction and read the specified registers.
Execute	Perform ALU or memory operations.
Write	Write the result to the specified register.

Answer the following questions. Assume that the processing time required for each stage is $5\times 10^{-10}$ seconds in questions (1) and (2).

1. Obtain the execution time per instruction on this microprocessor. Also, obtain the throughput of this microprocessor (the number of instructions processed per second). Assume that each instruction always requires the four stages, and the next instruction is fetched only after the four stages are completed.

2. The pipelining method is used to increase the throughput of a microprocessor. Explain how the above four stages are executed by the pipelining method. Also, obtain the throughput of this microprocessor under the assumption that the pipelining method works ideally.

3. If pipeline hazards occur, the pipelining method may not work ideally. Explain the following three types of pipeline hazards.

   • Structural hazard
   • Data hazard
   • Control hazard

4. The loop unrolling method is used to avoid pipeline hazards to some extent. Explain what is the loop unrolling method, and how it avoids pipeline hazards.

---

考虑一个微处理器，该处理器在以下四个阶段处理每条指令。

阶段	描述
取指令	从存储器中取出一条指令。
解码	解码指令并读取指定的寄存器。
执行	执行 ALU 或内存操作。
写回	将结果写入指定的寄存器。

回答以下问题。在问题 (1) 和 (2) 中，假设每个阶段所需的处理时间为 $5\times 10^{-10}$ 秒。

1. 求该微处理器每条指令的执行时间。 另外，求该微处理器的吞吐量（每秒处理的指令数）。假设每条指令始终需要四个阶段，并且只有在四个阶段完成后才取出下一条指令。

2. 流水线方法用于提高微处理器的吞吐量。解释如何通过流水线方法执行上述四个阶段。 另外，假设流水线方法理想工作，求该微处理器的吞吐量。

3. 如果发生流水线阻塞，流水线方法可能无法理想工作。解释以下三种类型的流水线阻塞。

   • 结构性阻塞
   • 数据阻塞
   • 控制阻塞

4. 循环展开方法在一定程度上用于避免流水线阻塞。解释什么是循环展开方法，以及它如何避免流水线阻塞。

---

Problem 5

Suppose that $\mathbf{A}$ is an $n$ dimensional positive-definite real symmetric matrix. Answer the following questions.

1. An $n$ dimensional real lower triangular matrix $\mathbf{L}$ whose diagonal entries are all positive can be expressed in a block form,

$$\mathbf{L}=\left(\begin{array}{cc}{\lambda }_1& 0\\ {\mathbf{\ell }}_1& {\mathbf{L}}^{(1)}\end{array}\right),$$

where ${\lambda }_1$, ${\mathbf{\ell }}_1$, and ${\mathbf{L}}^{(1)}$ are a positive real number, an $n-1$ dimensional real vector, and an $n-1$ dimensional real lower triangular matrix whose diagonal entries are all positive, respectively. Using this expression, reduce the Cholesky decomposition of $\mathbf{A},\mathbf{A}=\mathbf{L}{\mathbf{L}}^{\top }$, to the Cholesky decomposition of an $n-1$ dimensional real symmetric matrix. Here, you need not show that we may assume ${\lambda }_1$ to be a positive real number. You need not show that the obtained $n-1$ dimensional real symmetric matrix is positive definite, either.

2. Using the Cholesky decomposition, construct a direct method to solve a system of linear equations whose coefficient matrix is $\mathbf{A}$.

3. Prove that the $(1,1)$-entry (the entry in the first row and first column) of $\mathbf{A}$ is a positive real number.

4. Using the result of question (1), answer the total number of the four arithmetic operations $(+,-,\times ,/)$ required for the Cholesky decomposition of $\mathbf{A}$ in the form of $c\times n^p$, where $c$ and $p$ are constants. Note that this form means that the obtained number of operations may include an error which becomes relatively negligible when $n\to \infty$. In addition, suppose that the number of the four arithmetic operations required to compute a square root is a constant.

---

假设 $\mathbf{A}$ 是一个 $n$ 维正定实对称矩阵。回答以下问题。

1. 一个 $n$ 维实数下三角矩阵 $\mathbf{L}$ 其对角线元素均为正可以用块形式表示为

$$\mathbf{L}=\left(\begin{array}{cc}{\lambda }_1& 0\\ {\mathbf{\ell }}_1& {\mathbf{L}}^{(1)}\end{array}\right),$$

其中 ${\lambda }_1$，${\mathbf{\ell }}_1$ 和 ${\mathbf{L}}^{(1)}$ 分别为一个正实数、一个 $n-1$ 维实数向量和一个 $n-1$ 维实数下三角矩阵，其对角线元素均为正。使用这个表达式，将 $\mathbf{A}$ 的 Cholesky 分解 $\mathbf{A}=\mathbf{L}{\mathbf{L}}^{\top }$ 约化为一个 $n-1$ 维实对称矩阵的 Cholesky 分解。在这里，你不需要证明我们可以假设 ${\lambda }_1$ 是一个正实数。你也不需要证明得到的 $n-1$ 维实对称矩阵是正定的。

2. 使用 Cholesky 分解，构造一种直接方法来解系数矩阵为 $\mathbf{A}$ 的线性方程组。

3. 证明 $\mathbf{A}$ 的 $(1,1)$-元素（第一行和第一列的元素）是正实数。

4. 使用问题 (1) 的结果，回答 Cholesky 分解 $\mathbf{A}$ 所需的四种算术运算 $(+,-,\times ,/)$ 的总数，以 $c\times n^p$ 的形式，其中 $c$ 和 $p$ 是常数。注意，这种形式意味着获得的运算次数可能包括当 $n\to \infty$ 时变得相对可忽略的误差。此外，假设计算平方根所需的四种算术运算的次数是常数。

---

Problem 6

Consider the following decision problems A, B, and C.

A: A problem to determine whether there exist integers $i,j(1\le i<j\le n)$ such that $s_i+s_j=c$, for a given sorted array of $n$ different integers $S=[s_1,s_2,\dots ,s_n](s_1<s_2<\dots <s_n)$ and a fixed constant $c$.

B: A problem to determine whether there exist integers $i,j,k(1\le i<j<k\le n)$ such that $t_i+t_j+t_k=0$, for a given set of $n$ different integers $T=\{t_1,t_2,\dots ,t_n\}$.

C: A problem to determine whether there exist integers $i,j,k(1\le i<j<k\le n)$ such that three points $(x_i,y_i),(x_j,y_j),(x_k,y_k)\in \mathbf{P}$ are on the same line, for a given set of $n$ different points $\mathbf{P}=\{(x_1,y_1),(x_2,y_2),\dots ,(x_n,y_n)\}$ represented by an orthogonal coordinate system, on the 2-dimensional Euclidean plane.

Answer the following questions.

1. Show an algorithm that solves decision problem A in $O(n)$ time.

2. Show an algorithm that solves decision problem B in $O(n^2)$ time.

3. Suppose that three points $(a,a^3),(b,b^3),(c,c^3)$ represented by an orthogonal coordinate system, on the 2-dimensional Euclidean plane, are on the same line, where

4. $a,b$ and $c$ are different real numbers. Express $c$ using $a$ and $b$.

5. Prove that there exists no algorithm that solves decision problem C in $O(n)$ time under the assumption that there exists no algorithm that solves decision problem B in $O(n)$ time.

---

考虑以下决策问题 A、B 和 C。

A: 解决一个问题，即是否存在整数 $i,j(1\le i<j\le n)$ 使得 $s_i+s_j=c$，对于给定的长度为 $n$ 的不同整数数组 $S=[s_1,s_2,\dots ,s_n](s_1<s_2<\dots <s_n)$ 和一个固定常数 $c$。

B: 解决一个问题，即是否存在整数 $i,j,k(1\le i<j<k\le n)$ 使得 $t_i+t_j+t_k=0$，对于给定的长度为 $n$ 的不同整数集合 $T=\{t_1,t_2,\dots ,t_n\}$。

C: 解决一个问题，即是否存在整数 $i,j,k(1\le i<j<k\le n)$ 使得三个点 $(x_i,y_i),(x_j,y_j),(x_k,y_k)\in \mathbf{P}$ 在同一直线上，对于给定的长度为 $n$ 的不同点集 $\mathbf{P}=\{(x_1,y_1),(x_2,y_2),\dots ,(x_n,y_n)\}$ 由一个正交坐标系表示，在二维欧几里得平面上。

回答以下问题。

1. 给出一个算法，该算法以 $O(n)$ 时间解决决策问题 A。

2. 给出一个算法，该算法以 $O(n^2)$ 时间解决决策问题 B。

3. 假设三个点 $(a,a^3),(b,b^3),(c,c^3)$ 由一个正交坐标系表示，在二维欧几里得平面上，在同一直线上，其中 $a,b$ 和 $c$ 是不同的实数。使用 $a$ 和 $b$ 表示 $c$。

4. 在假设不存在算法以 $O(n)$ 时间解决决策问题 C 的情况下，证明不存在算法以 $O(n)$ 时间解决决策问题 B。