Ada important question bank

 UNIT 1

  1. Define asymptotic notations. Explain different asymptotic notations with the help of Graphical representations (BL-04, CO-1, PO-1, 2)

  2. Describe the various methods of solving recurrences? Explain them in Brief? (BL-04, CO-1, PO-3)

  3. State the Master’s theorem and explain it with examples? (BL-04, CO-1, PO-4)

  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

  1. 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)

  1. Explain the merge sort method of sorting with example (BL-04, CO-2, PO-1, 2)

  2. Find the minimum spanning tree using Prim’s method for the following graph:(BL-04, CO-2, PO-1)

  3.  Explain optimal storage on tapes and optimal merge patterns.? (BL-04, CO-2, PO-1, 2)






UNIT 3

  1. Write short notes on: (BL-6, (i) Strongly Connected Components    (BL-04, CO-3, PO-1)

  2. 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)

  3. Write short notes on: Travelling salesperson problem? (BL-04, CO-3, PO-1, 2)

  4. Define multistage graph. Find the optimal shortest path for the    following multistage graph. (BL-4, CO-3, PO-1, 2)

UNIT 4

  1. Explain the general method of backtracking and Recursive backtracking with reference to n-queens problem? (BL-04, CO-4, PO-1, 2)

  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)

  3. Write and explain the recursive backtracking algorithm to solve the Hamiltonian cycle problem (BL-04, CO-4, PO-1, 4)

  4. Explain backtracking method of solving graph-coloring problem. (BL-04, CO-4, PO-1, 2)

UNIT 5

  1. Discuss the least cost search method with reference to branch and bound for 4 Queens Problem. (BL-04, CO-5, PO-1,4)

  2. Explain the branch and bound method for solving 15 puzzle problem with least cost search. (BL-04, CO-5, PO-1, 2)

  3. Write notes on cook’s theorem in order to prove NP completeness of Circuit satisfiability problem? (BL-04, CO-5, PO-1, 2)

  4. Write down the differences between P and NP classes.(BL-04, CO-5, PO-1, 2)

Comments

Popular posts from this blog

Huffman coding || Huffman coding with example || Huffman coding method || Huffman coding in c/c++ ||Huffman coding programe in c/c++/data structure /java || what is Huffman coding || Huffman complete,

Unix assignment question

Graphs in data structure, it's algorithm

Java question bank

M-way Trees

Data structure question bank

B Tree

Radix Sort

csa unit 01 part 01 basic of computers notes pdf