## Analysis of Algorithms - Dec 2015

### 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)** Define 0, Ω, and θ notations. To find the complexity of given recurrence relation.

i) T(n)=4T(n/2)+n^{3}

ii) T(n)=2T (n/2)+n^{3}.(10 marks)
**1 (b)** Implement the binary search, and derive its complexity.(10 marks)
**2 (a)** Explain 0/1 knapsack problem using dynamic programming.(10 marks)
**2 (b)** Explain optimal storage on tapes and find the optimal order for given instance.

n=3, and (1_{1}, 1_{2}, 1_{3})=(5, 10, 3).(10 marks)
**3 (a)** Let n=4, (p_{1}, p_{2}, p_{3}, p_{4})=(100, 10, 15, 27) and (d1, d2, d3, d4) = (2, 1, 2, 1). Find feasible solutions, using job sequencing with deadlines.(10 marks)
**3 (b)** Find a minimum cost path from 3 to 3 in the given graph using dynamic programming.

(10 marks)
**4 (a)** Explain 8 Queen problem.(10 marks)
**4 (b)** Explain sum of subset problem. Find all possible subsets of weight that sum to m, let n=6, m=30, and w[1:6]={5, 10, 12, 13, 15, 18}(10 marks)
**5 (a)** Write an algorithm for Kunth-Morrie-Pratt (KMP).(10 marks)
**5 (b)** Explain the Strassen's Matrix multiplication.(10 marks)

### Write note on (any two):

**6 (a)** Randomized Algorithms.(10 marks)
**6 (b)** Branch and bound strategy(10 marks)
**6 (c)** Huffman coding.(10 marks)
**6 (d)** Rabin karp algorithm(10 marks)