# 2000 S

*215,687*pages on

this wiki

## 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.

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.