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