ANALYSIS OF ALGORITHMS (AOA) DECEMBER 2013 COMPUTER AND SCIENCE SEMESTER 4
Con.5779-13. LJ-10604(3 Hours) [Total Marks : -100]
N.B.: (1) Question No.1 is compulsory.
(2) Attempt any four out of remaining six questions.
(3) Assume suitable data wherever required.
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]
(b) Explain asymptotic . Explain time complexity and space complexity in detail. [10 Marks]
2. (a) Construct the optimal binary search tree for identifier set [10 Marks]
(a1,a2,a3,a4,) = (count, float, if, while)
(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]
(b) Solve following problem using krushkal's algorithm which is used to find minimum
spanning tree. [10 Marks]
4. (a) State graph coloring algorithm. Explain strategy used for solving it along with
example. [10 Marks]
(b) Consider following set of frequencies. [10 Marks]
A=2 B=5 C=7 D=8 E=7 F=22 G=4 H=17
Find Huffman code for same.
5. (a) Explain Binary search. Derive its best case and worst case complexity. [10 Marks]
(b) Find shortest path using Djkstra's algorithm 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]
(b) Explain job sequencing with dead lines along with example. [10 Marks]
7. Write short notes on the following :- [20 Marks]
(i) Radix sort
(ii) Tries
(iii) Randomised algorithm
(iv) Strassen's matrix multiplication.
No comments:
Post a Comment