Skip to content

Instantly share code, notes, and snippets.

@cmrmahesh

cmrmahesh/AssemblyLineScheduling.cpp

Created November 10, 2016 07:14
Show Gist options
  • Save cmrmahesh/61216fbf3ac7e0548a57cc2667e5b70c to your computer and use it in GitHub Desktop.
Save cmrmahesh/61216fbf3ac7e0548a57cc2667e5b70c to your computer and use it in GitHub Desktop.
Download ZIP
Advanced Algorithms Lab
Raw
AssemblyLineScheduling.cpp
#include<stdio.h>
#include<conio.h>
#define SZ 20
int k;
main()
{
int i,j,m ,F;
int e[3],a[SZ][SZ],t[SZ][SZ],x[3],n;
printf("This program is for 2 line and maximum 20 station at each line.\n");
printf("Enter number of station \n");
scanf("%d",&n);
printf("Enter the entry value for line 1 and line2\n");
scanf("%d%d",&e[1],&e[2]);
printf("Enter the assembly time for %d stations each of line1 and then of line2 \n",n);
for(i=1;i<=2;i++)
{
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
}
printf("Enter the %d transfer time for %d stations each for line1 and then of line2 \n",n-1,n);
for(i=1;i<=2;i++)
{
for(j=1;j<n;j++)
scanf("%d",&t[i][j]);
}
printf("Enter the exit value for line 1 and line2\n");
scanf("%d\t%d",&x[1],&x[2]);
printf("...PLEASE WAIT...\n");
int f[2][n],l[2][n],L;
f[1][1]=e[1] + a[1][1];
f[2][1]=e[2] + a[2][1];
for(j=2;j<=n;j++)
{
if(f[1][j-1]+a[1][j]<=f[2][j-1]+t[2][j-1]+a[1][j])
{
f[1][j]=f[1][j-1]+a[1][j];
l[1][j]=1;
}
else
{
f[1][j]=f[2][j-1]+t[2][j-1]+a[1][j];
l[1][j]=2;
}
if(f[2][j-1]+a[2][j]<=f[1][j-1]+t[1][j-1]+a[2][j])
{
f[2][j]=f[2][j-1]+a[2][j];
l[2][j]=2;
}
else
{
f[2][j]=f[1][j-1]+t[1][j-1]+a[2][j];
l[2][j]=1;
}
}
if(f[1][n]+x[1]<=f[2][n]+x[2])
{
F=f[1][n]+x[1];
L=1;
}
else
{
F=f[2][n]+x[2];
L=2;
}
printf("line1\n");
for(k=1;k<=n;k++)
{
printf("%d\t",f[1][k]);
}
printf("\nline2\n");
for(k=1;k<=n;k++)
{
printf("%d\t",f[2][k]);
}
printf("\n optimal value is %d \n",F);
printf("\n\n");
printf("line %d ,station %d\n",L,n);
for(j=n;j>=2;j--)
{
m=l[L][j];
printf(" line %d,station %d\n",m,j-(n-1));
}
getch();
return 0;
}
Raw
BellmanFord.cpp
#include<stdio.h>
#include<conio.h>
int dist[5];
int pred[5];
void Init_Shortest_Path(int s)
{
int i = 0;
for(i = 0; i < 5; ++i)
{
dist[i] = 9999;
pred[i] = -1;
}
dist[s] = 0;
}
void Relax(int u, int v, int w)
{
if(dist[v] > dist[u] + w)
{
dist[v] = dist[u] + w;
pred[v] = u;
}
}
int Bellman_Ford(int G[5][5], int s)
{
int i, j, k;
Init_Shortest_Path(s);
for(i = 0; i < 4; ++i) //For each vertex
{
for(j = 0; j < 5; ++j)
{
for(k = 0; k < 5; ++k)
{
if(G[j][k] != 0)
Relax(j, k, G[j][k]);
}
}
}
for(i = 0; i < 5; ++i)
{
for(j = 0; j < 5; ++j)
{
if(dist[j] > dist[i] + G[j][i])
return 0;
}
}
return 1;
}
void Path_trace(int s, int d)
{
int i = 0;
int j = d-1;
printf("\n\nPath trace from source(vertex %d) to dest(vertex %d):\n\n", s, d);
while(j != 0)
{
printf("%d -> ", j);
j = pred[j];
}
printf("%d", j);
}
void Print_Shortest_Path(int s)
{
int i = 0;
printf("\nShortest path from vertex %d (source):\n\n", s);
for(i = 0; i < 5; ++i)
printf("To vertex %d: %d\n",i, dist[i]);
}
int main()
{
int G[5][5] = { {0,6,7,0,0},
{0,0,8,5,-4},
{0,0,0,-3,9},
{0,-2,0,0,0},
{2,0,0,7,0}};
int retCode;
retCode = Bellman_Ford(G,0);
Print_Shortest_Path(0);
Path_trace(0,5);
getch();
return 0;
}
Raw
BinomialHeap.cpp
#include<stdio.h>
#include<malloc.h>
struct node
{
int n;
int degree;
struct node* parent;
struct node* child;
struct node* sibling;
};
struct node* MAKE_bin_HEAP();
int bin_LINK(struct node*,struct node*);
struct node* CREATE_NODE(int);
struct node* bin_HEAP_UNION(struct node*,struct node*);
struct node* bin_HEAP_INSERT(struct node*,struct node*);
struct node* bin_HEAP_MERGE(struct node*,struct node*);
struct node* bin_HEAP_EXTRACT_MIN(struct node*);
int REVERT_LIST(struct node*);
int DISPLAY(struct node*);
struct node* FIND_NODE(struct node*,int);
int bin_HEAP_DECREASE_KEY(struct node*,int,int);
int bin_HEAP_DELETE(struct node*,int);
int count=1;
struct node* MAKE_bin_HEAP()
{
struct node* np;
np=NULL;
return np;
}
struct node * H=NULL;struct node *Hr=NULL;
int bin_LINK(struct node* y,struct node* z)
{
y->parent=z;
y->sibling=z->child;
z->child=y;
z->degree=z->degree+1;
}
struct node* CREATE_NODE(int k)
{
struct node* p;//new node;
p=(struct node*)malloc(sizeof(struct node));
p->n=k;
return p;
}
Program 14:Binomial heap
CSC51102 Lab Manual
Page 66 of 87
struct node* bin_HEAP_UNION(struct node* H1,struct node* H2)
{
struct node* prev_x;
struct node* next_x;
struct node* x;
struct node* H=MAKE_bin_HEAP();
H=bin_HEAP_MERGE(H1,H2);
if(H==NULL)
return H;
prev_x=NULL;
x=H;
next_x=x->sibling;
while(next_x!=NULL)
{
if((x->degree!=next_x->degree)||((next_x->sibling!=NULL)&&(next_x->sibling)->degree==x-
>degree))
{
prev_x=x;
x=next_x;
}
else
{
if(x->n<=next_x->n)
{
x->sibling=next_x->sibling;
bin_LINK(next_x,x);
}
else
{
if(prev_x==NULL)
H=next_x;
else
prev_x->sibling=next_x;
bin_LINK(x,next_x);
x=next_x;
}
}
next_x=x->sibling;
}
return H;
}
struct node* bin_HEAP_INSERT(struct node* H,struct node* x)
{
struct node* H1=MAKE_bin_HEAP();
x->parent=NULL;
x->child=NULL;
x->sibling=NULL;
x->degree=0;
H1=x;
H=bin_HEAP_UNION(H,H1);
CSC51102 Lab Manual
Page 67 of 87
return H;
}
struct node* bin_HEAP_MERGE(struct node* H1,struct node* H2)
{
struct node* H=MAKE_bin_HEAP();
struct node* y;
struct node* z;
struct node* a;
struct node* b;
y=H1;
z=H2;
if(y!=NULL)
{
if(z!=NULL&&y->degree<=z->degree)
H=y;
else if(z!=NULL&&y->degree>z->degree)//need some modificationss here;the first and the else
conditions can be merged together!!!!
H=z;
else H=y;
}
else
H=z;
while(y!=NULL&&z!=NULL)
{
if(y->degree<z->degree)
{
y=y->sibling;
}
else if(y->degree==z->degree)
{
a=y->sibling;
y->sibling=z;
y=a;
}
else
{
b=z->sibling;
z->sibling=y;
z=b;
}
}
return H;
}
int DISPLAY(struct node* H)
{
struct node* p;
if(H==NULL)
{
printf("\nHEAP EMPTY");
CSC51102 Lab Manual
Page 68 of 87
return 0;
}
printf("\nTHE ROOT NODES ARE:-\n");
p=H;
while(p!=NULL)
{
printf("%d",p->n);
if(p->sibling!=NULL)
printf("-->");p=p->sibling;
}
printf("\n");
}
struct node* bin_HEAP_EXTRACT_MIN(struct node* H1)
{
int min;
struct node* t=NULL;
struct node* x=H1;
struct node *Hr;
struct node* p;
Hr=NULL;
if(x==NULL)
{
printf("\nNOTHING TO EXTRACT");
return x;
}
// int min=x->n;
p=x;
while(p->sibling!=NULL)
{
if((p->sibling)->n<min)
{
min=(p->sibling)->n;
t=p;
x=p->sibling;
}
p=p->sibling;
}
if(t==NULL&&x->sibling==NULL)
H1=NULL;
else if(t==NULL)
H1=x->sibling;
else if(t->sibling==NULL)
t=NULL;
else
t->sibling=x->sibling;
if(x->child!=NULL)
{
REVERT_LIST(x->child);
(x->child)->sibling=NULL;
CSC51102 Lab Manual
Page 69 of 87
}
H=bin_HEAP_UNION(H1,Hr);
return x;
}
int REVERT_LIST(struct node* y)
{
if(y->sibling!=NULL)
{
REVERT_LIST(y->sibling);
(y->sibling)->sibling=y;
}
else
{
Hr=y;
}
}
struct node* FIND_NODE(struct node* H,int k)
{
struct node* x=H;
struct node* p=NULL;
if(x->n==k)
{
p=x;
return p;
}
if(x->child!=NULL&&p==NULL)
{
p=FIND_NODE(x->child,k);
}
if(x->sibling!=NULL&&p==NULL)
{
p=FIND_NODE(x->sibling,k);
}
return p;
}
int bin_HEAP_DECREASE_KEY(struct node* H,int i,int k)
{
int temp;
struct node* p;
struct node* y;
struct node* z;
p=FIND_NODE(H,i);
if(p==NULL)
{
printf("\nINVALID CHOICE OF KEY TO BE REDUCED");
return 0;
}
if(k>p->n)
CSC51102 Lab Manual
Page 70 of 87
{
printf("\nSORY!THE NEW KEY IS GREATER THAN CURRENT ONE");
return 0;
}
p->n=k;
y=p;
z=p->parent;
while(z!=NULL&&y->n<z->n)
{
temp=y->n;
y->n=z->n;
z->n=temp;
y=z;
z=z->parent;
}
printf("\nKEY REDUCED SUCCESSFULLY!");
}
int bin_HEAP_DELETE(struct node* H,int k)
{
struct node* np;
if(H==NULL)
{
printf("\nHEAP EMPTY");
return 0;
}
bin_HEAP_DECREASE_KEY(H,k,-1000);
np=bin_HEAP_EXTRACT_MIN(H);
if(np!=NULL)
printf("\nNODE DELETED SUCCESSFULLY");
}
int main()
{
int i,n,m,l;
struct node* p;
struct node* np;
//struct node *H;
char ch;
printf("\nENTER THE NUMBER OF ELEMENTS:");
scanf("%d",&n);
printf("\nENTER THE ELEMENTS:\n");
for(i=1;i<=n;i++)
{
scanf("%d",&m);
np=CREATE_NODE(m);
H=bin_HEAP_INSERT(H,np);
}
DISPLAY(H);
do
{
CSC51102 Lab Manual
Page 71 of 87
printf("\nMENU:-\n");
printf("\n1)INSERT AN ELEMENT\n2)EXTRACT THE MINIMUM KEY NODE\n3)DECREASE A NODE KEY\n
4)DELETE A NODE\n5)QUIT\n");
scanf("%d",&l);
switch(l)
{
case 1:do
{
printf("\nENTER THE ELEMENT TO BE INSERTED:");
scanf("%d",&m);
p=CREATE_NODE(m);
H=bin_HEAP_INSERT(H,p);
printf("\nNOW THE HEAP IS:\n");
DISPLAY(H);
printf("\nINSERT MORE(y/Y)= \n");
fflush(stdin);
scanf("%c",&ch);
}while(ch=='Y'||ch=='y');
break;
case 2:do
{
printf("\nEXTRACTING THE MINIMUM KEY NODE");
p=bin_HEAP_EXTRACT_MIN(H);
if(p!=NULL)
printf("\nTHE EXTRACTED NODE IS %d",p->n);
printf("\nNOW THE HEAP IS:\n");
DISPLAY(H);
printf("\nEXTRACT MORE(y/Y)\n");
fflush(stdin);
scanf("%c",&ch);
}while(ch=='Y'||ch=='y');
break;
case 3:do
{
printf("\nENTER THE KEY OF THE NODE TO BE DECREASED:");
scanf("%d",&m);
printf("\nENTER THE NEW KEY : ");
scanf("%d",&l);
bin_HEAP_DECREASE_KEY(H,m,l);
printf("\nNOW THE HEAP IS:\n");
DISPLAY(H);
printf("\nDECREASE MORE(y/Y)\n");
fflush(stdin);
scanf("%c",&ch);
}while(ch=='Y'||ch=='y');
break;
case 4:do
{
printf("\nENTER THE KEY TO BE DELETED: ");
CSC51102 Lab Manual
Page 72 of 87
scanf("%d",&m);
bin_HEAP_DELETE(H,m);
printf("\nDELETE MORE(y/Y)\n");
fflush(stdin);
scanf("%c",&ch);
}while(ch=='y'||ch=='Y');
break;
case 5:printf("\nTHANK U SIR\n");break;
default :printf("\nINVALID ENTRY...TRY AGAIN....\n");
}
}while(l!=5);
}
Raw
DijkstraDAG.cpp
#include<stdio.h>
#include<conio.h>
#define MAX 5
#define INF 998
int allselected(int *selected)
{
int i;
for(i=0;i<MAX;i++)
if(selected[i]==0)
return 0;
return 1;
}
void shortpath(int cost[][MAX],int *preced,int *distance)
{
int selected[MAX]={0};
int current=0,i,k,dc,smalldist,newdist;
for(i=0;i<MAX;i++)
distance[i]=INF;
selected[current]=1;
distance[0]=0;
current=0;
while(!allselected(selected))
{
smalldist=INF;
dc=distance[current];
for(i=0;i<MAX;i++)
{
if(selected[i]==0)
{
newdist=dc+cost[current][i];
if(newdist<distance[i])
{
distance[i]=newdist;
preced[i]=current;
}
if(distance[i]<smalldist)
{
smalldist=distance[i];
k=i;
}
}
}
current=k;
selected[current]=1;
}
}
void main()
{
int cost[MAX][MAX]=
{{0,10,INF,5,INF},
{INF,0,1,2,INF},
{INF,INF,0,INF,4},
{INF,3,9,0,2},
{7,INF,6,INF,0}};
int i,preced[MAX]={0},distance[MAX];
shortpath(cost,preced,distance);
for(i=0;i<MAX;i++)
{
printf("Shortest Distance From source to node %d = %d \n",i,distance[i]);
}
getch();
}
Raw
FFT.cpp
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#define PI M_PI
#define TWOPI (2.0*PI)
void four1(double data[], int nn, int isign)
{
int n, mmax, m, j, istep, i;
double wtemp, wr, wpr, wpi, wi, theta;
double tempr, tempi;
n = nn << 1;
j = 1;
for (i = 1; i < n; i += 2) {
if (j > i) {
tempr = data[j]; data[j] = data[i]; data[i] = tempr;
tempr = data[j+1]; data[j+1] = data[i+1]; data[i+1] = tempr;
}
m = n >> 1;
while (m >= 2 && j > m) {
j -= m;
m >>= 1;
}
j += m;
}
mmax = 2;
while (n > mmax) {
istep = 2*mmax;
theta = TWOPI/(isign*mmax);
wtemp = sin(0.5*theta);
wpr = -2.0*wtemp*wtemp;
wpi = sin(theta);
wr = 1.0;
wi = 0.0;
for (m = 1; m < mmax; m += 2) {
for (i = m; i <= n; i += istep) {
j =i + mmax;
tempr = wr*data[j] - wi*data[j+1];
tempi = wr*data[j+1] + wi*data[j];
data[j] = data[i] - tempr;
data[j+1] = data[i+1] - tempi;
data[i] += tempr;
data[i+1] += tempi;
}
wr = (wtemp = wr)*wpr - wi*wpi + wr;
wi = wi*wpr + wtemp*wpi + wi;
}
mmax = istep;
}
}
int main(int argc, char * argv[])
{
int i;
int Nx;
int NFFT;
double *x;
double *X;
Nx = 10;
printf("\n\n Nx = %d\n", Nx);
x = (double *) malloc(Nx * sizeof(double));
for(i=0; i<Nx; i++)
{
x[i] = i;
}
NFFT = (int)pow(2.0, ceil(log((double)Nx)/log(2.0)));
printf(" NFFT = %d\n", NFFT);
X = (double *) malloc((2*NFFT+1) * sizeof(double));
for(i=0; i<Nx; i++)
{
X[2*i+1] = x[i];
X[2*i+2] = 0.0;
}
for(i=Nx; i<NFFT; i++)
{
X[2*i+1] = 0.0;
X[2*i+2] = 0.0;
}
printf("\n Input complex sequence :\n");
for(i=0; i<NFFT; i++)
{
printf(" x[%d] = (%.2f + j %.2f)\n", i, X[2*i+1], X[2*i+2]);
}
four1(X, NFFT, 1);
printf("\n\n\n FFT Output :\n\n\n");
for(i=0; i<NFFT; i++)
{
printf(" X[%d] = (%.2f + j %.2f)\n", i, X[2*i+1], X[2*i+2]);
}
getchar();
}
Raw
FibonacciHeap.cpp
#include<stdio.h>
#include<conio.h>
#include<math.h>
#include<malloc.h>
#define NIL 0
int nNodes;
void create_fib()
{
min->parent=NIL;
min->key=NIL;
min->left=NIL;
min->right=NIL;
min->child=NIL;
nNodes=0;
}
/* inserting in fibonacci heap */
void Finsert(int val)
{
struct fheap_node *fheap;
fheap=malloc(sizeof(struct fheap_node));
fheap->key=val;
fheap->parent=NIL;
fheap->left=NIL;
fheap->right=NIL;
fheap->child=NIL;
if(min->key!=NIL)
{
fheap->right=min;
fheap->left=min->left;
(min)->left=fheap;
(fheap->left)->right=fheap;
if(val<min->key)
min=fheap; }
else
{
min=fheap;
min->left=min;
min->right=min;
}
nNodes++;
}
/* Displaying Fibonacci heap*/
void display(struct node *min1)
{
struct fheap_node *q,*chil;
if(min==NIL)
{
printf("\n Fibonacci heap is empty");
return;
}
q=min;
printf("\n Fibonacci heap display");
do
{
printf("\t%d ",q->key);
if(q->child!=NIL)
{
display(q->child);
}
q=q->right;
}
while(q!=min);
}
/* finding minimum key in heap */
void findmin()
{
printf("\nminimum is %d: ",min->key);
}
int main ()
{
int option,n,i,m;
clrscr();
min=NIL;
while(1)
{printf("\nmenu\n");
printf("1:create fibonacci heap\n");
printf("2:insert in fibonacci heap\n");
printf("3: find min in fibonacci heap \n");
printf("4:display\n");
printf("5: exit \n");
scanf ("%d",&option);
switch(option)
{ case 1 :create_fib();
break;
case 2: printf("\nenter the element= ");
scanf("%d",&n);
Finsert(n);
break;
case 3: findmin();
break;
case 4: display(min1);
break;
case 5 :exit(1);
default: printf("\nwrong choice... try again \n ");
}
}
}
Raw
FloydWarshall.cpp
#include<stdio.h>
#define V 4
#define INF 99999
void printSolution(int dist[][V]);
void floydWarshell (int graph[][V])
{
int dist[V][V], i, j, k;
for (i = 0; i < V; i++)
for (j = 0; j < V; j++)
dist[i][j] = graph[i][j];
for (k = 0; k < V; k++)
{
for (i = 0; i < V; i++)
{
for (j = 0; j < V; j++)
{
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
printSolution(dist);
}
void printSolution(int dist[][V])
{ int i,j;
printf ("Following matrix shows the shortest distances"
" between every pair of vertices \n");
for (i = 0; i < V; i++)
{
for ( j = 0; j < V; j++)
{
if (dist[i][j] == INF)
printf("%7s", "INF");
else
printf ("%7d", dist[i][j]);
}
printf("\n");
}}
int main()
{
int graph[V][V] = { {0, 5, INF, 10},
{INF, 0, 3, INF},
{INF, INF, 0, 1},
{INF, INF, INF, 0}
};
floydWarshell(graph)
return 0;}
Raw
KMP.cpp
#include<stdio.h>
#include<string.h>
char t[30],p[30];
int pre[30],m,n;
void prefix()
{
int k,q;
pre[1]=0;
k=0;
for(q=2;q<=m;q++)
{
while(k>0 && p[k]!=p[q-1])
{
k=pre[k];
}
if(p[k]==p[q-1])
k=k+1;
pre[q]=k;
}
printf("\n");
printf("prefix :");
for(q=1;q<=m;q++)
printf("%d",pre[q]);
}
int main()
{
printf("\n ** KMP Pattern Matcher **\n\n");
int q,i;
printf("Enter a Text T:");
gets(t);
n=strlen(t);
printf("\nEnter the pattern P : ");
gets(p);
m=strlen(p);
prefix();
q=0;
printf("\n");
for(i=0;i<n;i++)
{
while(q>0 && p[q]!=t[i])
{
q=pre[q];
}
if(p[q]==t[i])
{
q=q+1;
}
if(q==m)
{
printf("\nPattern matching with shift %d",i-m+1);
q=pre[q];
}
}
getchar();
}
Raw
MatrixChainMultiplication.cpp
# include <stdio.h>
# include <conio.h>
# include <stdlib.h>
# define sz 20
# define INF 200000
void print(unsigned long s[][sz], int i, int j)
{
if (i == j)
printf(" A%d ",i);
else
{
printf(" ( ");
print(s, i, s[i][j]);
print(s, s[i][j] + 1, j);
printf(" ) ");
}
}
void printm(unsigned long m[][sz], int n)
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%5d",m[i][j]);
}
printf("\n\n");
}
printf("\nThe No. of multiplication required is : %d",m[1][n]);
}
void Matrix_Chain_Order(int p[],int num)
{
unsigned long m[sz][sz] = {0};
unsigned long s[sz][sz] = {0};
unsigned int q = 0;
int i, j, k, l;
int n = num;
for(i = 1; i <= n; i++)
m[i][i] = 0;
for(l = 2; l <= n; l++)
for(i = 1; i <= (n - l + 1); i++)
{
j = i + l - 1;
m[i][j] = INF;
for(k = i; k <= j - 1; k++)
{
q = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j];
if(q < m[i][j])
{
m[i][j] = q;
s[i][j] = k;
}
}
}
print(s, i-1, j);
printf("\n\n");
printf("The Minimum No. of Multiplication Required is:\n\n");
printm(m,n);
}
main()
{
int i,num=0,p[sz]={0};
//clrscr();
printf("Enter the number of matrix : ");
scanf("%d",&num);
printf("Enter %d no. of order sequence for %d matrix :\n",num+1,num);
for(i=0;i<=num;i++)
scanf("%d",&p[i]);
printf("\n\n");
printf("MULTIPLICATION SEQUENCE IS : ");
printf("\n\n\t");
Matrix_Chain_Order(p,num);
getch();
return 0;
}
Raw
NaiveStringMatch.cpp
#include<stdio.h>
#include<conio.h>
#include<string.h>
#define MAX 50
int main()
{ char T[MAX]="ATGGTPTPTPTPTPFFFTFT";
char P[MAX]="FFT";
int n,m,s,i;//s for shift position
n=strlen(T);
m=strlen(P);
printf("string is %s\n",T);
printf("string pattern to match %s\n",P);
for (s=0;s<=n-m;s++)
{
for(i=0;i<m;i++)
{
if(P[i]!=T[s+i])
{
break;
}
}
if(i==m)
{
printf("\n Match occur with shift %d",s);
getch();
return 0;
}
}
getch();
return 0;
}
Raw
RabinKarp.cpp
#include<stdio.h>
#include<string.h>
#define d 256
int main()
{ char txt[80],pat[10];
printf("\n ** Rabinkarp Pattern Matcher **\n\n");
printf("Enter the text string: ");
gets(txt);
printf("\nEnter the pattern to be searched: ");
gets(pat);
int q = 101;
int M = strlen(pat);
int N = strlen(txt);
int i, j;
int p = 0;
int t = 0;
int h = 1;
for (i = 0; i < M-1; i++)
h = (h*d)%q;
for (i = 0; i < M; i++)
{
p = (d*p + pat[i])%q;
t = (d*t + txt[i])%q;
}
for (i = 0; i <= N - M; i++)
{
if ( p == t )
{
for (j = 0; j < M; j++)
{
if (txt[i+j] != pat[j])
break;
}
if (j == M)
{
printf("Pattern found at index %d \n", i);
}
}
if ( i < N-M )
{
t = (d*(t - txt[i]*h) + txt[i+M])%q;
if(t < 0)
t = (t + q);
}
}
getchar();
return 0;}
Raw
StringMatchingFiniteAutomata.cpp
#include<stdio.h>
#include<conio.h>
#include<string.h>
char t[100];
char p[100];
int m,n,i,j=0,k,x,q,d[100][26],l;
void compute_transition_function()
{
m=strlen(p);
for(q=0;q<=m;q++)
{
for(i=0;i<l;i++)
{
if(m<q+1)
{k=m;x=1;}
else {k=q+1;
x=0;}
while(k!=0)
{
j=0;
while(p[j]==p[x+j]&&j<k-1)
j++;
if(p[j]==i+97)
j++;
if(j==k)
break;
else {k--;x++;}
}
d[q][i]=k;
}
}
}
void finite_automaton_matcher()
{
n=strlen(t);
m=strlen(p);
q=0;
for(i=0;i<n;i++)
{
q=d[q][t[i]-97];
if(q==m)
printf("pattern occur with shift %d\n",i-m+1);
}
}
int main()
{
printf("\n ** Finite_Automata Pattern Matcher **\n\n");
printf("Enter the text: ");
gets(t);
printf("Enter pattern: ");
gets(p);
printf("Enter no. of chars: ");
scanf("%d",&l);
compute_transition_function();
finite_automaton_matcher();
printf("\nTransition Function :\n\n");
for(i=0;i<=m;i++)
{
for(j=0;j<l;j++)
{
printf("%d\t",d[i][j]);
}
printf("\n");
}
getch();
return 0;
}
Raw
StronglyConnectedComponents.cpp
# include<stdio.h>
# include<conio.h >
#define NIL -1
enum c{white=-5,gray,black};
int n;
int d[6],f[6],a[6],time;
int graph[6][6]={{0,1,0,0,0,1},{0,0,0,0,1,0},{0,0,0,1,1,0},{0,0,0,0,0,0},{0,0,0,0,0,0},{0,1,0,0,1,0}};
int color[6],pred[6];
int gt[6][6],k=6;
void DFS_VISIT(int u)
{
int v;
color[u]=gray;
time++;
d[u]=time;
for(v=0;v<6;v++)
{
if(graph[u][v]!=0)
{
if(color[v]==white)
{
pred[v]=u;
DFS_VISIT(v);
}
}
}
color[u]=black;
printf("%4d",u);
f[u]=++time;
a[k-1]=u;
k--;
}
void transpose()// Transpose Graph
{
int i,j;
for(i=0;i<6;i++)
{
for(j=0;j<6;j++)
{
gt[i][j]=graph[j][i];
}
}
}
void dfs2(int u) // DFS of Transposed Graph, u=a[i], Parameter is nodes finished in decr order
{
int j;
color[u]=black;
for(j=0;j<6;j++)
{
if(gt[u][j]!=0)
{
if(color[j]==white)
dfs2(j);
}
}
printf("%d\t",u);
}
int main()
{
int i,j,count=0;;
time=0;
for(i=0;i<6;i++) // Initialize
{
color[i]=white;
pred[i]=NIL;
}
printf("\nThe DFS traversal of the graph as:\n\n");
for(i=0;i<6;i++)
{
if(color[i]==white)
DFS_VISIT(i); // call DFS_Visit(u)
}
printf("\n\n\nThe discovery & finishing time of the vertices are:\n\n\n");
for(i=0;i<6;i++)
{
printf("For vertex %d : \td[%d]=%d f[%d]=%d\n",i,i,d[i],i,f[i]);
}
transpose();
for(i=0;i<6;i++) // initialize for SCC
{
color[a[i]]=white;
}
for(i=0;i<6;i++)
{
if(color[a[i]]==white)
{
count++;
printf("\n\nStrongly Connected Component %d --> ",count);
dfs2(a[i]);
}
}
getch();
return 0;
}
Raw
TopologicalSort.cpp
# include<stdio.h>
# include<conio.h >
#define NIL -1
enum c{white=-5,gray,black};
int n;
int d[6],f[6],time;
int graph[6][6]={{0,1,0,0,0,1},{0,0,0,0,1,0},{0,0,0,1,1,0},{0,0,0,0,0,0},{0,0,0,0,0,0},{0,1,0,0,1,0}};
int color[6],pred[6];
void DFS_VISIT(int u)
{
int v;
color[u]=gray;
time++;
d[u]=time;
for(v=0;v<6;v++)
{
if(graph[u][v]!=0)
{
if(color[v]==white)
{
pred[v]=u;
DFS_VISIT(v);
}
}
}
color[u]=black;
printf("%5d",u);
f[u]=++time;
}
int main()
{
int i,j;
time=0;
for(i=0;i<6;i++)
{
color[i]=white;
pred[i]=NIL;
}
printf("The DFS traversal of the graph gives:\n");
for(i=0;i<6;i++)
{
if(color[i]==white)
DFS_VISIT(i); // call DFS_Visit(u)
}
printf("\n\nThe discovery & finishing time of the vertices are:\n");
for(i=0;i<6;i++)
{
printf("For vertex %d\n\td[%d]=%d \tf[%d]=%d\n",i,i,d[i],i,f[i]);
}
int highest;
int idx;
printf("\n\nTopological Sort :\t", idx);
for( j = 0; j < 6; ++j)
{
highest = f[j];
for(i = 0; i < 6; ++i)
{
if(f[i] > highest)
{
highest = f[i];
idx = i;
}
}
printf("%d\t", idx);
f[idx] = -1;
}
getch();
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment