105清大資工計科[參考解答]

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{equation}
\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}
\end{equation}
$
(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

---

試題(pdf)：連結

有任何問題，或想要完整解釋的，歡迎在下方留言唷！