Analysis of Algorithms - May 2017
MU Computer Engineering (Semester 4)
Total marks: --80
Total time: --3hrsINSTRUCTIONS
(1) Assume appropriate data and state your reasons
(2) Marks are given to the right of every question
(3) Draw neat diagrams wherever necessary
Total time: --3hrsINSTRUCTIONS
(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 scheduling5 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=125 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 ABE5 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 of three questions from Q.6(a, b, c,d)
6(a) !mage Problem of multiplying Long integers5 marks
6(b) Strassen's matrix multiplication5 marks
6(c) Knuth Morris Pratt's Pattern matching5 marks
6(d) Multi stage Graphs5 marks
