## Analysis of Algorithms - May 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)** Explain the asymptotic notations.(10 marks)
**1(b)** Write an algorithm to find minimum and maximum value using divide and conquer and also derive its complexity.(10 marks)
**2(a)** Explain the concept of multiplying long integers using divide and conquer.(10 marks)
**2(b)** Sort the following numbers using Quick Sort. Also derive the time complexity of Quick Sort.

50, 31,71,81,12,33(10 marks)
**3(a)** Solve the following Job sequescing with deadlines problem

n=7, Profits (p1, p2, ......, p7) = {3, 5, 20, 18, 1, 6, 30}

Deadlines(d1,d2,......,d7) = {1, 3, 4, 3, 2, 1, 2}(10 marks)
**3(b)** Explain Different string matching algorithm.(10 marks)
**4(a)** Find the Minimum Spanning Tree of the following graph using Kruskal's algorithm

**4(b)**Explain flow shop scheduling with example.(10 marks)

**5(a)**Write an algorithm for sum of subsets. Solve the following problem.

M=30 W={5, 10, 12,13,15,18}(10 marks)

**5(b)**Find the shortest path from source vertex A using Dijkstra's algorithm (10 marks)

### Write note on (any two)

**6(a)** Strasen;s matrix multiplication(10 marks)
**6(b)** 8- Queen problem.(10 marks)
**6(c)** Graph coloring(10 marks)
**6(d)** 15-puzzle problem(10 marks)