Assignment 2

1. "Greedy Algorithms are used to solve optimization problems." Explain it with an example.
2. An undirected graph G(V, E) contains n ( n > 2 ) nodes named v1 , v2 ,….vn. Two nodes vi , vj are connected if and only if 0 < |i – j| <= 2. Each edge (vi, vj ) is assigned a weight i + j. A sample graph with n = 4 is shown below. What will be the cost of the minimum spanning tree (MST) of such a graph with n nodes? (GATE CS 2011) 

A	1/12(11n^2 – 5n)
B	n^2 – n + 1
C	6n – 11
D	2n+1

3. Create MST by primes and kruskal's algorithm

4. Explain Drawbacks of Dynamic programming and greedy method.

5. Given a chain of  matrices <5,4,6,2,7>  find optimal parenthesization of matrix chain product.

6. Find Longest common subsequence of "human" and "chimpanzee".

7. Explain lower Bound Theory.
8. Solve by using fractional and 0/1 Knapsack problem,
i) Knapsack Capacity W = 25 and

Item	A	B	C	D
Price	12	9	9	5
Size	24	10	10	7

ii) where Knapsack Capacity W = 30 and

Item	A	B	C	D
Value	50	140	60	60
Size	5	20	10	12
Ratio	10	7	6	5