Scribd
Upload
500 views2 pages

DAA Unit Wise Important Q

The document contains important questions from 5 units: Unit 1 covers algorithms including definition, analysis, representation techniques, recursion, sorting algorithms like merge sort and quicksort. Unit 2 covers set representation using trees and algorithms for operations on sets like union and find. It also includes problems like n-queens and subset sum. Unit 3 is about dynamic programming and covers problems like traveling salesperson, all pairs shortest path, optimal binary search tree, knapsack. Unit 4 includes greedy algorithms, minimum spanning tree algorithms like Prim's and Kruskal's, and single source shortest path. Unit 5 is about NP-hard and NP-complete problems, the satisfiability problem

Uploaded by

MUSHAM HARI KIRAN6737
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
500 views2 pages

DAA Unit Wise Important Q

The document contains important questions from 5 units: Unit 1 covers algorithms including definition, analysis, representation techniques, recursion, sorting algorithms like merge sort and quicksort. Unit 2 covers set representation using trees and algorithms for operations on sets like union and find. It also includes problems like n-queens and subset sum. Unit 3 is about dynamic programming and covers problems like traveling salesperson, all pairs shortest path, optimal binary search tree, knapsack. Unit 4 includes greedy algorithms, minimum spanning tree algorithms like Prim's and Kruskal's, and single source shortest path. Unit 5 is about NP-hard and NP-complete problems, the satisfiability problem

Uploaded by

MUSHAM HARI KIRAN6737
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 2

DAA Unit wise important 

question

 UNIT-I

1.         (a)        Define an algorithm. What are the different criteria that satisfy the algorithm?
(b)   Explain how algorithms performance is analyzed ? Describe asymptotic notation?
2.           What are the different techniques to represent an algorithm? Explain.
3.           Write an algorithm to find the sum of individual digits of a given number.
4.        What is meant by recursion? Explain with example, the direct and indirect recursive
algorithms.
5.          Write an algorithm for Fibonacci series and discuss time complexity.
6.       What is meant by time complexity? Define different time complexity notations? Define
example for one of each?

7.  Write the algorithm for binaryseach.


 8.       Draw the tree of calls of merge sort for the following set.write algorithm.
     (35, 25,15,10,45, 75, 85, 65, 55, 5, 20, 18)
 9.       Sort the given set of elements using Quicksort
     (20, 30, 10, 40, 5, 60, 90, 45, 35, 25, 15, 55)
 10.       Write an algorithm for quick sort by using recursive method. complexity for Quick Sort

11. Explain Strassen is matrix multiplication algorithm with an example.     

UNIT-II

1.         (a)        Explain the set representation using trees.


(b)        Develop the algorithms for the following
i). UNION
ii) FIND
iii) WEIGHTED UNION.
iv)COLLAPSE FIND
 2.         n-queens problem with example algorithm

3. Sum of subsets problem with state space tree and algorithm.


4. Graph coloring state space tree and algorithm.

UNIT-III
1. Solve the tavelling sales person problem using dynamic programming with example.
2. With the help of suitable example Explain all pair shortest path problem.
3. Draw an Optimal Binary Search Tree for n=4 identifiers (a1,a2,a3,a4) = ( do, if, read, while)
P(1:4)=(3,3,1,1) and Q(0:4)=(2,3,1,1,1).
4. Write about 0/1 knapsack problem with example and algorithm
5. How the reliability of a system is determined using dynamic programming? Explain with
example.

UNIT-IV

1.    What is greedy method? Give the control abstraction for greedy method.

2.     What is the solution generated by the function JS when n = 7,


P [1 : 7 ] =(3,5,20,18,1,6,30) and W [1:7 ] = (1,3,4,3,2,1,2)  .write the algorithm
  
3.  Explain, how to find the minimum cost spanning tree by using Prim’s
     And Kruskal’s Algorithm.
4.Explain knapsack problem with example.
5.Write about single source shortest path problem.

UNIT-V

1.                  (a) Write short notes on


i) Classes of NP-hard
ii) Classes of NP-complete
(b) Prove that if NP ≠ CO − NP, then P ≠ NP
   
2.       Distinguish between deterministic and non-deterministic algorithms
      3.        Explain the satisfiability problem?
4.Solve the Travelling Salesman problem using branch and bound algorithms.
5.What are the differences between backtracking and branch and bound solutions?
6. Explain the LC branch and bound algorithm.
7.Explain how branch and bound technique is used to solve 0/1 knapsack problem.
8. Cook’s theorm

You might also like