1. (17%) Answer the following questions.

(A) (4%) Prove or disprove whether the two graphs in each subproblem are isomorphic. No point will be given without a formal proof.

(B) (4%) Prove that if $n \in Z^+$ and $n \geq 3,$ then $\prod_{i=2}^n (1 – i^{-2}) = \dfrac{n + 1}{2n}.$
(C) (4%) How many $n < 801, n \in Z^+$ are not divisible by 2, 3, 4, 5, 6, 8, and 10?
(D) (5%) Define $p(x),q(x),$ and $r(x)$ as follows:
$p(x): x^2 – 26x + 120 = 0 \\ q(x): x \text{ is even} \\ r(x): x < 0$
Determine the truth or falsity of the following statements, for the universe of integers. For a false statement, give a counter example.
(a) $\forall x [q(x) \to p(x)]$
(b) $\exists x [q(x) \to p(x)]$
(c) $\exists x [p(x) \to (q(x) \land r(x))]$
(d) $\forall x [\neg q(x) \to \neg p(x)]$
(e) $\forall x [(p(x) \lor q(x)) \to r(x)]$

(A) (a) Two graphs are isomorphic (b) Two graphs are not isomorphic
(B)
$(1 – \dfrac{1}{2^2})(1 – \dfrac{1}{3^2})…(1 – \dfrac{1}{n^2}) = \dfrac{(2 + 1)(2 – 1)}{2^2} \dfrac{(3 + 1)(3 – 1)}{3^2} … \dfrac{(n + 1)(n – 1)}{n^2} = \dfrac{[3 \cdot 4 \cdots (n + 1)][1 \cdot 2 \cdots (n – 1)]}{(2 \cdot 3 \cdots n)^2} = \dfrac{(n + 1)!(n – 1)!}{2(n!)(n!)} = \dfrac{n + 1}{2n}$
(C) 214
(D) (a) F (b) T (c) T (d) T (e) F

2. (17%) Answer the following questions.

(A) (5%) Solve the following recurrence:
$$G_0 = 1, \, G_1 = 2, \, G_k = 5G_{k-1} + 6G_{k-2} \text{ for } k \geq 2.$$
(B) (4%) In a 10-sided polygon,
(i) How many diagonals are there?
(ii) Suppose that no three diagonals meet at one point. How many intersections will the diagonals form?
(C) (4%) How many positive integer solutions (x, y, z) for the following inequality?
$$x + y + z \leq 100$$
(D) (4%) Find the greatest common divisor of 41537 and 248419.

(A) $G_k = \dfrac{1}{7} [4 \times (-1)^k + 3 \times 6^k], \text{ for } k \geq 0.$
(B) (i) 35 (ii) $\binom{10}{4}$
(C) 161700
(D) 73

3. (17%) Answer the following questions.

(A) Consider the infix expression (A/(B-C+D))*C and answer the following two questions:
(a) (3%) Which of the following is the expression tree of the given expression?

(b) (4%) Write down the equivalent postfix expression.
(B) Consider using arrays as the underlying representations of binary trees. Answer the following questions.
(a) (4%) Insert a set of keys 8, 29, 14, 16, 31, 19, 13 in this order into an initially empty max heap H. Show the content of the array that stores H.
(b) (3%) Insert a set of keys 27, 3, 15, 2, 30 into an initially empty binary search tree T. Show the content of the array that stores T.
(c) (3%) Treat H as a priority queue, pop two keys from it, and then insert the two keys into T. Show the content of the array that stores T again.

(A) (a) 2 (b) ABC-D+/C*
(B)
(a)

(b)

(c)

4. (17%) Answer the following questions.

(A) (2%) Please choose an answer that best completes the following sentence: The number of comparisons required to find an element in a hash table with $N$ buckets, of which $M$ are full,
(a) is approximately $log_2M.$
(b) is approximately $log_2N.$
(c) is usually only slightly less than $N.$
(d) may be large if $M$ is only slightly less than $N.$
(B) (9%)
(a) How many different binary trees can be made from three nodes that contain the key values 1, 2, and 3? Explain why.
(b) How many different binary search trees can be made from three nodes that contain the key values 1, 2, and 3? Explain why.
(c) Color the nodes in the following tree so that it is a red-black tree.

(C) (6%)
(a) Which of the following graphs are bipartite?
(b) Which of the following graphs are biconnected?
(c) What are the real-world applications that would use the biconnected graph? Please give an example.

(A) D
(B) (a) 30 (b) 5
(c)

(C) (a) a, b, d (b) c (c) Network services would use the biconnected graph. When building a network, we don’t want the entire system to shut down with only one node failure.

5. (17%) Answer the following questions.

(A) (9%) Consider the following C program of a recursive function:

void f(int n)
{
int i;

if (n > 1) {
for (i = 1; i <= n; i++) {
printf("Computer Science.\n");
}
f(n/2);
f(n/2);
}
}

(a) How many lines does the program print if we call f(1024)?
(b) Write a recurrence relation for the time complexity.
(c) How many lines, as a function of n in $\Theta (\cdot)$ form, does the program print? Assume n is a power of 2.
(B) (6%) The following code block is an implementation of Floyd’s algorithm for finding all-pairs shortest paths. Initially, dist[i][j] is the length of the directed edge from vertex i and vertex j if it exists, and is infinity otherwise. Please write down the missing code for (a) and (b).

for (k = 1; k <= N; k++)
for (i = 1; i <= N; i++)
for (j = 1; j <= N; j++)
dist[i][j] = min((a), (b));

(C) (2%) Please describe the maximum-flow problem.

(A) (a) 10240 (b) $T(n) = 2T(\dfrac{n}{2}) + O(n)$ (c) $\Theta (nlogn)$
(B) (a) dist[i][j] (b) dist[i][k] + dist[k][j]
(C) Given a graph with its capacity of every edges. We need to find the maximum flow from the source to the sink.

6. (15%) Answer the following questions.

(A) (10%) Let A(1:n,1:n) be a positive definite matrix. The following algorithm takes a positive definite matrix A, as input and decomposes A into the product of L and $L^t$ (the transpose of matrix L), where L is a lower triangular matrix stored in the diagonal and lower part of A.

for j = 1,2,...,n
{
t = A(j,j);

for r = 1,2,...,j-1
{ t = t - A(j,r) * A(j,r); }

A(j,j) = sqrt(t);

for i = j+1,j+2,...,n
{
s = A(i,j);

for r = 1,2,...,j-1
{ s = s - A(i,r) * A(j,r); }

A(i,j) = s / A(j,j);
}
}

Give the following matrix A(1:3,1:3) as input
$A = \begin{bmatrix} 9 & 3 & -3\\ 3 & 17 & 3\\ -3 & 3 & 27 \end{bmatrix}$
What is the result of A after running the algorithm? (Show only the integer part)
(B) (5%) Let a and n be positive integers with $1 < a < n$ and gcd(a,n) = 1, that is, they are relatively prime. The order of $a \, mod \, n$ is the smallest positive integer r such that $a^r \equiv 1 (mod \, n),$ we denote $r = ord_n(a).$ For example, $ord_4(3) = 2.$
(a) What is $ord_{11}(3)?$
(b) What is $ord_{31}(3)?$

(A)
$\begin{bmatrix} 3 & 1 & -1\\ 1 & 4 & 1\\ -1 & 1 & 5 \end{bmatrix}$
(B) (a) 5 (b) 30

### 6 留言

1. #### andy

Insert a set of keys 8, 29, 14, 16, 31, 19, 13 in this order into an initially empty max heap H. Show the content of the array that stores H.
想請問這題要怎麼知道應該要使用 top-down的方法解題，而不是使用 bottom-up
謝謝~

• 文章作者的留言

#### mt

因為這題是給你很多keys然後要你依序插入至空heap，所以一定是用top down。
bottom up的話題目一開始會給你一個二元樹請你調整為heap，但這題沒有。
希望這樣有解決你的問題，加油啦～

2. #### TT

你好，請問6-A-b 是用什麼方法求出30的呢

• 文章作者的留言

#### mt

6B都是先用費馬小定理，然後再確認他們的因數就可以囉！
像(a)就是找10的因數(b)就是找30的因數。

3. #### QQ

想請問6(a)的output上面三個是怎麼跑出來的, 我trace一次是一個下三角的matrix,跑出來的數值跟你一樣,但我不會跑出A[1][2],A[1][3],A[2][3]的數值

• 文章作者的留言

#### mt

這題出來應該會是L放在左下角（包含對角線）然後L^T放在右上角。