Analysis of Algorithms : Question Paper May 2013 - Computer Engineering (Semester 4)

20views

written 8.1 years ago by

Analysis of Algorithms - May 2013

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 Divide and Conquer strategy. Write control abstraction (general method) for it. List any four examples that can be solved by divide and conquer.(10 marks) 1 (b) Explain asymptotic notations. Explain time complexity and space complexity in detail.(10 marks) 2 (a) Explain Graph Colouring problem using backtracking. Write algorithm for same.(10 marks) 2 (b) Find out single source shortest path for following problem using Dijkstra's Algorithm.

(10 marks) 3 (a) Find the longest common subsequence from the given two sub-sequences:-
P = {100101101101}
Q = {0110}(10 marks) 3 (b) Explain 15 puzzle problem using Branch and Bound.(10 marks) 4 (a) Sort following numbers using Quicksort algorithm.
65, 70, 75, 80, 85, 60, 55, 50, 45.
Show all passes of execution. Also state the time complexity.(10 marks) 4 (b) Explain and write Knuth-Morris Pratt algorithm. Explain with an example.(10 marks) 5 (a) Explain job sequencing with deadlines. Solve the following instance: n=5
(P1, P2, P3, P4, P5) = (20, 15, 10, 5, 1)(d1, d2, d3, d4, d5) = (2, 2, 1, 3, 3)(10 marks) 5 (b) Solve the following sum of subset problem using backtracking:
w= {1, 3, 4, 5}, m=8.
Find the possible subsets of 'w' that sum to 'm'.(10 marks) 6 (a) Solve shortest path from source 1 for following graph using dynamic programming.

(10 marks) 6 (b) Explain travelling Salesperson Problem using branch and bound method.(10 marks)

Write short notes:-

7 (a) Differentiate between greedy approach and dynamic programming.(5 marks) 7 (b) Optimal Storage On Tapes(5 marks) 7 (c) Radix Sort(5 marks) 7 (d) Minimum Spanning Tree using Kruskal's algorithm.(5 marks)

ADD COMMENT EDIT