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)
3. Create MST by primes and kruskal's algorithm
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)
1/12(11n^2 – 5n)
| |
n^2 – n + 1
| |
6n – 11
| |
| 2n+1 |
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
ii) where Knapsack Capacity W = 30 and
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 |
| Item | A | B | C | D |
| Value | 50 | 140 | 60 | 60 |
| Size | 5 | 20 | 10 | 12 |
| Ratio | 10 | 7 | 6 | 5 |
