# DAA Unit wise important question

## UNIT-I

1. Define an algorithm. What are the different criteria that satisfy the algorithm
2. Explain how algorithms performance is analyzed ? Describe asymptotic notation?
3.   What are the different techniques to represent an algorithm? Explain.
4.   Give an algorithm to solve the towers of Hanoi problem.
5. Write an algorithm to find the sum of individual digits of a given number.
6. Explain the different looping statements used in pseudo code conventions.
7. What is meant by recursion? Explain with example, the direct and indirect recursive algorithm.
8. List the advantages of pseudo code convention over flow charts.
9. Write an algorithm for Fibonacci series and discuss time complexity.
10. Write about the two methods to calculate time complexity worth case.
11. What is meant by time complexity? Define different time complexity notations?

## UNIT II

1. Explain the set representation using trees
2. Give the trees for the set { 1, 2, 3, 4, 5, … n} by using weighting rule
3. Give an algorithm for implementation of union instruction using linked list and explain its implementation.
4.   Write a short note on spanning trees.
5. What are connected and bi – connected components? Explain with suitable example.
6. Write a pseudo code for the implementation of UNION instruction using linked list. Explain the working of the implementation.
7. Explain the usefulness of the following fundamental operations in sets i). MIN ii) DELETE iii) FIND iv) INSERT

## UNIT-III

1. Draw the binary decision tree for the following set (3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 4)
2.  Derive the time complexity for Quick Sort
3. Draw the tree of calls of merge sort for the following sets (35, 25,15,10,45, 75, 85, 65, 55, 5, 20, 18)
4. Compare Quick sort algorithm performance from insertion sort algorithm.
5. Discuss briefly about the randomized quick sort.
6. Draw the tree of calls of merge for the following set of elements. (20, 30, 10, 40, 5, 60, 90, 45, 35, 25, 15, 55)
7. Write an algorithm for quick sort by using recursive method
8. Explain Strassen is matrix multiplication algorithm with an example.

## UNIT-IV

1. Present a Greedy Algorithm for Sequencing Unit Time Jobs with deadlines and profits.
2. What is greedy method? Explain with example.
3.  Give the control abstraction for greedy method.
4. Present an optimal Randomized algorithm for minimum cost spanning trees.
5.  What are the observation that should made for finding the shortest by using Greedy
6.  Explain, how to find the minimum cost spanning tree by using Prim’s Algorithm.
7. Define minimum cost spanning trees. Explain them with suitable example.
8. Explain about spanning tree and write Kruskal’s algorithm and explain it with following graph?

## UNIT-V

1. Write short notes on i) Classes of NP-hard ii) Classes of NP-complete Distinguish between deterministic and non-deterministic algorithms.
2.  Explain the satisfiability problem?
3. Defination of NP-hard Problem.
4. Defination of NP-complete Problem.
5. What is LIFO and FIFO search?
6. Travelling Salesman Problem