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 , and M, find , 0≤≤1 such that is maximized subject to ≤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. */
- 4. for each v∈Adj[u] do /* Adj[u] denotes the adjacency list of u. */
- 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+d
- (b) (5%) Show that when n is odd, then T(n)≤c+d, for your choice of c and d in (a).

9. (10%) Suppose you can solve a problem directly in time . Suppose in time 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.