Short Questions and Answers
(2 Marks )
Prepared By,
Mr. S. P. Santhoshkumar M.E.,
Assistant Professor,
Department of CSE.
UNIT V –DYNAMIC PROGRAMMING AND BACKTRACKING
1. Define Graph.
A graph G consist of a nonempty set V which
is a set of nodes of the graph, a set E which is the set of edges of the graph, and a mapping from the set
for edge E to a set of pairs of elements of V. It can
also be represented as G=(V, E).
2. What is meant by strongly and Weekly connected
in a graph?
An undirected graph is connected, if there is a path from every vertex to
every other vertex. A directed graph with this property is called strongly
connected.
When a directed graph is not strongly connected but the underlying graph is
connected, then the graph is said to be weakly connected.
3. List the two important key points of depth
first search.
i) If
path exists from one node to another node, walk across the edge – exploring
the
edge.
ii)
If path does not exist from one specific node to any other node, return to the
previous
node where we have been before – backtracking.
4. What do you mean by breadth first search
(BFS)?
BFS performs simultaneous explorations starting from a
common point and
spreading out independently.
5. Differentiate BFS and DFS.
No.
|
DFS
|
BFS
|
1.
|
Backtracking
is possible from a
dead
end
|
Backtracking
is not possible
|
2.
|
Vertices
from which exploration is
incomplete are processed in a
LIFO order
|
The
vertices to be explored are organized as a
FIFO
queue
|
3.
|
Search
is done in one particular
Direction
|
The
vertices in the same level are maintained
parallely
|
6. What do you mean by articulation point?
If a graph is not biconnected, the vertices whose removal would disconnect
the
graph
are known as articulation points.
7.
What is a state space tree?
The processing of backtracking is
implemented by constructing a tree of choices being made. This is called the
state-space tree. Its root represents a initial state before the search for a
solution begins. The nodes of the first level in the tree represent the choices
made for the first component of the solution, the nodes in the second level
represent the choices for the second component and so on.
8. What is a promising node in the state-space
tree?
A node in a state-space tree is said
to be promising if it corresponds to a partially constructed solution that may
still lead to a complete solution.
9.
What is a non-promising node in the state-space tree?
A node in a state-space tree is said
to be promising if it corresponds to a partially constructed solution that may
still lead to a complete solution; otherwise it is called non-promising.
10.
What do leaves in the state space tree represent?
Leaves in the state-space tree represent
either non-promising dead ends or complete solutions found by the algorithm.
11.
What is dynamic programming and who discovered it?
Dynamic programming is a technique for solving
problems with overlapping subproblems. These subproblems arise from a
recurrence relating a solution to a given problem with solutions to its smaller
subproblems only once and recording the results in a table from which the
solution to the original problem is obtained. It was invented by a prominent
U.S Mathematician, Richard Bellman in the 1950s.
12.
What is backtracking?
Backtracking constructs solutions one
component at a time and such partially constructed solutions are evaluated as
follows
i. If a partially constructed solution
can be developed further without
violating the problem’s constraints,
it is done by taking the first remaining legitimate option for the next
component.
ii.If there is no legitimate option
for the next component, no alternatives for the remaining component need to be
considered. In this case, the algorithm backtracks to replace the last
component of the partially constructed solution with its next option.
13.
What is the manner in which the state-space tree for a backtracking algorithm
is constructed?
In the majority of cases, a
state-space tree for backtracking algorithm is constructed in the manner of
depth-first search. If the current node is promising, its child is generated by
adding the first remaining legitimate option for the next component of a
solution, and the processing moves to this child. If the current node turns out
to be non-promising, the algorithm backtracks to the node’s parent to consider
the next possible solution to the problem, it either stops or backtracks to
continue searching for other possible solutions.
14.
How can the output of a backtracking algorithm be thought of?
The output of a backtracking algorithm
can be thought of as an n-tuple (x1, …xn) where each coordinate xi is an element
of some finite linearly ordered set Si. If such a tuple (x1, …xi) is not a
solution, the algorithm finds the next element in Si+1 that is consistent with
the values of (x1, …xi) and the problem’s constraints and adds it to the tuple
as its (I+1)st coordinate. If such an element does not exist, the algorithm
backtracks to consider the next value of xi, and so on.
15.
Give a template for a generic backtracking algorithm.
ALGORITHM
Backtrack
(X[1..i]) //Gives a template of a
generic backtracking algorithm //Input X[1..i] specifies the first I promising
components of a solution //Output All
the tuples representing the problem’s solution if X[1..i] is a solution write
X[1..i] else for each element x[Si+1
]consistent with X[1..i] and the constraints do X[i+1]
x
Backtrack(X[1..i+1]
16.
Write a recursive algorithm for solving Tower of Hanoi problem. ALGORITHM
To move n>1 disks from peg1 to
peg3, with peg2 as auxiliary, first move recursively n-1 disks from peg1 to
peg2 with peg3 as auxiliary.
-
Then
move the largest disk directly from peg1 to peg3
-
Finally
move recursively n-1 disks from peg2 to peg3 with peg1 as auxiliary
-
If
n=1 simply move the single disk from source peg to destination peg.
17.
What is the basic operation in the Tower of Hanoi problem and give the
recurrence relation for the number of moves?
The moving of disks is considered the
basic operation in the Tower of Hanoi problem and the recurrence relation for
the number of moves is given as
M(n)=2M(n)+1 for n>1 M(1)=1
18.
What is n-queens problem?
The problem is to place ‘n’ queens on an
n-by-n chessboard so that no two queens attack each other by being in the same
row or in the column or in the same diagonal.
19Define
the Hamiltonian circuit.
The Hamiltonian is defined as a cycle
that passes through all the vertices of the graph exactly once. It is named
after the Irish mathematician Sir William Rowan Hamilton (1805-1865).It is a
sequence of n+1 adjacent vertices vi0,
vi1,……, vin-1, vi0
where the first vertex of the sequence
is same as the last one while all the other n-1 vertices are distinct.
20.
What is the method used to find the solution in n-queen problem by symmetry?
The board of the n-queens problem has
several symmetries so that some solutions can be obtained by other reflections.
Placements in the last n/2 columns need not be considered, because any solution
with the first queen in square (1,i), n/2≤i≤n can be obtained by reflection
from a solution with the first queen in square (1,n-i+1)
21.
What are the additional features required in branch-and-bound when compared to
backtracking?
Compared to backtracking,
branch-and-bound requires:
i.A way to provide, for every node of
a state space tree, a bound on the best value of the objective function on any
solution that can be obtained by adding further components to the partial
solution represented by the node.
ii.The value of the best solution seen
so far
22.
What is knapsack problem?
Given n items of known weights wi and
values vi, i=1,2,…,n, and a knapsack of capacity W, find the most valuable
subset of the items that fit the knapsack. It is convenient to order the items
of a given instance in descending order by their value-to-weight ratios. Then
the first item gives the best payoff per weight unit and the last one gives the
worst payoff per weight unit.
23.
Give the formula used to find the upper bound for knapsack problem.
A simple way to find the upper bound ‘ub’ is
to add ‘v’, the total value of the items already selected, the product of the
remaining capacity of the knapsack W-w and the best per unit payoff among the
remaining items, which is v
i+1/wi+1 ub = v + (W-w)( vi+1/wi+1)
24.
What is the traveling salesman problem?
The problem can be modeled as a
weighted graph, with the graph’s vertices representing the cities and the edge
weights specifying the distances. Then the problem can be stated as finding the
shortest Hamiltonian circuit of the graph, where the Hamiltonian is defined as
a cycle that passes through all the vertices of the graph exactly once.
25.
What are the strengths of backtracking and branch-and-bound?
The strengths are as follows
i.It is typically applied to difficult
combinatorial problems for which no efficient algorithm for finding exact
solution possibly exist
ii.It holds hope for solving some
instances of nontrivial sizes in an acceptable amount of time
iii.Even if it does not eliminate any
elements of a problem’s state space and ends up generating all its elements, it
provides a specific technique for doing so, which can be of some value.
