.
, then 
if and only if 
.
be given
by 
. Then 
,
then any subset of size n+2 from S must contain two elements
that sum to 2n+2.
,
.
.
time where 
is
the number of vertices in the graph.| 92年6月11日 08:30~10:00 電子系資訊組 | 誠實是我們珍視的美德， 我們喜愛「拒絕作弊，堅守正直」的你！ |
| 科目：計算機理論 |
| Part I | ||
| 1. | [20%]True or False. In problems (a)-(j), determine whether the statement is true or false. | |
| (a) | If x is a real number, then |
|
| (b) | . |
|
| (c) | |
|
| (d) | If is ƒ：Ｚ→Ｚ is defined by ƒ (n)=n2+1, then ƒ (n) is one-to-one. | |
| (e) | |
|
| (f) | Every vertex of a tree is a cut-vertex.. | |
| (g) | If , then
if and only if . |
|
| (h) | The set of real numbers between 0 and 1 is not a countably infinite set. | |
| (i) | Let be given
by . Then |
|
| (j) | Every u-v walk in a graph contains a u-v path. | |
| 2. | [10%] Show that if ,
then any subset of size n+2 from S must contain two elements
that sum to 2n+2. |
|
| 3. | [10%] Show that in every tree ,. |
|
| 4. | [10%] Solve the following recurrence relation . |
|
| ============================================================= | ||
| Part II | ||
| 1. | (10%) For each of the following questions, write T for true and F for false. You do not need to provide any reasoning. | |
| (a) | For a sequence of operations to be performed on a data structure, if the ith operation costs i when i is an exact power of 2, and costs 1 otherwise, then the average cost of each operation is 1. | |
| (b) | Whether a graph has any cycle can be determined in linear time. | |
| (c) | If all edge weights of a connected, undirected graph are distinct, then the minimum spanning tree of the graph is unique. | |
| (d) | The transitive closure of a directed graph can be computed
in time where is
the number of vertices in the graph. |
|
| (e) | Any NP-complete problem is also an NP-hard problem. | |
| 2. | (12%) What is the running time T(n) for the following algorithm? | |
| (a) | Merge sort (worst case) | |
| (b) | Randomized quick sort (expected) | |
| (c) | Binary search (worst case) | |
| (d) | Number Selection (worst case) | |
| 3. | (3%) Is the array [ 30 25 7 18 24 8 4 9 12 22 5] a binary max-heap? If it is not a max-heap, then modify it to become a max-heap. | |
| 4. | (10%) We are given a directed graph 
on which each edge  has an
associated value  , which is
a real number in the range 
that represents the reliability of a communication channel form vertex u
to vertex v. We interpret
as the probability that the cannel from u to v will not fail,
and we assume that these probabilities are independent. Give an efficient
algorithm to find the most reliable path between two given vertices. |
|
| 5. | (15%) You have just discovered a breakthrough result in number
theory that will quickly become world-famous, but there is one step left
for you to complete. You need to find a fast algorithm to tell whether a
number X is a perfect power. That is, you want a fast algorithm which, on
an input integer X that is n bits long, finds whether there exist integers
B  2 and e
2 such that X = Be. If so your algorithm should output the values
of B and e. |
|
| (a) | If X = Be is a perfect power, how large can e be? Express your answer as a function of n. | |
| (b) | Suppose that your computer had an O(1)-time operation ROOT(M,r)
that returns the rth root of an integer M. if that root is an integer (and
returns  otherwise). Give an
algorithm to solve the perfect-power problem and analyze its running time. |
|
|
--- END ---
|
||