## Analysis of Algorithms - Dec 2014

### 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)** Write an algorithm to find minimum and maximum value using divide and conquer and also drive its complexity.(10 marks)
**1 (b)** To sort the given set of number using insertion sort and also show the result of each pass.

<11, 7, 17, 3, 9, 29, 85, 9>(10 marks)
**2 (a)** Find an optional solution to the knapsack instance n=7 m=15, Profit = {10, 5, 15, 7, 6, 18, 3}

Weight = {2, 3, 5, 7, 1, 4, 1}(10 marks)
**2 (b)** Explain optimal storage on tape with example.(10 marks)
**3 (a)** Find a minimum cost path from 1 to 9 in the given graph using dynamic programming.

(10 marks)
**3 (b)** Find the path of travelling sales person problem of given graph.

(10 marks)
**4 (a)** To generate the Huffman code for given set of frequencies.

1, 1, 2, 3, 4, 8, 13, 21(10 marks)
**4 (b)** To implement the Knuth-Morris-Pratt, string matching algorithm.(10 marks)
**5 (a)** To find MST of following graph using Prim's and Kruskal's algorithm.

(10 marks)
**5 (b)** Explain flow shop scheduling using suitable data.(10 marks)

### Write notes on: (any two): -

**6 (a)** N-Queen problem.(10 marks)
**6 (b)** Randomized Algorithm(10 marks)
**6 (c)** Tries(10 marks)
**6 (d)** The 15 Puzzle problem.(10 marks)