Minimum Edit Distance using Dynamic Programming

The Minimum edit distance between two strings is the minimum number of editing operations required to transform string into other string. Minimum Edit distance use Insertion, Deletion and Substitution operation to transform string into other.

Here I am writing c program to get minimum edit distance between to string using dynamic programming.

Code

public class MinEditDistance
{
public static void main(String[] args)
{
String X="#"+"EXECUTION";
String Y="#"+"INTENTION";
int X_l=X.length();
int Y_l=Y.length();
int D[][]=new int[X_l][Y_l];//Distance Array


//Initialize first row with its index
for (int i = 0; i < X_l; i++)
{
D[i][0]=i;
}
//Initialize first column with its index
for (int j = 0; j < Y_l; j++)
{
D[0][j]=j;
}

for (int i = 1; i < X_l; i++)
{
for (int j = 1; j < Y_l; j++)
{
int min=99999; //reset to infinity
//Get minimum from all
if(X.charAt(i)==Y.charAt(j))
{
min=D[i-1][j-1];
}
if(min > (D[i-1][j-1]+2))
{
min=D[i-1][j-1]+2;
}
if(min > (D[i][j-1]+1))
{
min=D[i][j-1]+1;
}
if(min> (D[i-1][j]+1))
{
min=D[i-1][j]+1;
}

D[i][j]=min;
}
}

//Display Distance Matrix
for (int j = 0; j < Y_l; j++)
{
System.out.print("\t"+Y.charAt(j));
}
System.out.println();
for (int i = 0; i < X_l; i++)
{
System.out.print(X.charAt(i)+"  ");
for (int j = 0; j < Y_l; j++)
{
System.out.print("\t"+D[i][j]);
}
System.out.println();
}

System.out.println("mINIMUM eDIT dISTANCE IS "+D[X_l-1][Y_l-1]);
}

}

Kite cutting problem using Dynamic programming program

Cloth cutting or kite cutting problem is well known problem of DP (Dynamic programming) used in real life.

Here we have sheet of 9x10 and we want to divide it in such a way that we get maximum value.

 Price of subsheets are     2x3=50 and 3x5=100.

Code

public class kite_cutting 

{

public static void main(String strd[]) 

{

int M=9,N=10; //Given SIze of sheet= 9x10

M++; //Make space for 0

N++;

int sheet[][]=new int[M][N];

sheet[2][3]=50; //Already given the value 2x3=50

sheet[3][2]=50;

sheet[3][5]=100;//Already given the value 3x5=50

sheet[5][3]=100;

//initialize first row and column to 0.

for(int i=0;i<M;i++)

sheet[i][0]=0; 

for(int i=0;i<N;i++)

sheet[0][i]=0;

int temp;

//Start DP

for (int i = 0; i < M; i++) 

{

for (int j = 0; j < N; j++) 

{

temp=0;

//Cut the sheet horizontally upto i/2

for (int k = 0; k <= i/2 ; k++) 

{

if(temp<(sheet[k][j]+sheet[i-k][j]))

{

temp=(sheet[k][j]+sheet[i-k][j]);

}

}

//cut the sheet vertically upto j/2

for (int k = 0; k <= j/2 ; k++) 

{

if(temp<(sheet[i][k]+sheet[i][j-k]))

{

temp=(sheet[i][k]+sheet[i][j-k]);

}

}

//store max temp into table

sheet[i][j]=temp;

}

}

//print Table

for (int i = 0; i < M; i++) 

{

System.out.print(i +"||\t");

for (int j = 0; j < N; j++) 

{

System.out.print(sheet[i][j]+"\t");

}

System.out.println();

}

for (int j = 0; j < N; j++)

{

System.out.print("-------------");

}

System.out.print("\n\t");

for (int j = 0; j < N; j++)

{

System.out.print(j+"\t");

}

System.out.println("\n Maximum values we get from sheet is "+sheet[M-1][N-1]);

}

}

Download Source Code in Java
click on above link to get source code

MultiLevel and Distributed Cache

Multi Level Cache and Distributed cache are widely used today for multiprocessor and cluster applications.

Download PPT

Thank You For Reading

Advanced Cache Concepts: Snoopy and Directory Cache coherence protocol

• Since all the processors share the same address space, it is possible for more than one processor to cache an address at the same time.(coherence issue).
• If one processor updates the data item without informing the other processor, inconsistency may result and cause incorrect execution.(consistency issue).

• To solve this problem we suggest below two cache coherence protocols

                  1. Snoopy protocol

                 2. Directory protocol

Download PPT

Thank You For Reading.

Create bootable Pen drive using command prompt in windows

Create bootable Pen drive using command prompt in windows

Creating bootable pendrive in windows is very easy task, we can do it without installing any third party software. I am writing the steps to create bootable pen drive for any OS.

1. Attach your pen drive.( Back up all your important data from Pendrive & Format it)
2. Open Command Prompt.
   
3. Type "DISKPART" in command prompt. It will open new windows.

    4. Type "LIST DISK" in newly open window.

   5. Select your target Pen Drive by just type its number. here I am making "disk 2" as bootable drive. 

                       Type "select disk <DISK NO>"

                        Example: select disk 2.

  6. Execute below commands in Sequence.

1. clean
2. create partition primary
3. select partition 1
4. active
5. format fs=ntfs (This take upto 15 minutes depends on your drive size)

         6. assign

         7. exit

7. Now simply copy your OS content into that pen drive.

Now Your PENDRIVE work as bootable pen drive..

THANK YOU FOR READING !!!