## 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^{2}-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)