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)
3) Explain the algorithm design and analysis process
4) Prove the following theorem if t1(n) ϵO((g1(n)) and t2(n) ϵ O(g2(n)) then t1(n)+ t2(n) ϵ O(max{g1(n),g2(n}).
5) The factorial function n! has value 1when n<=1 and value n *(n-1)! When n is >1. Write both a recursive and iterative algorithm to compute n!
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 , 22n , 0.001n4 +3n3 +1, ln2 n, 3 √n, 3n
Solution
(n-2)!= Theta(n!)
5 log (n+100)10 = theta(log n())
22n = theta(4n )
0.001n4 +3n3 +1 =theta(n4 )
ln2 n =theta(log2 n )
3 √n =Theta(n 1/3 )
3n =theta(3n)
7) Write an algorithm to find the uniqueness of elements in an array and give the mathematical analysis of this non-recursive algorithm with all steps.
8) Define algorithm with a specification of the writing algorithm
9) Write Tower of Hanoi algorithm and steps for analysis of recursive algorithm. Show the analysis of above algorithm.
10) Explain with example how the count variable is introduced in the program to find the number of steps required by a program to solve the problems.
11) Write an algorithm to find max element in the array of n elements. Give mathematical analysis of this algorithm.
12) Explain the general plan for analyzing the efficiency of recursive algorithm. Write the algorithm to find factorial of a given number. Derive its efficiency.
13) What are the various basic efficiency classes? Explain Big O, Big Omega and Big Theta asymptotic notations.
14) Write an algorithm for Selection sort, trace its working for the given elements and also analyze its efficiency.
89 45 68 90 29 34 17
15) Explain Brute Force String matching problem with an example. Write an algorithm for same and analyze its efficiency.
16) Design an algorithm for performing sequential / linear search and compute best case, worst case, and average case efficiency.
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:
4) State Master Theorem. Solve the recurrence relation using Master Theorem
5) Design an algorithm for performing merge sort. Analyze its time efficiency; apply the same to sort the following number.
6) Design an algorithm for performing quick sort . Apply the same to solve the following set of numbers : 5 3 1 9 8 2 4 7
7) Sort the following keyword A,L,G,O,R,I,T,H,M by applying Quicksort method
8) Apply quick sort algorithm to sort the list E,X,A,M,P,L,E in alphabetical order. Draw tree of recursive calls made
9) List the advantages and disadvantages of divide and conquer
10) Explain the concept of divide and conquer . Write recursive algorithm to perform binary search on list of elements
11) Compare straight forward method and divide and conquer method of finding max and min element of the list
12) Show the number of elements comparison with example and proof of Binary search for Average, best and worst time case analysis.
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.
15) Design an algorithm for performing insertion sort. Analyze its time efficiency; apply the same to sort the following number. 89 45 68 90 29 34 17
16) Design an algorithm for DFS and BFS traversal methods. Comment on its efficiency. Apply the same for the given graph
17) Differentiate between DFS and BFS
18) Apply topological sort on the following graph using source removal and DFS based methods
MODULE 3
Write an algorithm to solve knapsack problem using greedy technique. Find the optimal solution to the knapsack instance n=7, m=15.
(P1, P2, ………,P7) = (10,5,15,7,6,18,3)
(W1,W2,…….,W7)=(2,3,5,7,1,4,1)
2. Apply prim’s algorithm and kruskal’s algorithm method to find the minimum cost spanning tree to graph shown below
3. Write an algorithm to solve single source shortest path problem. Apply the algorithm to the graph shown below
4. Define heap. Write bottom-up construction algorithm. Construct heap for the list 1,8,6,5,3,7 using bottom-up algorithm and successive key insertion method
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. Construct a Huffman code for the following data.
Encode the text ABACABAD and decode 100010111001010.
8. Calculate the shortest distance and shortest path from vertex 5 to vertex 0 using Dijkstra’s algorithm
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
12. Explain the greedy criterion. Apply greedy method for the following instance of knapsack problem. Capacity of knapsack (M) = 5.
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
1 Explain the general procedure to solve a multistage graph problem using backward approach with an example
2. Explain multistage graph problem with example. Write an algorithm for multistage graph problem using forward approach
3. Solve multistage graph problem using forward approach for the given graph consider vertex 1 as the source and vertex 12 as sink
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.
8. Define transitive closure of a graph. Write Warshall’s algorithm to compute transitive closure of a directed graph. Apply the same on the graph defined by the following adjacency matrix:
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
10. Solve the following travelling sales person problem represented as a graph shown in Fig below using dynamic programming.
11. Find the optimal tour for sales person using dynamic programming technique for the given graph and its corresponding edge length matrix.
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
Construct state space tree for solving four queens problem using backtracking
2. Discuss graph coloring problem. Find different solutions for 4 nodes and all possible 3 coloring problem.
3. Write a note on (i) Non deterministic algorithms (ii) LC branch and bound solution to solve 0/1 knapsack problem.
4. What are the two additional items required by Branch and Bound technique compared with backtracking. Solve the following assignment problem using branch and bound technique whose cost matrix for assigning four jobs to four persons are given.
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 ?
8. Apply the branch and bound algorithm to solve the travelling salesman problem for the graph below.
9. Apply backtracking technique to solve the below instance of the subset sum problem.
S={1,3,4,6} d=7
S={5, 10, 12, 13, 15, 18} d=30
10. How the branch and bound technique is different from backtracking? Solve the following instance of knapsack problem using Branch and Bound technique. Give knapsack capacity = 10.
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
