Scribd Logo
Upload

Welcome to Scribd!

  • 8 views

    ADA QUESTUION BANK1

    Uploaded by

    nastikpure

    Copyright:

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

    ADA QUESTUION BANK1

    Uploaded by

    nastikpure
    8 views2 pages

    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
    8 views2 pages

    ADA QUESTUION BANK1

    Uploaded by

    nastikpure

    Copyright:

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

    Ahmedabad Institute of Technology

    Computer Engineering Department


    Analysis and Design of Algorithm(3150703)
    Question Bank

    1. What is asymptotic notation? Explain (i) Big O Notation, (ii) Big Theta Notation, (iii)
    Big Omega Notation.

    2. Solve the following using Master’s theorem: a. T(n) = 2T(n/4) + 1


    b. T(n)=3T(n/4) + nlgn
    3. Solve the following recurrence relation using the substitution method. T(n)
    =2T(n/2) + n. Here T(1) = 1.
    4. Arrange the following rate of growth in increasing order. 2N, n log n,
    n2, 1 , n, logn, n!, n3
    5. Explain Merge Sort algorithm with suitable examples.
    6. Analyze quick sort algorithm for best case, average case and worst case with
    example.In which case it performs similar to selection sort?
    7. What is the Principle of Optimality? Explain advantages and disadvantages of dynamic
    programming.
    8. Using algorithm find an optimal parenthesization of a matrix chain product whose
    sequence of dimension is (5,10,3,12,5,50,6) (use dynamic programming)
    9. Solve the following knapsack problem using a dynamic programming algorithm with
    given capacity W=5, Weight and Value are as follows (2,12),(1,10),(3,20),(2,15).
    10. Find an optimal Huffman code for the following set of frequency.

    A : 50, b: 20, c: 15, d: 30

    11. Explain depth first traversal using suitable examples.


    12. Write the Prim’s Algorithm to find out Minimum Spanning Tree.
    Apply the same and find MST for the graph given below.
    13. Generate minimum spanning tree using Kruskal's algorithm for the following
    graph.

    14. Find out LCS of A={K,A,N,D,L,A,P} and B = {A,N,D,L}


    15. Explain: Articulation Point, Graph, Tree.
    16. Explain general characteristics of greedy algorithms.
    17. Find out minimum number of multiplications required for multiplying:
    A[1 × 5], B[5 × 4], C[4 × 3], D[3 × 2], and E[2 × 1].
    18. Solve Making Change problems using Dynamic Programming. (Denominations:
    d1=1, d2=4, d3=6). Give your answer for making change of Rs. 9.
    19. Discuss Assembly Line Scheduling problem using dynamic programming with example.
    20. Explain the characteristics of Greedy algorithms. Compare Greedy algorithms with
    Dynamic Programming Method.

    You might also like