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.

Knapsack capacity=12

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, (p

_{1}, P_{2}, P_{3}, P_{4}) = (100,10,15, 27) and (d_{1}, d_{2}, d_{3}, d_{4}) (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