13

14

15

16

17

a)

b)

a)

b)

a)

b)

a)

b)

a)
b)
0)

1192010 Pages:4

Given 8 chain of 4 matrices with dimensions
,<4X6>,<6X2>,<2X7> respectively. Using Dynamic programming find the
minimum number of scalar multiplications needed and also write the optimal
multiplication order.

Write down Bellman Ford algorithm and analyse the complexity .What is the time
complexity of Bellman-Ford single-source shortest path algorithm on a complete
graph of n vertices?

Write a short note on graph traversals

Perform BFS traversal on the above graph starting from node A. If multiple node
choices may be available for next travel, choose the next node in alphabetical order.

(8) ಈ. (०)

Explain Strassen’s matrix multiplication and analyse its complexity
PART E
Answer any four full questions, each carries10 marks.
Give a comparison between dynamic programming and Divide and conquer
strategy
Apply Prim’s algorithm on the following graph. Let A be the source vertex

Formulate Fractional Knapsack Problem. Write Greedy Algorithm for fractional
Knapsack Problem.

Find the optimal solution for the following fractional Knapsack problem. Given
number of items(n)=4, capacity of sack(m) = 60, W={40,10,20,24} and
P={280,100,120,120}

Define NP hard and NP-Complete problems

Write short notes on Polynomial time reductions with example

Define class P and class NP

Page 3 of 4

(5)

(4)

(2)
(2)

(5)

(4)

(6)

(5)
(5)

(4)
(4)
(2)