Scribd Logo
Upload

Welcome to Scribd!

  • 24 views

    Daa 2022-23

    Uploaded by

    Siddhartha Sikder
    1. The document contains a multiple choice quiz with 15 questions testing knowledge of data structures and algorithms. Topics covered include queues, time complexity, sorting algorithms, graphs, trees, and graph algorithms. 2. It also contains short answer and problem solving questions to be answered for additional points. These include defining terms related to graphs like cliques and distinguishing between graph types, writing graph algorithms like Prim's and Kruskal's, and solving problems involving matrices, knapsacks, finding minimum spanning trees, graph coloring, and NP-complete problems. 3. Students are to attempt the multiple choice section and choose 4 of the short answer/problem solving questions to answer for full credit. This assesses

    Copyright:

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

    Daa 2022-23

    Uploaded by

    Siddhartha Sikder
    24 views3 pages
    1. The document contains a multiple choice quiz with 15 questions testing knowledge of data structures and algorithms. Topics covered include queues, time complexity, sorting algorithms, graphs, trees, and graph algorithms. 2. It also contains short answer and problem solving questions to be answered for additional points. These include defining terms related to graphs like cliques and distinguishing between graph types, writing graph algorithms like Prim's and Kruskal's, and solving problems involving matrices, knapsacks, finding minimum spanning trees, graph coloring, and NP-complete problems. 3. Students are to attempt the multiple choice section and choose 4 of the short answer/problem solving questions to answer for full credit. This assesses

    Original Title

    DAA 2022-23

    Copyright

    © © All Rights Reserved

    Available Formats

    DOC, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    1. The document contains a multiple choice quiz with 15 questions testing knowledge of data structures and algorithms. Topics covered include queues, time complexity, sorting algorithms, graphs, trees, and graph algorithms. 2. It also contains short answer and problem solving questions to be answered for additional points. These include defining terms related to graphs like cliques and distinguishing between graph types, writing graph algorithms like Prim's and Kruskal's, and solving problems involving matrices, knapsacks, finding minimum spanning trees, graph coloring, and NP-complete problems. 3. Students are to attempt the multiple choice section and choose 4 of the short answer/problem solving questions to answer for full credit. This assesses

    Copyright:

    © All Rights Reserved
    Download as DOC, PDF, TXT or read online from Scribd
    Download as doc, pdf, or txt
    24 views3 pages

    Daa 2022-23

    Uploaded by

    Siddhartha Sikder
    1. The document contains a multiple choice quiz with 15 questions testing knowledge of data structures and algorithms. Topics covered include queues, time complexity, sorting algorithms, graphs, trees, and graph algorithms. 2. It also contains short answer and problem solving questions to be answered for additional points. These include defining terms related to graphs like cliques and distinguishing between graph types, writing graph algorithms like Prim's and Kruskal's, and solving problems involving matrices, knapsacks, finding minimum spanning trees, graph coloring, and NP-complete problems. 3. Students are to attempt the multiple choice section and choose 4 of the short answer/problem solving questions to answer for full credit. This assesses

    Copyright:

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

    GROUP A (Attempt 10) (10 X1 =10)

    1. 1.Pick out the following invalidate statement: Queue can be used-


    a) BFS b) DFS c) Both d) None.
    2. 2.The running time of an algorithm T(n) ,where n is the input size is given by
    T(n) = 8 T(n/2 )+ qn if n>1
    = p if n=1 where p & q are the constants. The order of this algorithm is
    a) n^2 b) n^3 c) n^n d) n.
    3. Recharging your mobile balance is ……………….. policy.
    a) FIFO b)LIFO c)PRIORITY BASED d)NONE.
    4. The number of possible ordered trees with 3 nodes A ,B,C is
    a) 16 b) 12 c) 6 d) 10
    5. Which of the following structure is useful in implementing heap sort?
    a) Stack b) Linked list c) Array d) Queue.
    6. Which sort does not used Divide and Conquer methodology?
    a) Quick Sort b) Merge Sort c) Bubble Sort d) None of these.
    7. Time complexity of Dijkstra's algorithm where V is the number of vertices in the graph, is
    a)   O(V^2) b) O(V^3) c) O(v^2) d) none.
    8. Merge sort uses which of the following technique to implement sorting?
    a) backtracking
    b) greedy algorithm
    c) divide and conquer
    d) dynamic programming
    9. What is the average case time complexity of merge sort?
    a) O(n log n)
    b) O(n2)
    c) O(n2 log n)
    d) O(n log n2)
    10. Which of the following is not a type of graph in computer science?
    a) undirected graph
    b) bar graph
    c) directed graph
    d) weighted graph
    11. How many edges will a tree consisting of N nodes have?
    a) Log(N)
    b) N
    c) N – 1
    d) N + 1
    12. How many unique colors will be required for proper vertex coloring of an empty graph
    having n vertices?
    a) 0
    b) 1
    c) 2
    d) n
    13. Which of the following problems can’t be solved using recursion?
    a) Factorial of a number
    b) Nth fibonacci number
    c) Length of a string
    d) Problems without base case
    14. Chan’s algorithm is used for computing _________
    a) Closest distance between two points
    b) Convex hull
    c) Area of a polygon
    d) Shortest path between two points
    15. The Data structure used in standard implementation of Breadth First Search is?
    a) Stack
    b) Queue
    c) Linked List
    d) Tree
    GROUP B (Any four) 5X4=20

    1. Define Clique with example. What are the advantages of graph over tree? 3+2
    2. Write down Prim’s Algorithm or Kruskal’s algorithm 5
    3.Distinguish between Planner Graph and Regular Graph with example. 5
    4. Define the terms degree, vertex, edge, weightage, sub-graph with example. 5
    5. Define with example NP hard NP complete and P complete 5
    6. Find the MST using Kruskal’s Algorithm for the above figure: 5

    Group C (Any Two) 10x2= 20


    1. Explain Strassen’s matrix multiplication and job sequencing problem with an example.
    2. Differentiate 0/1 & fractional knapsack problem with an example.
    3. Find the MST using Dijkstra Algorithm for the following figure:
    Explain graph coloring problem with an example. 5+5
    4. Derive the time complexity of binary search, Quick sort, and Merge sort. 3+3+4
    5. Solve 4 queens’ problem. Write the algorithm for 8 queens’ problem. Solve the travelling
    salesman problem using greedy method. 4+3+3

    You might also like