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
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 */
(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)=22^{n/2}+d
(b) (5%) Show that when n is odd, then T(n)≤c2^{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.

Ad blocker interference detected!

Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.