MORE IN Analysis of Algorithms
MU Computer Engineering (Semester 4)
Analysis of Algorithms
May 2017
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 M
1(b)

Write the algorithm and derived the complexity of Binary search algorithm.

5 M
1(c) Explain masters method with example.
5 M
1(d) Write a note on flow shop scheduling
5 M
1(e) Compare divide and conquer, dynamic programming and Backtracking approache used for algorithm design.
5 M

2(a) Write and explain string matching with finite automata with an example.
10 M
2(b) Explain how branch and bound strategy can be used in 15 puzzle problem.
10 M

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
10 M
3(b) Explain insertion sort derive its complexity.
10 M

4(a) What is a binary search tree? How to generate optial binary search tree.
10 M
4(b) What is a longest common subsequence problem? Find LCS for following string X= ACB AED Y = ABC ABE
10 M

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.
10 M
5(b) Explain prims algorithm and minimum spanning tree for the follwing graph.
10 M

Solve any fthree question from Q.6(a, b, c,d)
6(a) !mage Problem of multiplying Long integers
7 M
6(b) Strassen's matrix multiplication
7 M
6(c) Knuth Morris Pratt's Pattern matching
7 M
6(d) Multi stage Graphs
7 M

More question papers from Analysis of Algorithms