Unit 5 - Previous Questions
Backtracking
N-Queens Problem
Compare Backtracking and Branch-and-Bound programming techniques.
What is backtracking? Explain how it can be used to solve the n-Queens problem, and obtain one solution for the 4-Queens problem using a state space tree.
Explain the Backtracking algorithm and apply it to solve the 4-Queens problem
Apply Backtracking to find all possible solutions to the 4-Queens problem.
Hamiltonian Circuit Problem
Define a Hamiltonian Circuit.
Compare Brute Force and Backtracking methods for finding Hamiltonian circuits in a graph.
Apply Backtracking to find all possible solutions to the Hamiltonian circuit problem. (2023 Sep, Fig 7)
Apply Backtracking to the problem of finding a Hamiltonian circuit in the given graph. (2021 Sep, Fig 13)
Illustrate how Backtracking can be applied to a given graph to find a Hamiltonian Circuit. (2021 Sep, Fig 16)
Subset-Sum Problem
Solve the Subset-Sum problem using Backtracking. Draw the state-space tree for the instance: S={3,5,6,7}, d=15
Solve the Subset Sum problem using Backtracking for the instance: S={1,2,5,6,8}, d=9
Apply Backtracking to solve the following instance and construct the state-space tree: S={1,3,4,5}, d=11
Branch-and-Bound
Knapsack Problem
- Find the maximum profit using Branch and Bound for the following instance of knapsack problem: W=16
| Item | Weight | Value |
|---|---|---|
| 1 | 10 | $100 |
| 2 | 7 | $63 |
| 3 | 8 | $56 |
| 4 | 4 | $12 |
- Solve using Branch-and-Bound for the following instance: W=15
| Item | Weight | Value |
|---|---|---|
| 1 | 5 | $40 |
| 2 | 7 | $35 |
| 3 | 2 | $18 |
| 4 | 4 | $4 |
| 5 | 5 | $10 |
| 6 | 1 | $2 |
- Apply Branch and Bound technique to the following instance: W = 15
| Item | Weight | Value |
|---|---|---|
| 1 | 2 | $18 |
| 2 | 5 | $40 |
| 3 | 7 | $35 |
| 4 | 4 | $12 |
| 5 | 1 | $2 |
| 6 | 4 | $4 |
- Solve the following Knapsack instance using Branch and Bound. W = 16
| Person | Item | Weight | Value |
|---|---|---|---|
| A | 1 | 10 | $100 |
| B | 2 | 7 | $63 |
| C | 3 | 8 | $56 |
| D | 4 | 4 | $12 |
Traveling Salesman Problem
Solve the Traveling Salesman Problem using Branch and Bound. (2024 Sep, Fig 3)
Find the optimal route using Branch and Bound for the cost matrix:
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 2 | 5 | 7 |
| B | 2 | 0 | 8 | 3 |
| C | 5 | 8 | 0 | 1 |
| D | 7 | 3 | 1 | 0 |
| Person | Job1 | Job2 | Job3 | Job4 |
|---|---|---|---|---|
| A | 9 | 2 | 7 | 8 |
| B | 6 | 4 | 3 | 7 |
| C | 5 | 8 | 1 | 8 |
| D | 7 | 6 | 9 | 4 |
P, NP-Completeness, and Approximation Algorithms
P and NP Problems, NP-complete Problems
Write a short note on P, NP, NP-complete, and NP-hard problems.
Define the following:
i) Tractable Problem
ii) NP-complete Problems
iii) Feasible Solution
Approximation Algorithms
Discuss two approximation algorithms used to solve the Traveling Salesman Problem.
Discuss approximation algorithms used for solving the Knapsack Problem.