Untitled - #18172

MUMBAI UNIVERSITY

Subject: Analysis of Algorithms

Semester: 4

[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
____________________________________________________________________________________________________________________________