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

**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)