a) Explain the working principle of merge sort algorithm.
b) Sort the following list of elements using merge sort: 23, 35, 12, 4, 67, 5, 9, 11, 80, 32.
a) What is a spanning tree? Explain Prim's algorithm to find the minimum spanning tree of a graph.
--- Content provided by FirstRanker.com ---
b) Find the minimum spanning tree for the following graph using Prim's algorithm.
a) Write an algorithm to find the shortest path using Dijkstra’s algorithm.
b) Explain the difference between Dynamic programming and Greedy method.
--- Content provided by FirstRanker.com ---
a) What is the 0/1 Knapsack problem? Write the algorithm for solving 0/1 Knapsack problem using dynamic programming.
b) Find an optimal solution to the knapsack instance n=7, m=15 (p1, p2, ...p7)=(10, 5, 15, 7, 6, 18, 3) and (w1, w2, ...w7) = (2, 3, 5, 7, 1, 4, 1)
a) Explain the sum of subset problem and write the algorithm for it using backtracking.
b) Let W = {5, 10, 12, 13, 15, 18} and m = 30. Find all possible subsets of ‘w’ that sum to ‘m’ using backtracking algorithm.
--- Content provided by FirstRanker.com ---
a) Describe the N-Queen’s problem and explain the algorithm to solve it using backtracking.
b) Solve 4-Queen problem using backtracking approach.
a) Explain NP-Hard and NP-Complete problems.
--- Content provided by FirstRanker.com ---
b) Write short notes on the following:
- i) Cook’s theorem
- ii) Traveling sales person problem
Visit FirstRanker.com for more question papers.
--- Content provided by FirstRanker.com ---