ANALYSIS OF ALGORITHMS (AOA) DECEMBER 2012 COMPUTER AND SCIENCE SEMESTER 4
Con.7847-12 KR-7472(3 Hours) [Total Marks :- 100]
N.B.: (1) Question No.1 is compulsory.
(2) Solve any four questions out of remaining six questions.
(3) Figures to the right indicate full marks.
(4) Assume suitable data if necessary but justify the same.
1. (a) Arrange the following function in increasing order. [5 Marks]
(b) Explain general method of Dynamic programming. List different examples of it. [5 Marks]
(c) Justify greedy approach for solving Knapsack problem. [5 Marks]
(d) State graph coloring problem. State the strategy used to solve above problem. [5 Marks]
2. (a) Sort the following numbers using Merge sort. Give the output of each pass. Write an algorithm
for Merge sort. [10 Marks]
27, 6, 18, 25, 48, 59, 98, 34
(b) Write an algorithm for minimum spanning tree using Prim's method. [10 Marks]
3. (a) Explain N-Queen's problem using Backtracking with algorithm. [10 Marks]
(b) Consider the following set of frequencies. [10 Marks]
A=2, B=6, C=4, D=15, E=7, F=22, G=9, H=17
Find Huffman codes for the same.
4. (a) Describe O/I Knapsack problem. How to solve it using Branch and Bound? [10 Marks]
(b) Write an algorithm for binary search. Derive its best case and worst case
complexities. [10 Marks]
5. (a) For the following graph find all pair shortest path using Dynamic programming. [10 Marks]
6. (a) Find longest common subsequence of given two strings. [10 Marks]
X = {B A T A}
Y = {T A T A}
(b) Explain single source shortest path using Dynamic programming. Write an algorithm
for same. [10 Marks]
7. Write short notes on the following:- [20 Marks]
(a) Radix Sort
(b) Job sequencing with Dead lines
(c) Strassen's Matrix Multiplication
(d) Branch and Bound strategy
No comments:
Post a Comment