Question Paper: Analysis of Algorithms Question Paper - May 2017 - Computer Engineering (Semester 4) - Mumbai University (MU)
0

## Analysis of Algorithms - May 2017

### MU Computer Engineering (Semester 4)

Total marks: --
Total time: --
INSTRUCTIONS
(1) Assume appropriate data and state your reasons
(2) Marks are given to the right of every question
(3) Draw neat diagrams wherever necessary

### Solve any four question from Q.1(a, b, c,d, e)

1(a) Write an algorithm for finding maximum and minimum number from given set. 5 marks

1(b) Write the algorithm and derived the complexity of Binary search algorithm. 5 marks

1(c) Explain masters method with example. 5 marks

1(d) Write a note on flow shop scheduling 5 marks

1(e) Compare divide and conquer, dynamic programming and Backtracking approache used for algorithm design. 5 marks

2(a) Write and explain string matching with finite automata with an example. 5 marks

2(b) Explain how branch and bound strategy can be used in 15 puzzle problem. 5 marks

3(a) What is 0/1 knapsack and fractional knasack problem. Slove following 0/1 knasack method.

 Item(i) Value(vi) Weight(wi) 1 18 3 2 25 5 3 27 4 4 10 3 5 15 6

Knapsack capacity=12 5 marks

3(b) Explain insertion sort derive its complexity. 5 marks

4(a) What is a binary search tree? How to generate optial binary search tree. 5 marks

4(b) What is a longest common subsequence problem? Find LCS for following string X= ACB AED Y = ABC ABE 5 marks

5(a) Explain job Sequence with deadlines. Let n=4, (p1, P2, P3, P4) = (100,10,15, 27) and (d1, d2, d3, d4) (2, 1, 2, 1) find feasible solution. 5 marks

5(b) Explain prims algorithm and minimum spanning tree for the follwing graph. 5 marks

### Solve any fthree question from Q.6(a, b, c,d)

6(a) !mage Problem of multiplying Long integers 5 marks

6(b) Strassen's matrix multiplication 5 marks

6(c) Knuth Morris Pratt's Pattern matching 5 marks

6(d) Multi stage Graphs 5 marks