1) Discuss optimal merge pattern algorithm in brief. 2) Write a note on decrease and conquer strategy to solve a problem.
[3 marks]Do as directed. 1) Define time complexity. 2) What do you understand by state space tree? 3) Sorting is required to perform binary search. True or False? 4) What is the use of kruskal’s algorithm? 5) Give the limitation of divide and conquer strategy. 6) Give the basic difference between greedy approach and dynamic approach. 7) Which algorithm will run faster? O(logn) or O(n2)?
[7 marks]Write a short note on closest pair algorithm.
[7 marks]What do you mean by asymptotic notation? Explain all the asymptotic notations.
[7 marks]Write a note on single source shortest path algorithm. Explain how it is used to find the shortest path from the source vertex to all the other vertices of the graph.
[7 marks]Solve the following problem to maximize the profit involved after cutting the rod into various pieces with the profits given below. Rod size – 8. Profit for the pieces with lengths(1,2,3,4,5,6,7,8)= (3,5,8,9,10,17,17,20).
[7 marks]Discuss about coin change problem using dynamic programming. Also solve it for making change of Rs 8 having denomination coins of values 1,4,and 6.
[7 marks]Define minimum spanning tree. Explain kruskal’s algorithm to find the minimum spanning tree from a graph. Also explain how union find data structure is used to for kruskal’s algorithm.
[7 marks]Write a note on DFS algorithm.
[7 marks]Write a short note on how to multiply series of matrices so as to decrease the total number of multiplications using dynamic programming approach.
[7 marks]1) Write a note on maximum flow problems. 2) Write a note on limitations of recursion.
[3 marks]Explain how branch and bound technology performs pruning of steps. Also explain 0-1 knapsack algorithm.
[7 marks]Write a note on n-queens problem. Explain it using the example of 4-queens.
[7 marks]What do you mean by N,NP-hard and NP-complete algorithms. Explain all of them using appropriate examples.1
[7 marks]Write a note on Regular expressions. Explain it using example of algorithm to find factorial of a given number.
[7 marks]Compare and contrast - divide and conquer, greedy and dynamic algorithms giving proper criteria and examples.
[7 marks]