Longest Common Subsequence

#include<iostream.h>
#include<conio.h>
#include<stdio.h>
int printlcs(char b[30][30],char x[], int m, int n)
{
if((m==0)||(n==0))
{
return 0;
}
if(b[m][n]==’*’)
{
cout<<“TEST”;
printlcs(b,x,m-1,n);
cout<<x[m];
}
else
{
cout<<“TEST”;
if(b[m][n]==’^’)
{
printlcs(b,x,m-1,n);
}
else
{
cout<<“test”;
printlcs(b,x,m,n-1);
}
}
}
void main()
{
clrscr();
char x[30], y[30],c[30][30],b[30][30];
int m,n;
cout<<“enter the length of strings”;
cin>>m>>n;
cout<<“enter string1”;
gets(x);
fflush(stdin);
cout<<“enter string 2”;
gets(y);
fflush(stdin);
for(int i=0;i<m;i++)
{
c[i][0]=0;
}
for(int j=0;j<n;j++)
{
c[0][j]=0;
}
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
if(x[i]==y[j])
{
c[i][j]=c[i-1][j-1]+1;
b[i][j]=’*’;
}
else
{
if((c[i-1][j]>c[i][j-1])||(c[i-1][j]==c[i][j-1]))
{
c[i][j]=c[i-1][j];
b[i][j]=’^’;
}
else
{
c[i][j]=c[i][j-1];
b[i][j]='<‘;
}
}
}
}
int h;
h=printlcs(b,x,m,n);
getch();
}

 

Theory:

http://www.algorithmist.com/index.php/Longest_Common_Subsequence

http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/

Prim’s Algorithm

#include<iostream.h>
#include<conio.h>
#include<stdio.h>
struct node
{
int index;
char ch;
int status;
char prev;
}v[10];
void update(node v[],node temp,int n)
{
for(int i=0;i<n;i++)
{
if(v[i].ch==temp.ch)
{
v[i].status=1;
}
}
}
node extractmin(int graph[10][10], node v[], int n)
{
node temp;
int min;
min=100;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if((v[i].status==1)&&(v[j].status==0))
{
if(min>graph[i][j])
{
min=graph[i][j];
v[j].prev=v[i].ch;
temp=v[j];
}
}
}
}
return temp;
}
void main()
{ clrscr();
int n,graph[10][10];
cout<<“enter n”;
cin>>n;
cout<<“enter graph”;
for(int i =0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>graph[i][j];
}
}
cout<<“enter vertices’ details”;
for(i=0;i<n;i++)
{
cout<<“enter vertex”;
cin>>v[i].ch;
v[i].status=0;
v[i].index=i;
v[i].prev=’r’;
}
int counter=0;
char s;
cout<<“enter source vertex”;
cin>>s;
for(i=0;i<n;i++)
{
if(s==v[i].ch)
{
v[i].status=1;
}
}
counter++;
char path;
int p=0;
node temp;
//char prev,recent,t;
//prev=s;
while(counter<n)
{
temp=extractmin(graph,v,n);
update(v,temp,n);
cout<<“\n “<<temp.prev<<“->”<<temp.ch;
//t=getprevious(v,graph,prev,temp,n);
counter++;
}
//cout<<“path is\n “;
//puts(path);
getch();
}

 

Theory:

http://students.ceid.upatras.gr/~papagel/project/prim.htm

http://lcm.csa.iisc.ernet.in/dsa/node183.html

Dijkstra’s Algorithm

#include<iostream.h>
#include<conio.h>
#include<stdio.h>
char path[10];
int p=0;
struct node
{
int weight;
char ch;
int index;
int status;
}v[10];
node extractmin(node v[], int n)
{
int min=300;
node temp;
for(int i=0;i<n;i++)
{
if((v[i].weight<min)&&(v[i].status==0))
{
min=v[i].weight;
temp=v[i];
}
}
return temp;
}
void update(node v[],node s,int n)
{
for(int i=0;i<n; i++)
{
if(v[i].ch==s.ch)
{
v[i].status=1;
path[p]=v[i].ch;
p++;
}
}
}
void main()
{
clrscr();
int graph[10][10];
int n;
cout<<“enter the number of vertices”;
cin>>n;
cout<<“enter the matrix”;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>graph[i][j];
}
}

for(i=0;i<n;i++)
{
cout<<“enter the weight”;
cin>>v[i].weight;
cout<<“enter the name”;
cin>>v[i].ch;
v[i].index=i;
v[i].status=0;
}
node s;
int wtest;
int counter =0;
while(counter<n)
{
s=extractmin(v,n);
update(v,s,n);
for(i=0;i<n;i++)
{
wtest=s.weight+graph[s.index][i];
if(wtest<v[i].weight)
{
v[i].weight=wtest;
}
}
counter++;
}
cout<<“the weights are”;
for( i=0;i<n;i++)
{
cout<<“\n “<<v[i].weight;
}
cout<<“path is”;
puts(path);
//cout<<“hello”;
getch();
}

 

For theory:

http://www.cs.auckland.ac.nz/~jmor159/PLDS210/dijkstra.html

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/dijkstraAlgor.htm

Bellman Ford

#include<iostream.h>
#include<stdio.h>
#include<conio.h>
struct node
{
int index;
char ch;
char prev;
int weight;
int status;
}v[10];
node getprev(node x,int n)
{
for(int i=0;i<n;i++)
{
if(v[i].ch==x.prev)
{
break;
}
}
return v[i];
}
void relax(node v[],int graph[10][10], int n, int counter)
{
int wtest;
/*int min;
for(int i=0;i<n;i++)
{min=100; */
for(int j=0;j<n;j++)
{
wtest=v[counter].weight+graph[counter][j];
if(wtest<v[j].weight)
{
v[j].weight=wtest;
v[j].prev=v[counter].ch;
}
}
}
void main()
{
clrscr();
int n;
int graph[10][10];
cout<<“enter n”;
cin>>n;
cout<<“enter grAPH”;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>graph[i][j];
}
}
cout<<“enter vertex details”;
for(i=0;i<n;i++)
{
cout<<“\n name”;
cin>>v[i].ch;
cout<<“\n weight”;
cin>>v[i].weight;
v[i].status=0;
v[i].index=i;
v[i].prev=’r’;
}
int counter;
counter=0;
for(i=1;i<n;i++)
{
counter=0;
while(counter<n)
{
relax(v,graph,n,counter);
counter++;
}
}
node p;
int exp;
for(i=0;i<n;i++)
{
p=getprev(v[i],n);
//exp=v[i].weight+ graph[p.index][i];
if(p.weight>v[i].weight)
{
cout<<“\n negative cycle”;
cout<<“\n”<<v[i].prev<<“->”<<v[i].ch;
}
if(v[i].weight<0)
{
cout<<“\n “<<v[i].prev<<“->”<<v[i].ch;
}
}
cout<<“TEST”;
for(i=0;i<n;i++)
{
cout<<“\t “<<v[i].weight<<“\t”<<v[i].prev;
cout<<“\n”;
}
getch();
}