Category solved model papers

Explain the general procedure to solve a multistage graph problem using a backward approach with an example. Answer: A multistage graph problem is to find the shortest path from a…

Explain multistage graph problem with example. Write an algorithm for multistage graph problem using forward approach. Answer: A multistage graph problem is to find the shortest path from a source…

Q. Explain N-Queen problem with example (or) Q. With the help Of State Space tree, solve the 4-queens problem by using backtracking approach The problem is to place n queens…

Solve multistage graph problem using forward approach for the given graph consider vertex 1 as the source and vertex 12 as sink. Answer:

Design Floyd’s algorithm to find the shortest distances from all nodes to all other nodes. Answer: Example:

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

Q. 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:…

Explain the greedy criterion. Apply greedy method for the following instance of knapsack problem. Capacity of knapsack (M) = 5. Answer:- Greedy Criterion: By selecting items with the highest value-to-weight ratio,…

Write an algorithm to solve the 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) Answer:-…