Scribd Logo
Upload

Welcome to Scribd!

  • 3 views

    ADA Questions For Prefinal

    Uploaded by

    anagha141516

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    ADA Questions For Prefinal

    Uploaded by

    anagha141516
    3 views2 pages

    Original Title

    ADA Questions for Prefinal

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    3 views2 pages

    ADA Questions For Prefinal

    Uploaded by

    anagha141516

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 2

    Short Answer Questions

    1. What do you mean by Asymptotic Notations? Explain.

    2. What is an algorithm?

    3. Explain about Disjoint set operations

    4. Write simple union algorithm

    5. Solve the recurrence T(n) = 7T(n/2) + n 3, T(n) = 3T(n/3) +n3.

    6. List out the applications of Backtracking techniques

    7. Write the objective of Travelling Salesperson Problem

    8. List out the applications of Dynamic Programming

    9. Distinguish between Prim’s and Kruskal’s spanning tree algorithm.

    10. Write the general method and Control Abstraction of Greedy method

    11. Define Non deterministic algorithm

    12. Define i) Principles of optimality ii) Feasible solution iii) Optimal solution.

    13. List out the applications of Dynamic Programming

    14. Write the Control Abstraction of Least – Cost Branch and Bound

    15. Define: i) LC – Search ii) Branch and Bound (BB) iii) FIFO – BB

    Long Answer Questions


    1. a) Explain the use of Divide and Conquer Technique for Binary Search Method.

    What is the complexity of Binary Search Method? Explain it with example. .

    b) Discuss matrix multiplication problem using divide and conquer technique

    2. Explain Merge sort (Stable sort (or) Not in-place) algorithm and trace this algorithm for

    n =8 elements: 24,12, 35, 23,45,34,20,48

    b) Derive the time complexity of Merge sort algorithm for all cases

    3. a) Discuss the general method of Backtracking strategy rule

    b) Give the statement of sum –of subsets problem. Find all sum of subsets for n=4, (w1, w2, w3, w4) =

    (11, 13, 24, 7) and M=31.Draw the portion of the state space tree using fixed – tuple sized approach

    4. a) What are union and find operations? Explain with suitable examples.

    b) Define Chromatic number. Explain about graph coloring algorithm.

    5. Consider n=4 & (q1,q2,q3,q4)=(do, if, int, while) the values for p’s & q’s are given as
    p(1:4)=(3,3,1,1) & q(0:4)=(2,3,1,1,1). Construct the Optimal Binary Search tree.

    6. a) State the principle of optimality in dynamic programming

    b) Write a function to compute lengths of shortest paths between all pairs of nodes for the given adjacency
    matrix.

    0 6 13
    . 8 0 4
    5 ∞ 0

    7. a) Define Minimum Spanning Tree(MST). Explain Krushkal’s Algorithm to find MST with example.

    b) Explain Prim’s Algorithm to find Minimum Spanning Tree with example. What is its Time
    Complexity?

    8. Define Greedy knapsack. Find the optimal solution of the Knapsack instance n= 7, M=20,

    (p1, p2, ……p7) = (8,5,6,7,6,12,3) and (w1,w2,....w7)=(2,10,8,7,6,4,11).

    9. Draw the portion of state space tree generated by LCBB for the following instance of

    0/1 knapsack n= 4, M=15, (p1,p2,p3,p4)=(10,10,12,18) (w1,w2,w3,w4) =(2, 4, 6, 9)

    10. a) Explain P,NP,NP Hard & NP complete classes

    b) Discuss about Cook’s theorem

    You might also like