What is the Idea of Developing a DP Algorithm?

The Idea of Developing a DP Algorithm :

Step 1: Structure : Characterize the structure of an optimal solution.

-Decompose the problem into smaller problems, and find a relation between the structure of the optimal solution of the original problem and the solutions of the smaller pronlms.

Step 2 : Principle of Optimality : Recursively define the value of an optimal solution.

-Express the solution of the original problem in terms of optimal solutions for smaller problems.

Step 3 : Bottom-up computation: Compute the value of an optimal solution in a bottom-up fashion by using a table structure.

Step 4 : construction of optimal Solution : Construct an optimal solution from computed information.Steps 3 and 4 may often be combined. 

What is 0-1 Knapsack Problem?

0-1 Knapsack Problem : Given two n-tuples of positive numbers (<V₁,V₂,.....,V_n) and (<w₁,w₂,w₃,.....,w_n and W>0, We wish to determine the subset T∈{1,2,3,....,n} (of files to store)) that maximizes ∑_ieT V_i subject to ∑_ieT w_i≤W

What is the 8-Queens Problem

The 8-Queens Problem :
The Bounding function for 8-queens problem is
No two queens placed on the same column  → x_i's are distinct
No two queens placed on the same diagonal → how to test?

The same value of "row-column" or "row+column" indicates that two queens placed on the same diagonal.

Supposing two queens on (i,j) and (k,1)
i-j=k-1(i.e,j-1=i-k) or i+j = k+1(i.e, j-1 = k-i)
So, two queens placed on the same diagonal iff
[j-i] = [i-k] 

Algorithm NQueen(k,n)

// Using backtracking, this procedure prints all
//possible placements of n queens on an nXn
//chessboard so that they are nontracking.
{
for(i=1;i<=n;i++)
{
if(Place(k,i))then
{
x[k] = i;
if(k=n)then write(x[1:n]);
else NQueens(k+1, n);
}
}
}

What is Implicit Constraints?

Implicit Constraints : The implicit constraints are rules that determine which of the tuples in the solution space of I satisfy the criterion function.Thus implicit constraints describe the way in which the x_i must relate to each other.

What is Explicit Constraints?

Explicit Constraints : Explicit constraints are rules that restrict each x_i to take on values only from a given set.

Common Examples of Explicit constraints are :
X_i≥0 or S_i = {all nonnegative real numbers} X_i = 0 or S_i = {0,1} 1_i≤x_i≤u_i or S_i = {a:1_i≥a≥u_i}
All tuples satisfying the explicit constraints define a possible solution space for 1(I = Problem instance)

What is the Formulation of the backtracking?

The Formulation of the backtracking : T(X₁,X₂,...,X_i): set of all possible values for x_i+1 such that (X₁,X₂,...,X_i,X_i+1) is also a B_i+1>(X₁,X₂,...,X_i,X_i+1): bounding function If B_i+1>(X₁,X₂,...,X_i,X_i+1) is false, then the path cannot be extended to reach an answer node.

Two Different ways of tree generation

** backtracking : Depth first node generation with bounding functions is called backtracking.

**Branch-and-bound : E-node remains E-node until it is dead 

Merge Sort Algorithm

Algorithm MergeSort(low, high)

//a[low:high] is a global array to be sorted
//small(P) is true if there is only one element to
//sort.In this case the list is already sorted
{
if(low<high) // If there are more than one element
{

//Divide P into subproblems.
Find where to split the set
mid = (low+high)/2;
//solve the subproblems.
MergeSort(low,mid);
MergeSort(mid+1, high);
//Combine the Solutions.
Merge(low, mid, high);
}
}

Finding the maximum and minimum number

Algorithm StraightMaxMin(a n, max, min)

//Set max to the maximum and min to the minimum of a[1:n].
{
max = min = a[1];
for i:=2 to n do
{
if(max<a[i] then max:=a[i]);
if(min>a[i] then min:=a[i]);
}
}

Algorithm BinSearch(a,n,x)

Algorithm BinSearch(a,n,x)

//given an array a(i,10 of elements in non-decreasing.
//order, 1<=i<=1, determine whether x is present and
//if so, return j such that x = a[j], else return 0.
{
low = 1;high = n;
while(low ≤ high) do
{
mid = [(low+high)/2];
if(x<a[mid]) then high = mid-1;
else if(x>a[mid]) then low = mid+1;
else return mid;
}
return 0;
}

Algorithm for recursive binary search

Algorithm BinarySearch(a, i, 1,x).

//Given an array  a(i,l) of elements in non-decreasing.
//order, 1<=i<=1, determine whether x is present and
//if so, return j such that x = a[j], else return 0.

{

if(1=i)then
{
if(x=a[i]) then return i;
else return 0;
}
else
{
mid:=[(i+1)/2];
if(x=a[mid]) then return mid;
else if(x<a[mid]) then
return Binarysearch(a, i, mid-1, x);
else return Binarysearch(a, mid+1, 1, x);
}
}

What is Branch and Bound?

Branch and Bound : E-node remains E-node until it is dead

What is Backtracking?

Backtracking : Depth first node generation with bounding functions is called backtracking.

What is Bounding Function?

Bounding Function : Bounding functions are used to kill live nodes without generating all their children.

What is E-node?

E-Node : The live node whose children are currently being generated is called the E-node

What is A Dead Node?

A Dead Node : A dead node is a generated node which is not  to be expanded further or all of whose children have been generated

What is Live Node?

Live Node: A node which has been generated and all of whose children have not yet been generated is called live node.

Difference between backtracking & Branch and Bound

Backtracking:
* It is used to find all posible solution available to the problem
*It traverse tree by DFS(Depth first Search)
*It realizes that it has made a bad choice & ubndoes the last choice by tracking up.
*It search the state space tree until it found a solution
*It involves feasibility function

Branch-and-Bound(BB):
*It is used to solve optimization problem
*It may traverse the tree in any manner, DFS or BFS
*It realizes that is already has a better optional solution that the pre-solution leads to so it abandons that pre-solution.
*It completely search the state space tree to get optional solution.
*It involves bounding function.

SumOfSub(s,k,r)

Algorithm:SumOfSub(s,k,r)

//Finfd all subset of W[1:n] that sum to m.The values
//of x[j]; 1<=j<k, have already been determined.

* s = ∑k-1j=1>W[j] * x[j] and r = ∑nj=k>W[j]
// The w[j]'s are in non decreasing order.
//It is assumed that W[1] <= m and  ∑ni=1>W[i] ≥ m

{

// Generate left child .Note that s+w[k] <= m
//because B<sub>k-1 is true. 
x[k] = 1;

if(s+w[k] == m) then write (x[1:k]) // Subset found

//There is no recursive call here as w[j] > 0, 1<=j <=n.

else if(s+w[k] + w[k+1] <=m)
then SumOfSub(s+w[k], k+1, r-w[k]);
//Generate right child and evaluate Bk-1

if((s+r-w[k] >=m) && (s+w[k+1] <=m)) then {
x[k] = 0;
SumOfSub(s, k+1, r-w[k]);</sub>
 

Sum of Subsets

Suppose we are given n distinct numbers (usually called weights) and we desire to find all combinations of these numbers whose sums are m.This is called sum of subsets problem.We consider a backtracking solution using fixed tuple size strategy.

The children of any node in fig 6.4 are easily generated.For a node at level 1 the left child corresponds to x_i = 1 and the right to x_i = 0.

A simple choice for bounding function is:

B_k(X₁,..,X_k) = true iff  ∑^k_i=1 W_iX_i + ∑^k_i=k+1 W<sub>i ≥ m

Assuming Wi's in nondecreasing order, (X1,..,Xk) cannot lead to an answer node if  
∑^ki=1 WiXi + ∑^ki=k+1 Wi > m

So, the bounding function is</sub>
 B_k(X₁,..,X_k) = true iff  ∑^k_i=1 W_iX_i + ∑^k_i=k+1 W_{i ≥ m and}
∑^k_i=1 W_iX_i + ∑^k_i=k+1 W_{i > m}