**[Total Time: 3 Hours]**

** [Total Marks: 80]**

**N.B.: (1) Question No. 1 is compulsory.**

** (2) Attempt any three out of the remaining five questions.**

** (3) Assumptions made should be clearly stated.
**____________________________________________________________________________________________________________________________

Q. 1) a) Explain recurrences and various methods to solve recurrences. **(5M)**

b) Differentiate between P and NP. **(5M)**

c) Differentiate between Prims and Kruskal’s algorithm. **(5M)**

d) Explain Dynamic programming with example. **(5M)**

Q. 2) a) Define Branch and Bound and Explain 15 Puzzle problems. **(10M)**

b) Apply Dijkstra’s algorithm on the following graph. **(10M)**

Consider vertex 0 as a source.

Q. 3) a) Find Longest Common Subsequence for Following strings : **(10M)**

X = ababcde

Y = bacadb

b) Explain Backtracking with an n-queen problem. **(10M)**

Q. 4) (a) Formulate Knapsack problem, Explain and differentiate between greedy knapsack and 0/1 knapsack. (10M)

b) Explain Multistage graph with example. **(10M)**

Q. 5) a) Rewrite KMP algorithm and explain with example. **(10M)**

b) Define a chromatic number of a graph. Explain Graph coloring algorithm. **(10M)**

Q. 6) Write a short note on following (any 4) **(20M)**

a) Master theorem

b) Rabin Karp algorithm

c) Steps for NP-Completeness proofs

d) Assembly line scheduling problem

e) Strassen’s matrix multiplication

____________________________________________________________________________________________________________________________

Login

Accessing this course requires a login. Please enter your credentials below!