## 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, (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.
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