× Close
Join the Ques10 Community
Ques10 is a community of thousands of students, teachers, and academic experts, just like you.
Join them; it only takes a minute
Sign up
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

question paper mu • 38 views
ADD COMMENTlink
written 13 days ago by gravatar for swatkat1127 swatkat1127 ♦♦ 0
Please log in to add an answer.


Use of this site constitutes acceptance of our User Agreement and Privacy Policy.