Analysis of Algorithms - Dec 2012

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) Arrange the following functions in increasing order
N, log n, n³, n², nlogn, 2ⁿ, n!(5 marks) 1 (b) Explain general method of dynamic programming. List different examples of it.(5 marks) 1 (c) Justify Greedy approach for solving knapsack problem.(5 marks) 1 (d) State Graph Colouring problem. State the strategy used to solve above problem.(5 marks) 2 (a) Sort the following numbers using Merge Sort-
27, 6, 18, 25, 48, 59, 98, 34.
Give the output of each pass. Write an algorithm for merge sort.(10 marks) 2 (b) Write an algorithm for minimum spanning tree using Prim^'s method.(10 marks) 3 (a) Explain N-Queen^'s problem using backtracking with algorithm.(10 marks) 3 (b) Consider the following set of frequencies
A=2, B=6, C=4, D=15, E=7, F=22, H=17
Find Huffman codes for the same.(10 marks) 4 (a) Describe 0/1 knapsack problem. How to solve it using branch and bound?(10 marks) 4 (b) Write an algorithm for binary search. Derive its best case and worst case complexities.(10 marks) 5 (a) For the following graph find all pairs shortest path using dynamic programming.

Write short notes on the following :-

7 (a) Radix Sort(5 marks) 7 (b) Job Sequencing with Deadline(5 marks) 7 (c) Strassens Multiplication(5 marks) 7 (d) Branch and Bound Strategy(5 marks)