Ada important question bank
UNIT 1
Define asymptotic notations. Explain different asymptotic notations with the help of Graphical representations (BL-04, CO-1, PO-1, 2)
Describe the various methods of solving recurrences? Explain them in Brief? (BL-04, CO-1, PO-3)
State the Master’s theorem and explain it with examples? (BL-04, CO-1, PO-4)
Show the operation of heap sort on the following array {4,1,3,2,16,9,10,14,8,7} (BL-04, CO-1, PO-1, 2, 3)
UNIT 2
Find the solution of following knapsack instance:
n=3,W=20,{v1,v2,v3}={60,100,120},{w1,w2,w3)={18,15,10} (BL-04, CO-2, PO-3,6)
Explain the merge sort method of sorting with example (BL-04, CO-2, PO-1, 2)
Find the minimum spanning tree using Prim’s method for the following graph:(BL-04, CO-2, PO-1)
Explain optimal storage on tapes and optimal merge patterns.? (BL-04, CO-2, PO-1, 2)
UNIT 3
Write short notes on: (BL-6, (i) Strongly Connected Components (BL-04, CO-3, PO-1)
Identify an optimal parenthesization of a matrix chain product whose sequence of dimensions is {5, 4, 2, 6, 7} (BL-04, CO-3, PO-2)
Write short notes on: Travelling salesperson problem? (BL-04, CO-3, PO-1, 2)
Define multistage graph. Find the optimal shortest path for the following multistage graph. (BL-4, CO-3, PO-1, 2)
UNIT 4
Explain the general method of backtracking and Recursive backtracking with reference to n-queens problem? (BL-04, CO-4, PO-1, 2)
Write the recursive algorithm for sum of subsets problem. Draw a state space search tree for following problem to find the answer state:-W= {5, 10, 12, 13, 15, 18} and M=30 (BL-04, CO-4, PO-1,3)
Write and explain the recursive backtracking algorithm to solve the Hamiltonian cycle problem (BL-04, CO-4, PO-1, 4)
Explain backtracking method of solving graph-coloring problem. (BL-04, CO-4, PO-1, 2)
UNIT 5
Discuss the least cost search method with reference to branch and bound for 4 Queens Problem. (BL-04, CO-5, PO-1,4)
Explain the branch and bound method for solving 15 puzzle problem with least cost search. (BL-04, CO-5, PO-1, 2)
Write notes on cook’s theorem in order to prove NP completeness of Circuit satisfiability problem? (BL-04, CO-5, PO-1, 2)
Write down the differences between P and NP classes.(BL-04, CO-5, PO-1, 2)
Comments
Post a Comment