Question Paper: Analysis of Algorithms : Question Paper Dec 2012 - Computer Engineering (Semester 4) | Mumbai University (MU)
0

## 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, n3, n2, nlogn, 2n, 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.

(10 marks) 5 (b) Explain optimal storage on tapes.(10 marks) 6 (a) Find longest subsequence of given two steps
X = {B A T A}
Y = {T A T A}
(10 marks)
6 (b) Explain single source shortest path using dynamic programming. Write an algorithm for the same.(10 marks)

### 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)