Scribd Logo
Upload

Welcome to Scribd!

  • 148 views

    Midsem 2 Important Questions

    Uploaded by

    shubh agrawal
    The document contains 15 important questions for a mid-term exam. The questions cover topics such as Floyd-Warshall algorithm, knapsack problem, Dijkstra's algorithm, dynamic programming, multistage graphs, backtracking, Hamiltonian cycles, graph coloring, branch and bound, traveling salesperson problem, binary search, 2-3 trees, complexity classes (P, NP, NP-complete, NP-hard), AVL trees, and B-trees. The questions involve solving problems, explaining concepts, writing algorithms, and constructing tree data structures.

    Copyright:

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

    Midsem 2 Important Questions

    Uploaded by

    shubh agrawal
    148 views2 pages
    The document contains 15 important questions for a mid-term exam. The questions cover topics such as Floyd-Warshall algorithm, knapsack problem, Dijkstra's algorithm, dynamic programming, multistage graphs, backtracking, Hamiltonian cycles, graph coloring, branch and bound, traveling salesperson problem, binary search, 2-3 trees, complexity classes (P, NP, NP-complete, NP-hard), AVL trees, and B-trees. The questions involve solving problems, explaining concepts, writing algorithms, and constructing tree data structures.

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document contains 15 important questions for a mid-term exam. The questions cover topics such as Floyd-Warshall algorithm, knapsack problem, Dijkstra's algorithm, dynamic programming, multistage graphs, backtracking, Hamiltonian cycles, graph coloring, branch and bound, traveling salesperson problem, binary search, 2-3 trees, complexity classes (P, NP, NP-complete, NP-hard), AVL trees, and B-trees. The questions involve solving problems, explaining concepts, writing algorithms, and constructing tree data structures.

    Copyright:

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

    Midsem 2 Important Questions

    Uploaded by

    shubh agrawal
    The document contains 15 important questions for a mid-term exam. The questions cover topics such as Floyd-Warshall algorithm, knapsack problem, Dijkstra's algorithm, dynamic programming, multistage graphs, backtracking, Hamiltonian cycles, graph coloring, branch and bound, traveling salesperson problem, binary search, 2-3 trees, complexity classes (P, NP, NP-complete, NP-hard), AVL trees, and B-trees. The questions involve solving problems, explaining concepts, writing algorithms, and constructing tree data structures.

    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 2

    Mid-term 2 Important Questions

    Q1. Using Floyd Warshall Algorithm solve the all pair shortest path problem for the
    graph. Where weight matrix is given below :-

    0 ∞ 3 ∞
    2 0 ∞ ∞
    ∞ 7 0 1
    6 ∞ ∞ 0

    Q2. Solve the following 0/1 Knapsack Problem using Dynamic Programming .The
    Capacity of Knapsack W is 10?

    Item 1 2 3 4

    Weight 4 7 5 3

    Value 40 42 25 12

    Q3. Find the shortest path from vertex 1 to vertex 5 in the following weighted graph
    using Dijkstra’s greedy algorithm.

    Q4. Find a minimum cost path from‘s’ to‘t’ in multistage graph using dynamic
    programming using backward approach.

    4
    A D
    1 18
    11 9

    2 5 13
    S B E T
    16 2

    5
    C 2
    F
    Q5. . Explain Multistage? Discuss its Application and reliability design with Example.

    Q6.What is Backtracking? Find the solution to the 4-Queen problem using backtracking
    strategy?
    Q7. What do you understand by Hamiltonian cycles? Write an algorithm to find all
    Hamiltonian cycles in a given graph using backtracking and determine the complexity
    also.
    Q8. Explain Graph Coloring problem with their complexity?

    Q9. Define Branch and Bound Method?

    Q10. Consider the traveling salesperson instance defined by the cost matrix. Obtain the
    reduced cost matrix and solve it

     20 30 10 11

    15  16 4 2

    3 5  2 4

    19 6 18  3

    16 4 7 16 

    Q11. Apply Binary search to find 123 in a


    list45,96,105,121,145,192,199,205,245,275,123,850,905

    Q12. What is 2-3 trees? Write characteristic of 2-3 trees?

    Q13. Discuss the relationship between class P,NP,NP-complete and NP-hard problems
    with suitable example of each class?

    Q14. Construct an AVL tree for the following list {5, 6, 8, 3, 2, 4, 7} by inserting the
    elements successively, starting with empty tree.

    Q15. Construct a B-tree of order of 5 elements 1 7 6 11 4 8 13 10 5 19 9 18 24 3 12 14 20 21


    16 and delete 8 18 16 4?

    You might also like