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

!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

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

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

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

6(b)
Job sequencing with deadlines

5 M

6(c)
Flow shop scheduling

5 M

6(d)
Multistage Graphs

5 M

6(e)
A symptotic Notations

5 M

More question papers from Analysis of Algorithms