# DAA Unit wise important question

## **UNIT-I**

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

## UNIT II

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

**UNIT-III**

- 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)
- Derive the time complexity for Quick Sort
- Draw the tree of calls of merge sort for the following sets (35, 25,15,10,45, 75, 85, 65, 55, 5, 20, 18)
- Compare Quick sort algorithm performance from insertion sort algorithm.
- Discuss briefly about the randomized quick sort.
- 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)
- Write an algorithm for quick sort by using recursive method
- Explain Strassen is matrix multiplication algorithm with an example.

**UNIT-IV**

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

**UNIT-V**

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