Scribd Logo
Upload

Welcome to Scribd!

  • 103 views

    Daa Question Paper

    Uploaded by

    varsha reddy
    This document contains a 20 question multiple choice exam on algorithms and data structures concepts like knapsack problem, spanning trees, single source shortest path problem, and complexity analysis notations like Big-O and Theta. It also contains short answer questions asking to explain algorithms like merge sort, knapsack problem using greedy approach, Dijkstra's algorithm for single source shortest path, Strassen's matrix multiplication, and all pairs shortest path.

    Copyright:

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

    Daa Question Paper

    Uploaded by

    varsha reddy
    103 views3 pages
    This document contains a 20 question multiple choice exam on algorithms and data structures concepts like knapsack problem, spanning trees, single source shortest path problem, and complexity analysis notations like Big-O and Theta. It also contains short answer questions asking to explain algorithms like merge sort, knapsack problem using greedy approach, Dijkstra's algorithm for single source shortest path, Strassen's matrix multiplication, and all pairs shortest path.

    Original Title

    daa question paper

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document contains a 20 question multiple choice exam on algorithms and data structures concepts like knapsack problem, spanning trees, single source shortest path problem, and complexity analysis notations like Big-O and Theta. It also contains short answer questions asking to explain algorithms like merge sort, knapsack problem using greedy approach, Dijkstra's algorithm for single source shortest path, Strassen's matrix multiplication, and all pairs shortest path.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    103 views3 pages

    Daa Question Paper

    Uploaded by

    varsha reddy
    This document contains a 20 question multiple choice exam on algorithms and data structures concepts like knapsack problem, spanning trees, single source shortest path problem, and complexity analysis notations like Big-O and Theta. It also contains short answer questions asking to explain algorithms like merge sort, knapsack problem using greedy approach, Dijkstra's algorithm for single source shortest path, Strassen's matrix multiplication, and all pairs shortest path.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    You are on page 1of 3

    SRINIVASA INSTITUTE OF TECHNOLOGY AND SCIENCE, KADAPA

    III B.Tech II SEM - I MID Examination March-2020


    Branch: CSE Date: 0-03-2020( )
    Sub: DAA
    Reg. No:
    1.

    Time: 20min. Max.Marks:10 Sign of Invigilator

    Choose the correct answer


    1.In Knapsack problem, the optimized function is_______ profit. [ ]
    A)Minimized B)Maximized C)Both D)None
    2. Feasible solution subset consist of [ ]
    A)input satisfying constraint B)input dissatisfying the constraint C)optimal solutions D)none

    3.Spanning tree of G should have n vertices ___ edges. [ ]


    A)n-2 B)n! C)n-1 D)n*n
    4. _____ problem staring with one vertex and traverse the all vertices and return to [ ]
    Same vetex.
    A) 0/1 Knapsack problem B)Travelling sales man C)Single source shortest path D)ALL
    5.In optimal storage on tapes the programs are stored in_____ permutations. [ ]
    A)n-2 B)n! C)n-1 D)n*n
    6. In _______ method based on rule principle of optimality. [ ]
    A) A)Back tracking B)Dynamic C)Divide-and-conquer D)Greedy
    7._____ formula is used to calculate no.of spanning trees of Connected graph. [ ]
    n-2
    A)n! B)n C)n D)n*n
    8.The computing time of Kruskal’s Algorithm is__ [ ]
    A)O(E log) B)O(nm) C)O(E logn) D)O(E)
    9. ____Tree should not a allow the cycles . [ ]
    A)Binary B)Spanning C)B-tree D)None
    10. The Recurrence relation isT(n)= 9T(n/3)+n then what is the time complexity. [ ]
    A)O(n3) B)O(n logn) C)O(logn) D) O(n2)

    11. Each step of the algorithm must be clear and Unambiguous. [ ]


    A)Finiteness B)Effectiveness C)Definiteness D)Generality
    12.______ notation is used to find the lower bound of a function f(n) [ ]
    A)Big-oh B)Theta C)Omega D)All

    13. An algorithm call itself is called ______________ [ ]


    A)Indirect recursive B)Direct recursive C)Both A& B D)ALL
    14.The best case time complexity of linear search. [ ]
    A)O(n logn) B)O(1) C)O(n) D)O(logn)
    15.___notation is used to find the run time between lower bound to upper bound. [ ]
    A)Big-oh B)Theta C)Omega D)All
    16 .In theta notation ____ constraint to check f(n)=theta(g(n). [ ]
    A )c1g(n)>=g(n)>=c2g(n) B)f(n) <= c*g(n) C)c1g(n)<=g(n)<=c2g(n)D)f(n) ==c*g(n)
    3
    17.In Big oh what is the meaning of O(n ) [ ]
    A) constant B)Linear C)Cubic D)Quadratic

    18. The worst case complexity of quick sort stands when the elements in the array are [ ]
    A) increasing order B ) random order C) decreasing order D)ALL

    19. ._____is the process of executing the correct program on data sets and measuring the [ ]
    Time and space it takes to compute the results.
    A)Profiling B)Analysis C)testing D)Debugging
    20.In space complexity the Sp denotes [ ]
    A)constants B)instance characteristics C)characteristics D)None

    SRINIVASA INSTITUTE OF TECHNOLOGY AND SCIENCE, KADAPA


    III B.Tech II SEM - I MID Examination March-2020
    Branch: CSE Sub: DAA
    Time: 90min. Date: 0-03-2020(N) Max.Marks:30
    Note: Answer any three of the following questions

    1. Write about Merge sort algorithm using example.


    (9,2,5,4,6,8,7,3)
    2. Explain Knapsack problem by using Greedy approach with Example?
    (p1,p2,p3)=(90,100,50) (w1,w2,w3)=(6,8,3) and m=14
    3. Explain Single source shortest path problem in detail using dijikstras algorithm?
    4. Explain in detail about the Stressen’s matrix multiplication using example?
    A= 2 4 B= 2 7
    5 6 8 2

    5.Explain in detail about all pairs shortest path using example?

    You might also like