 可使用計算機，惟僅限不具可程式及多重記憶者
□不可使用計算機 |
| |
| Note: Show your work and write the answer clearly. |
| |
|
| 1. |
Give asymptotically tight bound for each of the following
recurrences. (15%) |
| |
(a) |
 |
| |
(b) |
 |
| |
(c) |
 |
| |
|
|
| 2. |
Let 
and 
be constants, and let f(n) be a nonnegative function defined on exact powers
of b. A function g(n) is defined over exact powers of b by: (10%) |
| |
|
| |
(a) |
Suppose the function f(n) is bounded asymptotically as:  ,
give the asymptotically tight bound for the function g(n) in  |
| |
(b) |
Following the problem 2(a), if a function T(n) is defined
as:  ,
then give the asymptotically tight bound for the function T(n) in  |
| |
|
|
| 3. |
Huffman code is an effective technique for compressing data.
If we use the Huffman codes to compress a data file containing only six
characters, i.e., {a, b, c, d, e, f}, where the probabilities of the characters
are 0.45, 0.13, 0.12, 0.16, 0.09, and 0.05, respectively. (10%) |
| |
(a) |
Construct a binary tree corresponding to the optimal Huffman
codes. |
| |
(b) |
If the character c and f are encoded as 100 and 1100, what
are the characters d and e encoded? |
| |
|
|
| 4. |
Given the following graph, |
| |
|
| |
(a) |
Determine the total number of spanning trees. (7%) |
| |
(b) |
Simply describe an algorithm for finding the minimum spanning
tree and use the algorithm to find the minimum spanning tree of the given
graph. (10%) |
| |
|
|
| 5. |
Let 
denote the number of different binary trees with n nodes, which can be defined
as follows: |
| |
|
| |
and  .
Determine the number of different binary trees with 4 nodes. (10%) |
| |
|
|
| 6. |
For the following three data points  ,
namely (0, 0), (1, 1), (2, 3), the Lagrange's formula for data interpolation
is defined as: |
| |
|
| |
Calculate A(0.5) and A(1.5). (10%) |
| |
|
|
| 7. |
For each of the following statements, determine True or False:
(16%) |
| |
(a) |
The algorithm for finding the longest common subsequence (LCS)
is an example of a dynamic programming algorithm. |
| |
(b) |
Quicksort is an unstable sorting algorithm, while Heapsort
is a stable sorting algorithm. |
| |
(c) |
The problem of determining if a graph G has an Euler tour
is an NP-complete problem. |
| |
(d) |
The algorithm for the fast Fourier transform (FFT) is an
example of a divide-and-conquer algorithm. |
| |
(e) |
The Bellman-Ford algorithm can be used to find the single-source
shortest paths of a graph, even if the graph has negative weights. |
| |
(f) |
To show that the clique problem is NP-complete, one must
show that the vertex-cover problem reduces to the clique problem. |
| |
(g) |
The tower of Hanoi problem is a P problem which is solvable
in polynomial time. |
| |
(h) |
The 3-coloring problem is an NP-complete problem. |
| |
|
|
| 8. |
For the directed graph specified below: (12%)
G = (V, E),
V(G) = {a, b, c, d},
E(G) = {(a, b), (a, c), (b, d), (c, d), (b, a), (d, c)}. |
| |
(a) |
Find the adjacency matrix. |
| |
(b) |
Determine the graph  ,
the transpose of the graph G. |
| |
(c) |
Find the transitive closure. |
| |
|
|
|
---END---
|
