### 一、Data Structures (50%)

1. (20%)

Given a red-black tree in the following figure.

After one node with value 778 is inserted, the resulting red-black tree is shown as follows.

(a) Please describe the operation procedures for this insertion.
(b) Please indicate the color and value of node A and node B, respectively.

(a) 略
(b) node A: black, 614. node B: red, 419.

2. (10%) Given the expression, (x+y)*w+u/(v+x*w)+z, Please show the content in the stack after the operand v is read in postfix transformation.

3. (20%)

(a) Please finish the lost code for the choose function in the following Dijkstra shortest path implementation for a graph without negative-weight edges.

$$程式碼請看原檔$$

(b) In a directed graph without a cycle of negative length but with a negative-length edge, we can implement Bellman-Ford algorithm as follows to compute shortest paths. Please fill in the lost code.

$$程式碼請看原檔$$

(a)

.wp-block-code{border:0;padding:0}.wp-block-code>div{overflow:auto}.shcb-language{border:0;clip:rect(1px,1px,1px,1px);-webkit-clip-path:inset(50%);clip-path:inset(50%);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px;word-wrap:normal;word-break:normal}.hljs{box-sizing:border-box}.hljs.shcb-code-table{display:table;width:100%}.hljs.shcb-code-table>.shcb-loc{color:inherit;display:table-row;width:100%}.hljs.shcb-code-table .shcb-loc>span{display:table-cell}.wp-block-code code.hljs:not(.shcb-wrap-lines){white-space:pre}.wp-block-code code.hljs.shcb-wrap-lines{white-space:pre-wrap}.hljs.shcb-line-numbers{border-spacing:0;counter-reset:line}.hljs.shcb-line-numbers>.shcb-loc{counter-increment:line}.hljs.shcb-line-numbers .shcb-loc>span{padding-left:.75em}.hljs.shcb-line-numbers .shcb-loc::before{border-right:1px solid #ddd;content:counter(line);display:table-cell;padding:0 .75em;text-align:right;-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;white-space:nowrap;width:1%}for (i = 0; i < n; i++)
{
if (distance[i] < min && !found[i])
{
min = distance[i];
minpos = i;
}
}
Code language: C++ (cpp)

(b)

for (int i = 0; i < n; i++)
for (int u = 0; u < n; u++)
Code language: C++ (cpp)

### 二、Algorithms (50%)

1. (10%) Prove or disprove: The single-source shortest paths problem can be solved in linear time in directed acyclic graphs.

(1) 找Topological sort.
(2) 從sort的順序由前到後作Bellman-Ford algorithm的Relax function.

2. (15%) The matrix-chain multiplication problem can be stated as follows: Given a chain $(A_1, \, A_2,…, \, A_n)$ of $n$ matrices, where for $i = 1, \, 2,…, \, n,$ matrix $A_i$ has dimension $p_{i-1} \times p_i,$ fully parenthesize the product $A_1A_2…A_n$ in a way that minimizes the number of scalar multiplications. Suppose that you have 6 matrices: $A_1$ has dimension $30 \times 35, \, A_2$ has dimension $35 \times 15, A_3$ has dimension $15 \times 5, \, A_4$ has dimension $5 \times 10, \, A_5$ has dimension $10 \times 20, \, A_6$ has dimension $20 \times 30.$ Please calculate the minimum number of scalar multiplications.

3. (10%) Give asymptotic upper and lower bounds for $T(n) = 2T(\dfrac{n}{4}) + \sqrt{n}.$ Assume that $T(n)$ is constant for $n \leq 2.$ Make your bounds as tight as possible.

4. (15%) Consider the problem of finding the 5-vector $x = (x_i)$ that satisfies

$$\begin{pmatrix} 1 & -1 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & -1\\ 0 & 1 & 0 & 0 & -1\\ -1 & 0 & 1 & 0 & 0\\ -1 & 0 & 0 & 1 & 0\\ 0 & 0 & -1 & 1 & 0\\ 0 & 0 & -1 & 0 & 1\\ 0 & 0 & 0 & -1 & 1\\ \end{pmatrix} \begin{pmatrix} x_1\\ x_2\\ x_3\\ x_4\\ x_5 \end{pmatrix} \leq \begin{pmatrix} 0\\ -1\\ 1\\ 5\\ -4\\ -1\\ -3\\ -3 \end{pmatrix}$$

Determine whether there exists a solution or there is no solution.