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.
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 patterntxt [ ] = 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)
