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

ADD COMMENTlink
written 5 months ago by gravatar for aniketbab1 aniketbab10
Please log in to add an answer.