**21CS42 – Design and Analysis of Algorithm – DAA Solved Previous year question papers – PYQ’s **

#### MODULE – 1

**1) What is an algorithm? Explain the criteria/properties to be satisfied by the algorithm **

2)

**What does the Algorithm compute ………………………………….…………10M****What is its input size****What is its basic operation****How many times is the basic operation executed****What is the efficiency class of this algorithm**

**3) Explain the algorithm design and analysis process**

6) List the following functions according to their order of growth from lowest to highest. State proper reasons,

(n-2)! , 5 log (n+100)^{10}, 2^{2n }, 0.001n^{4} +3n^{3}+1, ln^{2 }n, ^{3}√n, 3^{n}

__Solution__

(n-2)!= Theta(n!)

5 log (n+100)^{10 }= theta(log n())

2^{2n } = theta(4^{n })

0.001n^{4} +3n^{3}+1 =theta(n^{4 } )

ln^{2 }n =theta(log^{2 }n )

^{3}√n =Theta(n ^{1/3} )

3^{n } =theta(3^{n) }

**8) Define algorithm with a specification of the writing algorithm**

89 45 68 90 29 34 17

#### Module 2

1) **Explain divide and conquer technique with general algorithm with control abstract**.

2) Write the control abstract for divide and conquer technique.

3) Solve the following recurrence relations:

(i) T(n)=2T(n/2)+1 (ii) T(n)=T(n-1)+cn

4) State Master Theorem. Solve the recurrence relation using Master Theorem

(i)T(n)=2T(n/2) + c n (ii) T(n)=2T(n/2)+1

7) **Sort the following keyword A,L,G,O,R,I,T,H,M by applying Quicksort method**.

9) **List the advantages and disadvantages of divide and conquer**.

13) **Develop a recursive algorithm to find max and min element from the list. Illustrate with an Example**.

14) Explain the decrease and conquer technique with its variations.

17) **Differentiate between DFS and BFS**.

18) Apply topological sort on the following graph using source removal and DFS based methods

#### MODULE 3

(P1, P2, ………,P7) = (10,5,15,7,6,18,3)

(W1,W2,…….,W7)=(2,3,5,7,1,4,1)

5. Find the optimal solution to the knapsack instant n=7, m=15 using greedy method.

6. **Find the minimum spanning tree using Kruskal’s algorithm**.

7. C**onstruct a Huffman code for the following data.**

**Encode the text ABACABAD and decode 100010111001010. **

9. State job sequencing with deadline problem. Find the solution generated by job sequencing problem for 7 jobs given profits 3,5,20,18,1,6,30 and deadlines 1,3,4,3,2,1,2 respectively.

10. **Obtain a minimum cost-spanning tree for the graph below using Prim’s algorithm**.

11. **Sort the given list of number using Heap sort**.

13. **Construct a Huffman code for the following data and encode the test BADEC**

14. **Solve the below instance of single source shortest path problem with vertex “a” as the source**

15. Apply Prim’s and Kruskal’s algorithm to the following instance to find minimum spanning tree.

16. Sort the below given lists by heapsort using the array representation of heaps.

- 3,2,4,1,6,5
- 3,4,2,1,5,6
- H,E,A,P,S,O,R,T

#### Module 4

4. Write an algorithm for optimal binary search tree. Construct an optimal binary search tree for the following:

Items | A | B | C | D |

Probabilities | 0.1 | 0.2 | 0.4 | 0.3 |

5. **Design Floyd’s algorithm to find shortest distances from all nodes to all other nodes**.

6. **Apply Floyd’s algorithm to find all pair shortest path for the given graph**.

**7. Apply Warshall’s algorithm to compute transitive closure for the graph below.**

**9. Using Dynamic Programming solve the below instance of knapsack problem. Capacity W=5**

Item | Weight | Value |

1 | 2 | 12 |

2 | 1 | 10 |

3 | 3 | 20 |

4 | 2 | 15 |

12. Write an algorithm for Bellman Ford. Find the shortest path from node 1 to every other node in the graph using Bellman Ford algorithm.

13. Explain the concept of negative weight cycle in a directed graph.

14. Explain sorting by counting.

15. Write an algorithm and explain input enhancement in string matching using Harspool’s algorithm.

#### Module 5

3. Write a note on (i) Non deterministic algorithms (ii) LC branch and bound solution to solve 0/1 knapsack problem.

**5. Explain Subset sum problem with suitable example. **

6. Explain the classes of NP hard and NP complete.

7. What is Hamiltonian circuit problem? What is the procedure to find Hamiltonian circuit of a graph ?

**9. Apply backtracking technique to solve the below instance of the subset sum problem.**

**S={5, 10, 12, 13, 15, 18} d=30**

**11. Define Hamiltonian cycle. Check whether the Hamiltonian cycle exists for the graph given below.**

**12. Apply backtracking to the problem of finding a Hamiltonian circuit in the graph shown below:**

13. Define the following (08 Marks)

- Class P
- Class NP
- NP Complete problem
- NP Hard problem