1. (8%) Find the formula $S_n$ which satisfies $S_n = -S_{n-1} + 6S_{n-2} \text{ for } n \geq 2,$ so that $S_0 = 7$ and $S_1 = 4.$

2. (9%) Prove that every tree with a vertex of degree k has at least k leaves.

$T(V,E), \, n = |E|$ 且leaves有 $l$ 個
$k = 1$ 時，trivial
$k \geq 2$ 時，assume $l \leq k – 1$

$m \geq l + k + 2(n-l-1) \\ = l + k + 2n – 2l – 2 \\ = 2n + (k-1) – l – 1 \geq 2n + l – l – 1 \\ = 2n – 1$

3. (10%) Determine whether each of the following statements is true or false. Justify your answers.

(a) The propositions $(p \to q) \to r$ and $p \to (q) \to r$ are logically equivalent.
(b) The proposition $(p \land (q \to \neg p)) \to \neg q$ is a tautology.
(c) The argument form is valid:
$$p \to r \\ p \lor q \\ \neg q \\ \therefore r$$
(d) If $A = \{1,2,3\} \text{ and } B = \{1,3,4\},$ then $(1,4) \in P(A \times B).$ ($P(S)$ is the power set of a set $S; \, A \times B$ is the Cartesian product of the two sets $A$ and $B.$)
(e) For all integers $a,b,c \text{ with } c \neq 0,$ if $ac | bc, \text{ then } a | b.$

4. (7%) Answer the following questions.

(a) Give a recursive definition with initial condition(s) to calculate the sequence $a_n = n! (mod \, m),$ where $n,m$ are positive integers.
(b) The Fibonacci numbers are defined by $f_0 = 0, \, f_1 = 1, \text{ and } f_n = f_{n-1} + f_{n-2} \text{ for } n \geq 2.$ Show that $f_1^2 + f_2^2 +…+ f_n^2 = f_nf_{n+1}$ when $n$ is a positive integer.

(a) $a_n = na_{n-1} (mod \, m), \, a_1 = 1.$
(b)
When $n = 1, \, f_1^2 = f_1f_2$ is true
Assume the statement is true for all $n \leq k$
When $n = k + 1, \, f_1^2 + f_2^2 +…+ f_k^2 + f_{k+1}^2 = [f_kf_{k+1}] + f_{k+1}^2 = [f_kf_{k+1}] + [f_k + f_{k-1}]^2 = [f_kf_{k+1}] + [f_{k+1}]^2 = [f_kf_{k+1}] + [f_{k+1}f_{k+1}] = f_{k+1} [f_k + f_{k+1}] = f_{k+1}f_{k+2}.$

5. (5%) Assume you are the system designer for the CS website and want to keep news records into the system. Please analyze the requirements and choose the most suitable storage mechanism and indexing structure from the following candidates.

You should specify the indexing keys for the selections and explain the reasons.

6. (12%) Assume you are the system designer for Far Eastern Electronic Toll Collection System and want to keep the distance-based transportation records for customers to check. Please analyze the requirements and choose the most suitable storage mechanism and indexing structure from the following candidates.

You should specify the indexing keys for the selections and explain the reasons.

7. (9%) Answer the following questions.

(a) A sorting algorithm is said to be stable if equal keys remain in the same relative order in the output as they are in the initial array. For quick sort, merge sort, bubble sort, insertion sort, selection sort, and heap sort, which sorting algorithms are stable?
(b) For quick sort, merge sort, bubble sort, insertion sort, selection sort, and heap sort, which sorting algorithms have the best-case time complexity in $O(n)?$

(a) merge sort, bubble sort, insertion sort.
(b) bubble sort, insertion sort.

8. (8%) Answer the following questions.

(a) What is the number of hash functions that can be used to assign positions to $n$ items in a table of $m$ positions (for $n \leq m$)?
(b) Following (a), what is the number of perfect hash functions?

9. (7%) Answer the following questions, where multiple selections are allowed.

(a) Which one is the running time complexity for the fractional knapsack problem, where a store has $n$ items? (A) $O(nlogn)$ (B) $O(n^2)$ (C) $O(n^2 logn)$ (D) $O(n^3)$.
(b) Which one is the running time complexity for the general 0-1 knapsack problem? (A) polynomial (B) exponential (C) NP-complete (D) none of above.

10. (8%) Let $B_n$ denote the number of binary trees of $n$ nodes and let $H_n$ denote the number of different binary trees of height $h.$ Write down the recurrence equations of $B_n$ and $H_n$ respectively.

$B_n = \sum_{i=0}^{n-1} B_iB_{n-1-i}, \, n \geq 2. B_0 = B_1 = 1. \\ H_n = H_{n-1}H_{n-1} + 2H_{n-1}(\sum_{i=0}^{h-2} H_i), \, n \geq 2. H_0 = 1, H_1 = 3.$

11. (12%) Given a connected, undirected graph $G=(V,E)$ with a weight function $w: E \to R^+,$ a bottleneck spanning tree $T$ of $G$ is defined to be a spanning tree of $G$ whose largest edge weight is minimum over all spanning trees of $G.$ Moreover, the weight of the maximum-weight edge of $T$ is called the value of the bottleneck spanning tree.

(a) Either prove that the following statement is true or give a counterexample to show that it is false: Any bottleneck spanning tree is also a minimum spanning tree.
(b) Either prove that the following statement is true or give a counterexample to show that it is false: Any minimum spanning tree is also a bottleneck spanning tree.
(c) Give an $O(|V| + |E|)$ time algorithm to solve the following problem: Given a graph $G$ and a positive integer $k,$ determine whether the value of the bottleneck spanning tree is at most $k.$

12. (5%) The degree-constrained spanning tree problem is defined as follows: Given a graph $G=(V,E)$ and a positive integer $k,$ does $G$ contain a spanning tree $T$ such that all vertices in $T$ have degree at most $k?$ Either give a polynomial time algorithm to solve the degree-constrained spanning tree problem, or prove that this problem is NP-hard.

### 2 留言

1. #### TNF

請問第五第六題
想說因為B tree的資料搜尋是O(logn) 且新聞與第六題的用戶資訊量大
可能要儲存在外部儲存裝置
所以我兩題都選的是B tree
第五題我覺得網站上都是新聞標題
key可以根據新聞名稱下去搜尋
第六題則是根據用戶名稱搜尋
不知道這樣的想法可不可以~

• 文章作者的留言

#### mt

可以喔～我感覺還滿合理的！