Osmania University (OU) 2009-2nd Year M.C.A Computer Aplications II Semester (Main) , - Question Paper

                                                                                                                                 

                                                                              Code No.816
                                       FACULTY OF INFORMATICS
                       
                       M.C.A II Year II Semester (Main) Examination, May 2009

                               Subject : DESIGN AND ANALYSIS OF ALGORITHMS
  Time : three Hours                                                              Max. Marks :80
          
   Note : ans 1 ques. from every Unit. All ques. carry equal marks.

                                          UNIT - I


1. (a)What are 5 criterias that an algorithm must satisfy?       [marks :4]
    
   (b)Explain the subsequent  :                                      [3*4=12 marks]
      (i)Asymptotic notations            (ii) Amortization
     (iii) Primality testing.

                                            OR

2. (a) discuss the following:                                       [4*3=12 marks]
       (i) Priority queues                    (ii) Union, obtain Algorithms
       (iii) Degenerated trees               (iv) Graph Representations.
 
   (b) Write an iterative algorithm to created Binary search tree. [marks :4] 

                                             
                                          UNIT - II

3. (a) Write Strassen's Matrix multiplication algorithm.Determine the time complexity. [marks :10] 

   (b) Using selection sort algorithm sort the subsequent set of elements.   [marks :6]      
       {30,25,15,10,12,20}

                                            OR

4. (a) Write control Abstraction for Greedy method.                  [marks :4]    

   (b)Write and discuss job sequencing with Deadlines algorithm. obtain optimal solution [marks :12] 
      for the subsequent instance n=5,(P1,....,P5)=(20,15,10,5,1) and (d1,...d5)=(2,2,1,3,3)
      where n is the number of jobs, to be processed. 


                                          UNIT - III


5. (a) What is Multistage graph problem? Write equations for forward approach and backward approach.[marks :6] 

   (b) provide a Fine Stage graph. obtain minimum cost path from s to t using forward approach.    [marks :10] 
       (Diagram for this (b)question is attached below)

                                            OR

6. (a) Write algorithm for optimal binary search tree.              [marks :8] 

   (b) Use OBST algorithm to calculate w(i,j), r(i,j), 0<=i       (a1,a2,a3,a4)= (cout,float,if,while) with P(1...4)=(1/20,1/5,1/10,1/20),
       q(0...4=(1/5,1/10,1/5,1/20,1/20). Using the r(i,j)'s construct the optimal binary search tree.

                           
                                         UNIT - IV

7.(a) Write algorithm for 8-queen's issue.                        [marks :8]

  (b) Draw solution state space tree for 4-queen's issues when nodes are numbered     [marks :8] 
      as in depth-first search.             

                                            OR

8.(a) Write control Absraction for LC-seach.                        [marks :8]
  
  (b) Draw the portion of the state tree generated by LCBB for the subsequent Knapsack   [marks :8]
      instance: n=5,(p1,p2...p5=(10,15,6,8,4),(W1,W2,...W5)=(4,6,3,4,2), m=12.

                              
                                         UNIT - V


9.(a) explain Cook's theorem .                                       [marks :12]      

  (b) discuss NP-completeness theory.                                [marks :4] 

                                           OR
10.(a)Show relationship ranging from P, NP, NP-complete, NP-Hard issues.[marks :6]
   
   (b) Show that CNF-satisfiability is reducable to Clique decision issue.      [marks :10] 

Earning:   Approval pending.