Tuesday, May 27, 2014

ANALYSIS OF ALGORITHMS (AOA) MAY 2010 COMPUTER AND SCIENCE SEMESTER 4

ANALYSIS OF ALGORITHMS (AOA) MAY 2010  COMPUTER AND SCIENCE SEMESTER 4

Con.3705-10                                        (REVISED COURSE)                     AN-3454

                                                                    (3 Hours)                            [Total Marks :-100]


N.B. (1) Question No.1 is compulsory.
        (2) Attempt any four questions from the remaining six questions.
        (3) Assumption made should be clearly stated.
        (4) Assume suitable data whenever required.


1. (a) Write a routine to delete a word from tries. [5 Marks]
    (b) Write an algorithm to find the sum of series and also find its time complexity
          where,  [5 Marks]
                        n
                 s=   ∑   i2
                       i=1  
    (c) Compare Greedy method & backtracking method. [5 Marks]
    (d) What is recursion? Write a routine to calculate Fibonacci series using it. [5 Marks]

2. (a) Implement the binary search, prove that the complexity of binary search is
         O(log2N). [10 Marks]
    (b) Explain randomized version of Quick sort and evaluate its complexity with
          example. [10 Marks]

3. (a) Explain with example job sequencing with deadlines. [10 Marks]
    (b) Explain optimal storage on tapes with example. [10 Marks] 

4. (a) Explain longest common subsequence with example. [10 Marks]
    (b) Write a note on all pairs shortest path algorithm. [10 Marks]

5. (a) Write and explain sum of subset algorithm, [10 Marks]
           with n=4, w= {2,7,8,15}, m=17
     (b) Explain backtracking method to solve 0/1 knapsack problem. [10 Marks]
          Find solution for n=3, m=20
          (p1, p2, p3) = (25,24,15) and (w1,w2,w3) = (18,15,10).

6. (a) Find minimum cost spanning tree for the given graph figure,using prim's & kruskal's
         Algorithm :- [10 Marks]
             

    (b) Explain how branch and bound method can be applied to solve 15 puzzle using least
         cost search. [10 Marks]

7. (a) Implement merge sort using divide & conquer strategy. [10 Marks]
         sort the following numbers showing output of each pass.
         100,20, 38, 14, 48, 07, 17, 57, 93, 35
   (b) Find the Huffman code for the following set of frequencies based on the first 8
        Fibonacci numbers. [10 Marks]
        a=1, b=1, c=2, d=3, e=5, f=8, g=13, h=21.    

No comments:

Post a Comment