cmrmahesh · November 10, 2016 07:14 · Nov 10, 2016
diff --git a/AssemblyLineScheduling.cpp b/AssemblyLineScheduling.cpp
@@ -0,0 +1,86 @@
+#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;
+}
diff --git a/BellmanFord.cpp b/BellmanFord.cpp
@@ -0,0 +1,80 @@
+#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;
+}
diff --git a/BinomialHeap.cpp b/BinomialHeap.cpp
@@ -0,0 +1,365 @@
+#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);
+}
diff --git a/DijkstraDAG.cpp b/DijkstraDAG.cpp
@@ -0,0 +1,62 @@
+#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();
+}
diff --git a/FFT.cpp b/FFT.cpp
@@ -0,0 +1,89 @@
+#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();
+}
diff --git a/FibonacciHeap.cpp b/FibonacciHeap.cpp
@@ -0,0 +1,97 @@
+#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 ");
+ }
+}
+}
diff --git a/FloydWarshall.cpp b/FloydWarshall.cpp
@@ -0,0 +1,47 @@
+#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;} 
diff --git a/KMP.cpp b/KMP.cpp
@@ -0,0 +1,55 @@
+#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();
+}
diff --git a/MatrixChainMultiplication.cpp b/MatrixChainMultiplication.cpp
@@ -0,0 +1,75 @@
+# 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;
+}
diff --git a/NaiveStringMatch.cpp b/NaiveStringMatch.cpp
@@ -0,0 +1,31 @@
+#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;
+}
diff --git a/RabinKarp.cpp b/RabinKarp.cpp
@@ -0,0 +1,47 @@
+#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;} 
diff --git a/StringMatchingFiniteAutomata.cpp b/StringMatchingFiniteAutomata.cpp
@@ -0,0 +1,67 @@
+#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;
+}
diff --git a/StronglyConnectedComponents.cpp b/StronglyConnectedComponents.cpp
@@ -0,0 +1,94 @@
+# 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;
+}
diff --git a/TopologicalSort.cpp b/TopologicalSort.cpp
@@ -0,0 +1,69 @@
+# 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;
+}
No results found