DAA QUESTIONS

• இன்னா செய்தாரை ஒறுத்தல் அவர் நாண நன்னயம் செய்து விடல் (திருக்குறள்)
• Make a wrong doer feel shy, by doing him a favour. (Source: Thirukkural)
• If others harm you, do good unto them, so that they are shamed into realizing their mistakes.

UNIT- I
 
1. What is an algorithm?
2. What are computational procedures?
3. What is a program?
4. Define Algorithm Validation.
5. Define program proving and program verification.
6. Define pseudocode.
7. What are the control structures in pseudocode?
8. Define Recursion. Give an example.
9. Define Time and space complexity.
10. Distinguish performance analysis and performance measurement.
11. What are the components of fixed and variable part in space complexity?
12. Define program step.
13. What are the methods to determine step count?
14. Define input data size.
15. Describe frequency table method.
16. Define best, average and worst case step count.
17. Define break-even point.
18. Define asymptotic notation.
19. Define Big Oh notation.
20. Define Theta notation.
21. Define Omega notation
22. Define little Oh and Little Omega notation.
23. What does O(1) mean?
24. How do you time a very short event?
25. What are the design techniques that are used to devise algorithms?
26. Define recursion. What are its types?
27. Write an algorithm to find if the given no is Armstrong no? Find its time complexity?
28. Differentiate algorithm and program.
29. Find the order of 20n3+100n2+2.

PART B
1. Explain Towers of Hanoi problem and solve it using recursion.
2. Find the time complexity and space complexity of the following problems.
1) Factorial using Recursion.
2) Compute nth Fibonacci Number.
3) Compute xn or exponentiate (x,n).
4) mxn matrix multiplication
5) nxn matrix multiplication
6) mxn matrix addition.
7) Sequential/linear search.
3. Describe best, worst and average case analysis with an example.

UNIT- II

PART A

1. What is divide and conquer technique?
2. Give the control abstraction for divide and conquer technique.
3. Write the recurrence relation for DandC.
4. Timecomplexity of Binary search is O(logn). Justify.
5. Write a straight forward max min algorithm.
6. Explain the greedy method.
7. Define feasible and optimal solution.
8. Write the control abstraction for greedy method.
9. What are the constraints of knapsack problem?
10. What is a minimum cost spanning tree?
11. Specify the algorithms used for constructing Minimum cost spanning tree.
12. State single source shortest path algorithm (Dijkstra's algorithm).
13. Calculate the T(n) for the given recurrence form
T(n) = T(1) if n=1
T(n) = aT(n/b)+f(n) if n>1
where a=2,b=2, T(1)=2, f(n)=n;

PART-B

1. Explain the binary search algorithm with an example.
2. Explain mimmax problem using Divide and conquer technique. Compute its time complexity.
3. Explain merge sort with an example. Compute its time complexity.
4. Explain Quick sort with an example. Give its time complexity.
5. Solve the knapsack problem using greedy technique.
6. Explain Prim's algorithm to construct Minimum cost spanning tree.
7. Explain Kruskal's algorithm to construct Minimum cost spanning tree.
8. Explain Optimal Randomized algorithm to construct Minimum cost spanning tree.
9. Explain single source shortest path algorithm (Dijkstra's algorithm).

UNIT- III

PART – A
1. Define Dynamic programming technique.
2. Define Principle of optimality.
3. What do you mean by Multistage graph.
4. Differentiate the 2 approaches in finding the minimum cost path of multistage graph.
5. Find the minimum cost path using forward and backward technique for the graph given below.
6. Give the conditions to the table in 0/1 knapsack.
7. 0/1 knapsack problem cannot be solved by Greedy technique.Why?
8. Explain briefly about Traveling sales person problem.
9. What are the 3 traversal technique for binary trees.
10. What do you mean by traversal?
11. Give the non recursive algorithm for Triple order traversal.
12. Give the recursive algorithm for Triple order traversal.
13. Define Breadth first search.
14. Define Depth first search.
15. What is breadth first spanning tree? Give and eg.
16. Give the constraints to solve the Traveling sales person problem in dynamic programming.
17. What is 0/1 knapsack problem.
18. Define connected graph. Give an eg.
19. Define Articulation point. Give the condition to identify an articulation point.
20. Identify the articulation points and draw the biconnected components for the graph given below.

PART – B
1. Explain all pairs shortest path algorithm with an eg. Give its time complexity
2. What is multistage graph? Explain with an eg. Write the pseudo code for the finding the minimum cost path using forward approach.
3. What is multistage graph? Explain with an eg. Write the pseudo code for the finding the minimum cost path using backward approach.
4. Write an algorithm for 0/1 knapsack problem.
5. Write and explain an algorithm for BFS and DFS. Give an eg.
6. Give an algorithm to identify articulation points and to construct biconnected components. Explain with an eg.

UNIT- IV

PART – A

1. What are explicit constraints and implicit constraints?
2. Explain 8-Queen problem in brief.
3. What are static trees and dynamic trees?
4. Give any 4 problems that could be solved by backtracking.
5. What are the constraints of 8-Queens problem
6. Define m-colorability optimization problem.
7. What is a Hamiltonian cycle?
8. What are the 2 methods of Branch and bound techniques?
9. Compare and contrast LC-BB and FIFO BB.
10. What is a reduced cost matrix?

PART – B

1. Explain N-Queens problem using Backtracking.
2. Explain Graph Coloring.
3. Explain sum of subsets.
4. Explain Hamiltonian cycles.
5. Solve Knapsack problem using backtracking.
6. Explain Traveling Salesperson problem using branch and bound techniques.

UNIT- V

PART – A

1. What is P and NP?
2. What is deterministic algorithm?
3. What is Non-Deterministic Algorithm?
4. Draw the relationship between P, NP, NP complete and NP-hard.
5. What is the property of NP-Complete problem?
6. What is the property of NP-Hard problem?
7. What are the two most famous unsolved problems in Computer science?

PART – B

1. Explain the basic concepts of P, NP, NP-Complete and NP-Hard.
2. Prove a graph problem is NP-Hard.
3. Explain a NP-Hard Scheduling problem.
4. Explain a NP-Hard code generation problem.
5. Explain the concepts of Approximation algorithm.