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