2004 S

219,203pages on
this wiki
Add New Page
Discuss this page0 Share

1. (24%) Give an asymptotic upper bound for T(n) in each of the following recurrences. Make your bound as tight as possible, and justify your answers.

(a) T(n)=2T(\lfloor \frac{n}{2}\rfloor+17)+n, T(17)=1
(b) T(n)=2T(\lfloor \frac{n}{2}\rfloor)+2nlogn, T(2)=4
(c) T(n)=T(\lfloor \frac{n}{2}\rfloor)+T(\sqrt n)+n, T(1)=1, T(2)=2
(d) T(n)=\sum_{i=1}^{n}\lceil{log \frac{n}{i}}\rceil.

2. (10%) Design an algorithm to compute the union of two given sets, both of size O(n). The sets are given as arrays of numbers. The output should be an array of distinct elements that form the union of the sets. No element should appear more than once. The worst-case running time of the algorithm should be O(nlogn).

3. (6%) Design an algorithm to identify the connected components of an arbitrary undirected graph. What is the running time of your algorithm?

4. (10%) Suppose G is a connected undirected graph with weighted edges. Let e_{min} be one edge of G with the minimum weight. Prove that there exists a minimum spanning tree for G with e_{min} as a tree edge.

5. (10%) The chromatic number γ(G) of an undirected graph G is defined as the minimum number of colors required for coloring all vertices of G such that no adjacent vertices get the same color. Let d_{max}(G) be the maximum degree of any vertex in G. It can be proved that γ(G)≤d_{max}(G)+1 for any undirected graph G.

(a) Give an example for which γ(G) is strictly less than d_{max}(G)+1.
(b) Give an example for which γ(G) is equal to d_{max}(G)+1.

6. (6%) Consider the following heuristic to solve the vertex-cover problem. Repeatedly select a vertex of highest degree, and remove all of its incident edges. Give an example to show that the heuristic does not have a ratio bound of 2.

7. (5%) The original sorting problem is to sort a_1, a_2, ..., a_n into ascending or descending sequence. Construct a decision problem corresponding to the sorting problem.

8. (5%) Describe the two-step procedure to prove that a problem A is NP-complete.

9. (10%) Use the partition problem to prove the NP-completeness of the bin packing problem. The bin packing decision problem: We are given a set of n items, each of size C_i which is a positive integer. We are also given positive integers B and C which are the number of bins and the bin capacity respectively. We are asked to determine whether we can assign items into k bins, 1≤k≤B, such that the sum of C_i's over all items assigned to each bin does not exceed C.

The partition problem: We are given A={a_1, a_2, ..., a_n} in which each a_i is a positive integer. The partition problem is to determine whether there is a subset P such that \sum_{i \in P} a_i=\sum_{i \in A-P} a_i.

10. (4%) The Strassen's remarkable recursive algorithm for multiplying two n*n matrices, which runs in Θ(n^{lg7})=Θ(n^{2.81}) time. However, from the practical point of view, this algorithm is often not the method of choice for matrix multiplication. Express this phenomenon with four reasons.

11. (10%) The knapsack problem is defined as follows: Given positive integers P_1, P_2, ..., P_n, W_1, W_2, ..., W_n and M. Find X_1, X_2, ..., X_n, 0≤X_i≤1 such that \sum_{i=1}^n P_iX_i is maximized subject to \sum_{i=1}^{n} W_iX_i≤M. Given a greedy method to find an optimal solution of the knapsack problem and prove its correctness.

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.

Also on Fandom

Random wikia