Analysis of Algorithms - May 2014

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) Explain 0, Ω and θ Notation with the help of graph.And represent the following function using above notations.
T(n)=3n+2
T(n) = 10n²-1(10 marks) 1(b) Explain 0/1 knapsack problem with example.(10 marks) 2(a) Write an algorithm of sum of subset.Solve following problem and draw portion of state space tree M =35,W=(5,7,10,12,15,18,20).(10 marks) 2(b) Explain longest common subsequence with example.(10 marks) 3(a) Explain all pair shortest path algorithm with suitable example.(10 marks) 3(b) Explain different string matching algorithms.(10 marks) 4(a) Write a Min Max function to find minimum and maximum value from given set of values using divide and conquer.Also drive its complexities.(10 marks) 4(b) Comment on any two modules of computation.(10 marks) 5(a) To find Dijkstra's shortest path from vertex 1 to vertex 4 for following graph.
(10 marks) 5(b) Explain flow shop scheduling with example.(10 marks)

Write notes on: (any two): -

6 (a) Job sequencing with deadlines(10 marks) 6 (b) Randomized Algorithm(10 marks) 6 (c) The 15 Puzzle problem.(10 marks) 6 (d) N-Queen problem.(10 marks)