UNIT 5
BACKTRACKING
Q1) Write short note on backtracking?
A1)
Q2) Explain 8-Queen problem with algorithm?
A2)
Formulation of problem:
Steps to be perform:
Algorithm:
Solution:
putQueen(row)
{
For every position col on the same row
If the position col is available
Place the next queen in position col
If(row<8)
putQueen(row+1)
else success
remove the queen from positioncol
Q3)Analyse the sum of subset with example?
A3)
Step 1: start with an empty set
Step 2: Add element from given list to the set
Step 3: If the set is having sum M then stop with that subset as solution
Step 4: if the set is not feasible then backtracks until we find the solution.
Step 5: If the set is feasible and sum of subset < M then go to step 2
Step 6: if we have visited all numbers given in set without finding suitable solution and if no backtrack is possible then stop.
Example:
Given set of numbers= {1,3,2,4}
Find subsets with sum=3
Step 1: consider an empty set { }
Add 1 into empty set { 1 } (sum=1,1<3)
Add 3 into set {1,3} (sum=4,4>3,backtrack)
Remove 3 from subset { 1 }
Add 2 into set { 1,2 } (sum=3,3=3,found solution)
We remove 2 and check all elements have been considered.
Solution: { } {1} {1, 3}(backtrack) {1} {1,2 }(found) {1}(end)
Q4) Write short note on knapsack problem with example?
A4)
Example:
Let 4 items are given.
W=8
Weight | 2 | 3 | 4 | 5 |
profit | 3 | 5 | 6 | 10 |
Selected weights are: 3 and 5
Maximum profit: 5+10=15
Q5) Analyse the Hamilton Cycle?
A5)
Hamilton path is the path from first vertex to last vertex which visits each vertex exactly once in undirected or directed graph.
Hamilton cycle is the circuit in which there is an edge from the last vertex to first vertex.
In this problem we can determine whether graph contains a Hamilton cycle or not. If the cycle presents then it prints the cycle.
Q6) Analyse Graph Coloring Algorithm with example?
A6)
Steps to color graph:
Step 1: start with coloring single vertex
Step 2: move to its adjacent vertex and use that which is not used by its connecting vertex. If no color is available then backtracks ie. Un-color the last colored vertex and return false
Step 3: Repeat step 2 until all vertices of given graph are colored.
Step 4: if we find the vertex is uncoloured and its adjacent are colored with different colors and no color is available for current vertex then we need more colors ie. Bigger chromatic number.
Example: