# 2000 S

219,606pages on
this wiki

1. (10%)

(a) (6%) Consider the problem of sorting n numbers, design two different algorithms which can solve the sorting problem by the divide-and-conquer strategies.
(b) (4%) What are the time complexities of your algorithms, respectively?

2. (10%) The knapsack problem is defined as follows: Given positive integers $P_1, P_2, ..., P_n, W_1, W_2, ..., W_m$, and M, find $X_1, X_2, ..., X_n$, 0≤$X_i$≤1 such that $\sum P_i X_i$ is maximized subject to $\sum W_i X_i$≤M. Give a greedy method to find an optimal solution of the above problem and prove its correctness.

3. (10%) Explain the followint terms: NP, NP-complete, NP-hard, and randomized algorithms, respectively.

4. (10%) Explain the following terms.

(a) (3%) approximation algorithm
(b) (3%) relative error
(c) (4%) approximation scheme

5. (15%) Let G=(V,E) be an undirected graph, in which each edge e∈E has a weight w(e). Suppose that G is represented by adjacency lists.

(a) (6%) Design an efficient algorithm that constructs an arbitrary spanning tree of G. What's the time complexity of your algorithm?
(b) (9%) Design an efficient algorithm that constructs a spanning tree of G whose largest edge weight is minimum over all spanning trees of G. What is the time complexity of your algorithm?

6. (15%) The following is an algorithm that takes an undirected graph G=(V,E) as input. Let n=|V| and m=|E|. Intially, each vertex v∈V has a weight w(v).

Algorithm test(G)
1. Q <- V; /* Construct a priority queue Q, which contains all vertices v∈V. The weight of each vertex v in Q is w(v).*/
2. While Q≠∅ do
begin
3. u <- Extract-Min(Q) /* Extract the vertex u having the smallest weight from Q. */
5. Decrease-Key(Q, v, w(v)-5) /* Decrease the weight of v in Q by 5 */
end
(a) (5%) How many times will Step 5 be performed?
(b) (5%) Suppose that Q is implemented by an unsorted linear array. What are the total running times of Steps 1, 3, and 5m respectively?
(c) (5%) Suppose that Q is implemented by a binary heap. What are the total running times of Steps 1, 3, and 5, respectively?

7. (10%) Show that the Fourier transform can be solved using the divide-and-conquer strategy.

8. (10%) Suppoer that T is defined over the integers by the relation

T(n)=2T(n-2)+3, T(1)=T(0)=1.
(a) (5%) Give an exact bound for T over even natural numbers, of the form T(n)=2$2^{n/2}$+d
(b) (5%) Show that when n is odd, then T(n)≤c$2^{n/2}$+d, for your choice of c and d in (a).

9. (10%) Suppose you can solve a problem directly in time $n^2$. Suppose in time $n^r$ you can divide (merge also) the problem into two subproblems of size n/s. How small must r be so that it is etter to divide a large problem into subproblems rather than to solve it directly.