A

14 a)
b)

15 a)
b)
0)

16 a)
0)

17 a)
0)

11008 Pages: 4

.. [و 859

State Matrix Chain Multiplication Problem. Write Dynamic Programming Algorithm for
Matrix Chain Multiplication Problem.
Using Dynamic Programming, find the fully parenthesized matrix product for multiplying
the chain of matrices< Al ۸2 A3 A4 A5 06 > whose dimensions are <30X35>, <35X15>,
<15X5>, <5X10>, <10X20> and <20X25> respectively.
PART E

Answer any four full questions, each carries10 marks.
Explain Greedy Approach. Write the general greedy algorithm.
Formulate Fractional Knapsack Problem. Write Greedy Algorithm for fractional Knapsack
Problem.
Find the optimal solution for the following fractional Knapsack problem.
n=4, m = 60, W={40, 10, 20, 24} and P={280, 100, 120, 120}
Write the Kruskal’s algorithm for Minimum Spanning Tree. Analyse its complexity.
Compute the Minimum Spanning Tree and its cost for the following graph using Kruskal’s

Algorithm. Indicate each step clearly.

An undirected graph G=(V, E) contains n (n> 2 ) nodes named நட, V2,....Vn. Two vertices ‏زلا‎ , vj are
connected if and only if 0 < |i — || <= 2. Each edge (vi, vj) is assigned a weight i + |. What will be
the cost of the minimum spanning tree (as a function of n) of such a graph with n nodes?

Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry wij in the matrix W
below is the weight of the edge {i, j}. What is the Cost of the Minimum Spanning Tree T using

Prim’s Algorithm in this graph such that vertex 0 is a leaf node in the tree T?

Page 3 of 4

(4)

(5)

(3)
(4)

(3)

(6)
(4)

(4)

(6)