Category 21CS42

12. Apply backtracking to the problem of finding a Hamiltonian circuit in the graph shown below: Answer:

11. Define Hamiltonian cycle. Check whether the Hamiltonian cycle exists for the graph given below. Answer:

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 Answer:

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. Answer: The…

8. Apply the branch and bound algorithm to solve the travelling salesman problem for the graph below. Answer:

5. Explain Subset sum problem with suitable example. Answer:

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…

2. Discuss graph coloring problem. Find different solutions for 4 nodes and all possible 3 coloring problem. Answer:

11. Find the optimal tour for sales person using dynamic programming technique for the given graph and its corresponding edge length matrix. Answer:

10. Solve the following travelling sales person problem represented as a graph shown in Fig below using dynamic programming. Answer: