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