Backtracking 40 Page
Backtracking 40 Page
Backtracking 40 Page
QUESTION BANK
UNIT-IV
SUB CODE: CS2251
DEPT: CSE
SEM/YEAR: III/ II
PART A (2 Marks)
1. What is the difference between explicit constraints and implicit constraints?(AUC MAY
2010/ MAY 2012 / DEC 2012 / DEC 2013)
Implicit constraints are constraints that will be satisfied by the manner in which
the branch-bound algorithm is constructed.
Explicit constraints, however, are defined to be constraints that will require
procedures for recognition as an integral part of the branch- and bound
algorithm.
2. What is the difference between a Live Node and a Dead Node?
The m- coloring problem concerns finding all ways to color an undirected graph using
at most m different colors, so that no two adjacent vertices are the same color.
We usually call the m- Coloring Problem a unique problem for each value of m.
5. What is Hamiltonian path?
M.AARTHI
Page 1
A graph is called planar if it can be drawn in a plane in such a way that no two
edges cross each other.
7. What do you mean by chromatic number of the graph? Define the chromatic number of a
graph.
needed to color G (i.e) ( the smallest k such that there exists a coloring C for G and |C(
V)| =K
8. Draw a graph with a cycle but no Hamiltonian cycle.
The general method of Backtracking assumes that all answer nodes have to be
found.
Let (x1,x2,,xi) be a path from root node to a problem state.
Let (x1,x2,,xi) represent the set of all possible values for(xi+1) Such that (x1,x2,,xi+1)
is a path of problem state.
Bi+1is a bounding function such that,Bi+1(x1,x2,,xi+1) is false if that path does not lead
to an answer state and hence backtracking to the previous node is done.
Page 2
Map is transformed into a graph. Each region of the map becomes a node. If the two
regions are adjacent in the map, then the corresponding nodes are joined by an
edge.
13. What is backtracking?
Find a solution by trying one of several choices.
If the choice proves incorrect, computation backtracks or restarts at the point of
choice and tries another choice.
It is often convenient to maintain choice points and alternate choices using
recursion.
14. What is 8-queens problem?
It is a classic combinatorial problem that place eight queens on
an 8 x 8
chessboard so that no two attack, i.e., no two of them are on the same row,
column, or diagonal.
15. What is solution space?
Tuples that satisfy the explicit constraints define a solution space.
The solution space can be organized into a tree.
16. What is bounding function?
Bounding function is a function used to kill live nodes without generating all their
children.
17. What are the different ways of tree organization?
Backtracking
Backtracking is depth first node generation with bounding functions.
Branch- and -bound
Branch- and bound is a state generation method in which E-node
remains E-node until is dead.
18. State if backtracking always produces optimal solution.
Backtracking always produces optimal solution since backtracking is a
systematic way to go through all the possible configurations of a solution space
for the problem instance.
19. What are the four factors considered for finding efficiency of the backtracking algorithm?
Time to generate the next xk
Number of xk satisfying the explicit constraints.
Time for the bounding function Bk
Number of xk satisfying Bk
M.AARTHI
Page 3
M.AARTHI
Page 4
Write down and explain the procedure for tackling the 8 queens problem using a
Backtracking approach. (16)
M.AARTHI
Page 5
M.AARTHI
Page 6
This shows how effective the backtracking approach of generating the state space tree
compared to the complete state space tree comprising of 69,281 nodes.
2. With an example, explain Graph Coloring Algorithm. (16)
Explain the algorithm for finding all m-colorings of a graph.(16)
M.AARTHI
Page 7
M.AARTHI
Page 8
M.AARTHI
Page 9
M.AARTHI
Page 10
M.AARTHI
Page 11
M.AARTHI
Page 12
M.AARTHI
Page 13
M.AARTHI
Page 14
M.AARTHI
Page 15
M.AARTHI
Page 16
M.AARTHI
Page 17
M.AARTHI
Page 18
M.AARTHI
Page 19
M.AARTHI
Page 20
5. Write an algorithm to determine the Sum of Subsets for a given Sum and a set of
numbers. Draw the tree representation to solve the subset sum problem given the
numbers set as {3, 5, 6, 7, 2} with the sum=15. Derive all the subsets. (16)
(AUC DEC 2010)
Explain subset-sum problem and discuss the possible solution strategies using
backtracking.(16)
M.AARTHI
Page 21
M.AARTHI
Page 22
M.AARTHI
Page 23
M.AARTHI
Page 24
6. Write an algorithm to determine Hamiltonian cycle in a graph using backtracking. For the
following graph determine the Hamiltonian cycle.
C
C
D
D
(or) Explain Hamiltonian cycles. (8)
E
E
M.AARTHI
Page 25
M.AARTHI
Page 26
7. Using
backtracking,
find
the
optimal
solution
to
knapsack
problem
for
the knapsack instance n = 8, m = 110, (p1, p2. ... p7) = (11, 21, 31, 33, 43,
53, 55, 65) and (w1, w2,...,w7) = (1, 11, 21, 33, 43, 53, 55, 65).(16)
M.AARTHI
Page 27
M.AARTHI
Page 28
8. Write an algorithm for N QUEENS Problem and Trace it for n=6. (16) (AUC MAY 2011)
M.AARTHI
Page 29
M.AARTHI
Page 30
M.AARTHI
Page 31
M.AARTHI
Page 32
M.AARTHI
Page 33
M.AARTHI
Page 34
M.AARTHI
Page 35
M.AARTHI
Page 36
M.AARTHI
Page 37
9. How does backtracking work on the 8 Queens problem with suitable example? (8)
(AUC DEC2011)
M.AARTHI
Page 38
M.AARTHI
Page 39
(AUC DEC2011)
M.AARTHI
Page 40