Define the following terms: 1. Optimum solution 2. Greedy method for problem solving 3. Dynamic programming 4. Spanning tree 5. Recursion 6. Time complexity 7. Branch and Bound
[7 marks]What is divide and conquer technique? Explain in context of binary search method. Also give its time complexity.
[7 marks]Explain the characteristics of greedy algorithms. Differentiate between greedy algorithms and dynamic programming methods.
[7 marks]Write a brief note on NP complete and the classes P, NP and NPC.
[7 marks]Differentiate between DFS and BFS with suitable examples.
[7 marks]Explain the knapsack problem. Consider the following: n = 3, M = 20, P = [25, 24, 15], W = [18,15,10]. Find the optimal solution is terms of maximized profit.
[7 marks]Define Order notation. Explain the use of it. List the various order notations and explain Big-Oh and small-oh notations in detail.
[7 marks]What are minimum spanning trees? Explain with a suitable example Kruskal’s method to find minimum spanning tree.
[7 marks]Explain rod cutting problem using a suitable example.
[7 marks]What is recurrence relation? Solve the recurrence equation T(n) = T (n-1) + n using forward substitution and backward substitution method.
[7 marks]Explain Multistage graph problem using Dynamic programming. OR1
[7 marks]Explain Maximum flow problem using Dynamic programming.
[7 marks]Discuss assembly line scheduling problem using dynamic programming with suitable example.
[7 marks]Explain backtracking method of problem solving. What is 8-Queen’s problem? Solve the 4-Queen’s problem using the backtracking method.
[7 marks]Sort the following data using insertion sort: A, L, G, O, R, I, T, H, M
[7 marks]Q.5. (a) Write notes on the following: 1. Branch and Bound 2. Hamiltonian cycles 3. M-colouring problem
[7 marks]Sort the following data using bubble sort: Mon, Tues, Wed, Thur, Fri, Sat, Sun
[7 marks]