MORE IN Analysis of Algorithms
MU Computer Engineering (Semester 4)
Analysis of Algorithms
December 2016
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

1(a) Which are the different methods of solving recurrences. Explain with examples.
10 M
1(b) Comapare Greedy and dynamic programming approach for algorithm Design. Explain How both can be used to solve Knapsack problem?
10 M

2(a) Explain the analysis of quick sort and apply the same to sort following data [1 0 7 5 9 1 2 3]
10 M
2(b) Write single source shortest path algorithm & apply the same for following.
!mage
10 M

3(a) Explain string matching with finite automata and apply the same technique to match following pattern
txt [ ] = UNIVERSITY OF MUMBAI
pat [ ]= MBA
10 M
3(b) Comapare Prims & Kruskal's method for finding Minimum spanning Tree find MST for following using prims method.
!mage
10 M

4(a) Expalin with example how divide and conquer stratergy is used in binary search?
10 M
4(b) Solve sum of subsets problem for following
N=6 W={3,5,7,8,9,15} & M =20 Also write the Algorithm for it.
10 M

5(a) Explain longest common subsequence problem with example.
10 M
5(b) What is backtracking method? How it is used in graph coloring problem?
10 M

Write a short note any four Q6.(a,b,c,d,e)
6(a) 8 queens problem
5 M