ANALYSIS OF ALGORITHMS (AOA) DECEMBER 2009 COMPUTER AND SCIENCE SEMESTER 4

ANALYSIS OF ALGORITHMS (AOA) DECEMBER 2009 COMPUTER AND SCIENCE SEMESTER 4

Con.5681-09.                                      (REVISED COURSE)                                 SP-7808

                                                           (3 Hours)                                              [Total Marks: -100]

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

1. (a) Consider the iterative program to find fibonacci numbers. [5 Marks]
          unsigned int fibonacci (Unsigned int n)
          {
            int previous = -1
            int result = 1
            for (Unsigned int i20; i< = n; ++i)
               {
                  int Const Sum = result + previous,
                  previous = result;
                  result = sum;
                 }
           return = sum;
           }
           Determine the running time of the above algorithm.
      (b) Discuss the best case and worst case efficiency for a quick sort algorithm. [5 Marks]
      (c) Write and explain with illustration the recursive algorithm for a merge sort. [5 Marks]
      (d) Explain the Strassen's Matrix Multiplication. [5 Marks]

2. (a) Explain the following algorithm with an example and give its complexity: [10 Marks]
         (i) Selection Sort         ii) Heap Sort
    (b) Write the algorithm for for pattern matching using Boyer-Moore Algorithm. Suppose we
           have a string - abacaabaccabacabaabb. Illustrate the Boyer Moore algorithm to search
           a string  -> abacab. [10 Marks]

3. (a) What are trics? What are its applications? Briefly, describe the types of tries. [10 Marks]
    (b) Illustrate the heap sort algorithm for the array. [10 Marks]
         A= <27, 17, 3, 16, 13, 10, 1, 5, 7, 12, 4, 8, 9>

4. (a) Find the minimum cost spanning tree for the graph using Prim's and Kruskal's
         algorithm. [10 Marks]

    (b) Write an algorithm for 0/1 Knapsack problem using dynamic programming. When do we
          use the greedy algorithm for the Knapsack problem? Explain. [10 Marks]

5. (a) Find the Huffman code for the following set of frequencies, based on the fist 8 fibonacci
         numbers. [10 Marks]
         a= 1, b = 1, c = 2, d = 3, e = 5, f = 8, g = 13, h = 21.
    (b) Explain the graph coloring algorithm with an example. [10 Marks]

6. (a) Explain the 8-queen problem. Write an algorithm using back -tracking to solve this
         problem. [10 Marks]
    (b) Compare the Radix sort and Bucket sort algorithm and state its complexity. [10 Marks] 
          (Write both the algorithms). [10 Marks]

7. (a) Explain the quick sort algorithm using the Divide and Conquer method. [10 Marks]
         Determine the complexity for the worst case/best case and average case.
    (b) Write short notes on the following :- [10 Marks]
           (i) Warshall's Algorithm       (ii) Djkstra's Algorithm