ANALYSIS OF ALGORITHMS (AOA) DECEMBER 2010 COMPUTER AND SCIENCE SEMESTER 4
Con.6221-10. GT-6462(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.
(4) Figures to right indicate full marks.
1. (a) Explain Big-oh, Omega and Theta Notations with the help of diagram. How do we analyze
and measure time complexity of algorithm? [10 Marks]
(b) Calculate variable length Huffman code for the following frequencies: [10 Marks]
A=1, B=2, C=1, D=4, E=8, F=5, G=14, H=22
2. (a) Prove that for the quick sort, [10 Marks]
(i) Worst case efficiency is T(N) = O(N2)
(ii) Best case efficiency is T(N) = O(NlogN)
(b) Explain the strassen's Matrix Multiplication. [10 Marks]
3. (a) Find MST of following graph using prim's and kruskal's Algorithm. [10 Marks]
(b) Explain optimal storage on tape with example. [10 Marks]
4. (a) Explain Hamiltonian Cycle and give an algorithm to find all Hamiltonian cycle. [10 Marks]
(b) Consider the following instance of the Knapsack problem: [10 Marks]
No. of objects n=3, knapsack capacity m=20, profits (p1,p2,p3) = (25,24,15) and
weights (w1,w2,w3) = (18,15,10)
Find out the optimal solution using greedy method.
5. (a) Describe 8 Queen problem. Write an algorithm using backtracking to solve this
problem. [10 Marks]
(b) What is Travelling Salesman problem. How to solve the same problem using Branch
Bound. Explain with example. [10 Marks]
5. (a) Describe the advantages of dynamic programming. How it differ from Divide and
Conquer. [10 Marks]
(b) Sort the following list of elements in ascending order using merge sort technique. Give output
of each pass. [10 Marks]
90, 20, 80, 89, 70, 65, 85, 74
7. (a) Define the Knuth-Morris-Fratt Algorithm for string matching. [10 Marks]
Write a function to implement the concept of the same algorithm.
(b) Write short note on : (any two) [10 Marks]
i) Tries
ii) Job sequencing with Deadlines
iii) Randomized Algorithms.
No comments:
Post a Comment