Question Paper: Analysis of Algorithms : Question Paper Dec 2016 - Computer Engineering (Semester 4) | Mumbai University (MU)
0

## Analysis of Algorithms - Dec 2016

### Computer Engineering (Semester 4)

TOTAL MARKS: 80
TOTAL TIME: 3 HOURS
(1) Question 1 is compulsory.
(2) Attempt any three from the remaining questions.
(3) Assume data if required.
(4) Figures to the right indicate full marks.
1(a) Which are the different methods of solving recurrences. Explain with examples.(10 marks) 1(b) Comapare Greedy and dynamic programming approach for algorithm Design. Explain How both can be used to solve Knapsack problem?(10 marks) 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 marks) 2(b) Write single source shortest path algorithm & apply the same for following.

(10 marks) 3(a) Explain string matching with finite automata and apply the same technique to match following pattern
txt [ ] = UNIVERSITY OF MUMBAI
pat [ ]= MBA
(10 marks)
3(b) Comapare Prims & Kruskal's method for finding Minimum spanning Tree find MST for following using prims method.
!mage
(10 marks)
4(a) Expalin with example how divide and conquer stratergy is used in binary search?(10 marks) 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 marks)
5(a) Explain longest common subsequence problem with example.(10 marks) 5(b) What is backtracking method? How it is used in graph coloring problem?(10 marks)

### Write a short note any four Q6.(a,b,c,d,e)

6(a) 8 queens problem(5 marks) 6(b) Job sequencing with deadlines(5 marks) 6(c) Flow shop scheduling(5 marks) 6(d) Multistage Graphs(5 marks) 6(e) A symptotic Notations(5 marks)