1. (17%) Answer each of the following questions.

(A) Given an infix expression (a+b)/c*(d-e), please write down the corresponding prefix and postfix expressions.
(B) Given the following binary tree, which corresponds to a Left Child-Right Sibling representation of a general tree. Please draw the input general tree.

(C) Given the following binary search tree (BST), please draw ALL possible tree(s) after deleting the node with key 48.

(D) Assume the pre-order and in-order traversal of a binary tree are ABDECFHGI and EDBAHFCGI, respectively. Please draw the tree, and explain whether or not the tree is unique.
(E) Assume the pre-order and post-order traversal of a binary tree are ABDECFHGI and EDBHFIGCA, respectively. Please draw the tree, and explain whether or not the tree is unique.
(F) A clocked tree is a binary tree in which each node $n_i$ is associated with a non-negative delay, delay($n_i$). The path delay from a root to a node is defined as the summation of delay of all nodes along the path. The longestDelay is defined as the longest path delay among all root-to-leaf paths. Please base on the class definition show on the right to write pseudo codes of function: void longestDelay(node *root, int AccDelay); that computes and stores the longest path delay in the variable “MAX”.

Class definition

class node {
int delay;
treenode *lchild;
treenode *rchild;
}

int MAX;

(A) Prefix: */+abc-de Postfix: ab+c/de-*
(B)

(C)

(D)

(E)

The tree is not unique. (There are 8 binary trees)
(F)

void longestDelay(node *root, int AccDelay)
{
if (root == null) return;

AccDelay += root -> delay;

if (root -> lchild)
longestDelay(root -> lchild, AccDelay);

if (root -> rchild)
longestDelay(root -> rchild, AccDelay);

if (root -> lchild == null && root -> rchild == null)
{
if (MAX < AccDelay)
MAX = AccDelay;
}
}

2. (17%) Answer each of the following questions.

(A) Give a definition for the reflexive transitive closure matrix $A^*$ of a directed graph G.
(B) What does the following function compute?

void Function1(int cost[][MAX_VERTICES], int distance[][MAX_VERTICES], int n)
{
/* cost is the adjacency matrix of some directed graph */
int i, j, k;

for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
distance[i][j] = cost[i][j];

for (k = 0; k < n; k++)
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (distance[i][k] + distance[k][j] < distance[i][j])
distance[i][j] = distance[i][k] + distance[k][j];
}

(C) Prove or disprove that a graph is bipartite only if it contains no cycles of odd length.
(D) What is a topological sort (or topological ordering) of a directed acyclic graph?
(E) Describe a linear time $O(|V| + |E|)$ algorithm for the topological sort of a graph $G=(V,E)$ using the depth first search implementation.

(A)
$\begin{cases} A^*[i,i] = 1\\ A^*[i,j] \text{ if there exist path from i to j, set to 1, else set to 0.} \end{cases}$
(B) All pairs shortest path
(C) 若bipartite有odd length cycle, 將vertex分成$v_1,v_2$兩種。假設起點為$u_1 \in v_1,$ 則終點$u_2 \in v_2$ (因odd length), 此時cycle不存在。Contradiction found.
(D) An order we use in AOV or AOE network to find whether a job needs to be done before another job.
(E) We can use DFS and then output the nodes in a descendant order from the finish time, that will be a topological sort.

3. (17%) Answer each of the following questions.

(A) Let x and y be integers and m be a positive integer, then x is congruent to y modulo m if (x-y) is divisible by m, we denote this fact as $x \equiv y \, mod \, m.$ Fermat’s Little Theorem states that if p is prime and z is an integer not divisible by p then $z^{p-1} \equiv 1 \, mod \, p.$
Use Fermat’s Little Theorem to compute $3^{302} \, mod \, 5, \, 3^{302} \, mod \, 7, \, 3^{302} \, mod \, 11,$ respectively.
(B) Use the results in (a) and Chinese Remainder Theorem to find $3^{302} \, mod \, 385.$ (Note that $385 = 5 \cdot 7 \cdot 11$)
(C) Solve the simultaneous recurrent relations
$a_n = 3a_{n-1} + 2b_{n-1} \\ b_n = a_{n-1} + 2b_{n-1} \\ \text{with } a_0 = 2, \, b_0 = 1.$

(A) 4, 2, 9.
(B) 9
(C) $a_n = 2 \cdot 4^n, \, b_n = 4^n, \, n \geq 0.$

4. (17%) Answer each of the following questions.

(A) How many different strings can be made by reordering the letters of the word SUCCESS?
(B) Assume that a sequence $\{a_n\}$ satisfies the recurrence relation $a_n = 8a_{n-1} + 10^{n-1}$ and the initial condition $a_1 = 9.$ Use generating functions to find an explicit formula for $a_n.$
(C) Consider the following relations on $\{1,2,3,4\},$

• $R_1$ = {(1,1),(1,2),(2,1),(2,2),(3,4),(4,1),(4,4)},
• $R_2$ = {(1,1),(1,2),(2,1)},
• $R_3$ = {(1,1),(1,2),(1,4),(2,1),(2,2),(3,3),(4,1),(4,4)},
• $R_4$ = {(2,1),(3,1),(3,2),(4,1),(4,2),(4,3)},
• $R_5$ = {(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)},
• $R_6$ = {(3,4)}.

Which of these relations are symmetric? anti-symmetric? transitive?

(A) $\dfrac{7!}{3!2!}$
(B) $a_n = \dfrac{1}{2}(8^n + 10^n), \, n \geq 1.$
(C) Symmetric: $R_2,R_3.$ Anti-symmetric: $R_4,R_5,R_6.$ Transitive: $R_4,R_5,R_6.$

5. (17%) Answer each of the following questions.

(A) Let u and v be two n bit numbers, where we assume that n is a power of 2 for simplicity. Clearly, multiplying u and v straightforwardly requires $O(n^2)$ steps.
(a) Please design a divide-and-conquer approach to compute the product of u and v in $O(n^{log_23})$ time.
(b) Explain why the time complexity of your divide-and-conquer approch is $O(n^{log_23}).$
(B) Determine whether the following statements are correct or not and also justify your answers. No points are given for answers without justification.
(a) The Cook’s theorem states that if the SAT (Satisfiability) problem is in NP, then P = NP.
(b) If we want to prove that a decision problem X is NP-complete, it is enough to reduce X to the SAT problem.
(c) For an NP-complete problem, we need to take exponential time to solve this problem for all kinds of inputs.

(A)
(a) Let $u = u_1u_2…u_n \text{ and } v = v_1v_2…v_n \to u_L = u_1u_2…u_{\frac{n}{2}-1}, \, u_R = u_{\frac{n}{2}}u_{\frac{n}{2}+1}…u_n, \, v_L = v_1v_2…v_{\frac{n}{2}-1}, \text{ and } v_R = v_{\frac{n}{2}}v_{\frac{n}{2}+1}…v_n.$
Step 1: $A = u_L \times v_L$
Step 2: $B = u_R \times v_R$
Step 3: $C = u_L \times v_R + u_R \times v_L$
Step 4: Put A, B, and C in the right position and add them to get the result.
(b) Let $T(n)$ be the time to compute $n \text{ bits} \times n \text{ bits},$ then $T(n) = 3T(\dfrac{n}{2}) + O(n),$ so the time complexity is $O(n^{lg3}).$
(B) (a) F (b) F (c) F

6. (15%) Answer each of the following questions.

(A) The following algorithm takes an n by n matrix A(1:n,1:n) as input, does LU-decomposition and stores the results in the same array A(1:n,1:n), where L is a unit lower triangular matrix (the diagonal elements are all 1s, and the elements above the diagonals are all 0s) and U is an upper triangular matrix (the elements below the diagonals are all 0s). We further assume that a given matrix can be LU-decomposed in our case.

for i = 1,2,...,n-1
for k = i+1,...,n
t = -A(k,i)/A(i,i);
for j = i+1,...,n
A(k,j) = A(k,j) + t*A(i,j);
endfor
A(k,i) = -t;
endfor
endfor

Given a 3 by 3 matrix as stated below as an input
$A = \begin{bmatrix} 1 & 1 & -1\\ 2 & 4 & -1\\ -1 & -3 & 3 \end{bmatrix}$
What are the contents of A after implementing the algorithm? (Show integer parts only).
(B) Let $n \geq m$ be positive integers and let r be a nonnegative integers. The following algorithm will compute gcd(n,m), the greatest common divisor of n and m.

while (m > 0) do
{r = n mod m; n = m; m = r;}
Return n

Given n = 13923 and m = 13056 as input, find the output of n.

(A)
$\begin{bmatrix} 1 & 1 & -1\\ 2 & 2 & 1\\ -1 & -1 & 3 \end{bmatrix}$
(B) 51

### 4 留言

1. #### aaa

嗨，第一題(f)小題的程式碼是不是有誤？因為第7行if statement的條件是「只有」當root的兩個child為null，若root還有左右child，recursion就無法繼續拜訪下去了，所以是否將裡面12和15行兩個判斷式和其中的遞迴式移出第7行的if statement並放在AccDelay+=root->value下方，讓只有當current node為leaf時才更新MAX，可以討論看看嗎？

• 文章作者的留言

#### mt

對誒～原本的的確有bug！像你這樣改就可以了喔～感謝！

2. #### leo

想問
第四小題的B小題
原先是想說是
An=An-1 +10^(n-1)
因為題目說初始條件是A1
是否代表A0不存在

• 文章作者的留言

#### mt

我想這題他一開始給a1而且也沒有用到a0所以自然就不會去在意a0是什麼了～