CS2251 -DESIGN AND ANALYSIS OF ALGORITHMS UNIT IV QUESTIONS

UNIT IV

l) Explain Backtracking

The principal idea is to construct solutions one component at a time and evaluate such partially constructed candidates as follows.

> If a partially constructed solution can be developed further without violating the problem's constraints, it is done by taking the first remaininig legitimate option for the next component.

> If there is no legitimate option for the next component, no alternatives for any 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

2) Explain State Space Tree

If it is convenient to implement backtracking by constructing a tree of choices being made, the tree is called a state space tree. Its root represents an initial state before the search for a solution begins.

3) Explain promising and nonpromising node

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 nonpromising

4) Explain 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 same column or on the same diagonal.

5) Explain Subset-Sum Problem

We consider the subset-sum problem: Find a subset of a given

set S={S₁,S₂,..........S_n} of n positive integers whose sum is equal to a given positive integer d.

6) Explain Branch and Bound Technique

Compared to backtracking, branch and bound requires

The idea to be strengthened further if we deal with an optimization problem, one that seeks to minimize or maximize an objective function, usually subject to some constraints.

7) Define Feasible Solution

          A feasible solution is a point in the problem's search space that satisfies all the problem's constraints.

Ex: A Hamiltonian Circuit in the traveling salesman problem.  A subset of items whose total weight does not exceed the knapsack's Capacity

8) Define Optimal solution

Is a feasible solution with the best value of the objective function

Eg: The shortest Hamiltonian Circuit

The most valuable subset of items that fit the knapsack

9)Mention two reasons to terminate a search path at the current node in a state-space tree of a branch and bound algorithm.

The value of the node's bound is not better than the value of the best solution seen so far. The node represents no feasible solutions because the constraints of the problem are already violated.

10) Explain ²Graph coloring” problem.

 The graph coloring problem asks us to assign the smallest number of colors to vertices of a graph so that no two adjacent vertices are the same color.

11) Explain Knapsack Problem

Find the most valuable subset of n items of given positive integer weights and values that fit into a knapsack of a given positive integer capacity.