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

## Analysis of Algorithms - Dec 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 problems that can be solved using divide and conquer.(10 marks) 1(b)

Explain asymptotic notation.Explain time complexity and space complexity in detail.

(10 marks) 2(a)

Construct the optimal Binary search tree for identifier set

$(a_{1},a_{2},a_{3},a_{4})=(Cout,float.if,while)\\\\ with \ p(1:4)=\left(\dfrac{1}{20},\dfrac{1}{5},\dfrac{1}{10},\dfrac{1}{20}\right)\\\\ and \ q(0:4)=\left(\dfrac{1}{5},\dfrac{1}{10},\dfrac{1}{5},\dfrac{1}{20},\dfrac{1}{20}\right)$

(10 marks) 2(b) Explain 0/1 knapsack problem using Branch and Bound method.(10 marks) 3(a) Explain flow shop scheduling with the help of example.(10 marks) 3(b)

Solve following problem using Kruskal's algorithm which is used to find minimum spanning tree.

(10 marks) 4(a) state graph colouring algorithm.Explain strategy used solving it along with example.(10 marks) 4(b) Consider following set of frequencies
A=2 B=5 C=7 D=8 E=7 F=22 G=4 H=17
Find Huffman code for same.
(10 marks)
5(a) Explain Binary search.Derive its best case and worst case complexity.(10 marks) 5(b)

Find shortest path using Djkstra's algorithms for the following graph assume source node is A.

(10 marks) 6(a) Explain 8 Queen problem and strategy used to solve it.(10 marks) 6(b) Explain job sequencing with dead lines along with example.(10 marks)

### Write short notes on the following:

7(a) Radix sort(5 marks) 7(b) Tries(5 marks) 7(c) Randomised Algorithm(5 marks) 7(d) Strassen's matrix multiplication.(5 marks)