Tuesday, June 20, 2017

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 (<V1,V2,.....,Vn) and (<w1,w2,w3,.....,wn and W>0, We wish to determine the subset T∈{1,2,3,....,n} (of files to store)) that maximizes ∑ieT Vi subject to ∑ieT wi≤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  → xi'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.
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 xi must relate to each other.

What is Explicit Constraints?

Explicit Constraints : Explicit constraints are rules that restrict each x<sub>i</sub> to take on values only from a given set.

Common Examples of Explicit constraints are :
Xi≥0 or Si = {all nonnegative real numbers} Xi = 0 or Si = {0,1} 1i≤xi≤ui or Si = {a:1i≥a≥ui}
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(X1,X2,...,Xi): set of all possible values for xi+1 such that (X1,X2,...,Xi,Xi+1) is also a Bi+1>(X1,X2,...,Xi,Xi+1): bounding function If Bi+1>(X1,X2,...,Xi,Xi+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 

Monday, June 19, 2017

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(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(x=a[i]) then return i;
else return 0;
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);

Sunday, June 18, 2017

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

* 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

*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.



//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 Bk-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]);

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 xi = 1 and the right to xi = 0.

A simple choice for bounding function is:

Bk(X1,..,Xk) = true iff  ∑ki=1 WiXi + ∑ki=k+1 Wi ≥ 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
 Bk(X1,..,Xk) = true iff  ∑ki=1 WiXi + ∑ki=k+1 Wi ≥ m and
ki=1 WiXi + ∑ki=k+1 Wi > m