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

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)