Algorithm Analysis And Design Complete File
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Algorithm Analysis And Design Complete File as PDF for free.
More details
- Words: 3,330
- Pages: 50
University School of Information Technology, G.G.S.I.PU.
ALGORITHM ANALYSIS AND DESIGN FILE
Submitted By : ANUP SINGH KUSHWAHA
Enrol
no: 0111645308
// Program to implement Breadth-First-Search (BFS) #include<stdio.h> #include #include<stdlib.h> #define MAX 100 void bfs(int n,int s); void enqueue(int q[],int m); int dequeue(int q[]); int color[MAX]; int d[MAX]; int pi[MAX]; typedef struct vert* ver; struct vert { int ident; ver next; } cor; ver adj_list[MAX]; void main() { int n,i,j,k,s,u; ver temp,prev; clrscr(); printf("Enter no of nodes : "); scanf("%d",&n); for(i=0;i<=n;i++) adj_list[i]='\0'; for(i=1;i<=n;i++) { prev=NULL; printf("Enter No of vertex connected to %d :",i); scanf("%d",&j); for(k=0;k<j;k++) { temp=(ver)malloc(sizeof(cor)); temp->next=NULL; printf("Enter Vertex No. connected to vertex %d : ",i); scanf("%d",&temp->ident); if(prev==NULL) adj_list[i]=temp; else prev->next=temp; prev=temp; }
} printf("\nEnter the starting point of graph : "); scanf("%d",&s); bfs(n,s); for(i=1;i<=n;i++) { printf("\nThe Distance from source(%d) to %d is %d",s,i,d[i]); printf("\nThe previous vertex of %d is %d",i,pi[i]); } getch(); } void bfs(int n,int s) { int i,v,q[MAX],u; ver temp; for(i=1;i<=n;i++) { if(i==s) continue; color[i]=0; d[i]=32767; pi[i]=NULL; } color[s]=1; d[s]=0; pi[s]=NULL; for(i=0;i<=n;i++) q[i]='\0'; enqueue(q,s); while(q[0]!='\0') { u=dequeue(q); temp=adj_list[u]; while(temp!=NULL) { v=temp->ident; if(color[v]==0) { color[v]=1; d[v]=d[u]+1; pi[v]=u; enqueue(q,v); } temp=temp->next; } color[u]=2; } } void enqueue(int q[MAX],int m)
{ int i=0; while(q[i]!='\0') { i++; } q[i]=m; } int dequeue(int q[MAX]) { int i=0,ret; ret=q[i]; while(q[i]!='\0') { q[i]=q[i+1]; i++; } return ret; }
//PROGRAM FOR COUNTING INVERSION WITH O(n SQUARE) COMPLEXITY #include #include int count_inver(int [],int); void main() { int a[100],n,i,c; clrscr(); cout<<"Enter the total number of elements in the array:"; cin>>n; cout<<"Enter the elements in the array\n"; for(i=0;i>a[i]; } c=count_inver(a,n); cout<<"\nThe total number of counting inverse is "<x[j]) { cout<<"\n"<<x[i]<<x[j]; c++; } return c; }
//PROGRAM FOR COUNTING INVERSION #include #include int a[100],b[100],d,n,low,high; void sortandcount(int,int); void mergeandcount(int,int,int); void main() { int i; clrscr(); cout<<"\n Enter the lengh of the series"; cin>>n; cout<<"\n Enter the series"; for(i=0;i>a[i]; low=0; high=n-1; sortandcount(low,high); cout<<"\nThe total number of inversions is "<
if(l>mid) { for(k=m;k<=high;k++) { b[h]=a[k]; h++; } } else { for(k=l;k<=mid;k++) { b[h]=a[k]; h++; } } for(i=low;i<=high;i++) a[i]=b[i]; d=counter; }
// Program to implement Depth-First-Search (DFS) #include<stdio.h> #include #include<stdlib.h> #define MAX 100 void dfs(int n); void dfs_visit(int u); int color[MAX]; int d[MAX]; int f[MAX]; int time; typedef struct vert* ver; struct vert { int ident; ver next; } cor; ver adj_list[MAX]; void main() { int n,i,j,k; ver temp,prev; clrscr(); printf("Enter no of nodes : "); scanf("%d",&n); for(i=0;i<=n;i++) adj_list[i]='\0'; for(i=1;i<=n;i++) { prev=NULL; printf("Enter No of vertex connected to %d :",i); scanf("%d",&j); for(k=0;k<j;k++) { temp=(ver)malloc(sizeof(cor)); temp->next=NULL; printf("Enter Vertex No. connected to vertex %d : ",i); scanf("%d",&temp->ident); if(prev==NULL) adj_list[i]=temp; else prev->next=temp; prev=temp; } }
dfs(n); for(i=1;i<=n;i++) { printf("\nStarting/Ending time of Vertex %d is %d/%d",i,d[i],f[i]); } getch(); } void dfs(int n) { int i; for(i=1;i<=n;i++) color[i]=0; time=0; for(i=1;i<=n;i++) { if(color[i]==0) dfs_visit(i); } } void dfs_visit(int u) { ver temp; color[u]=1; time++; d[u]=time; temp=adj_list[u]; while(temp!=NULL) { if(color[temp->ident]==0) dfs_visit(temp->ident); temp=temp->next; } color[u]=2; f[u]=++time; }
//PROGRAM FOR DIJKSTRA'S ALGORITHM #include #include int cost[50][50],b[50],dist[50],n; int find(int*,int*,int); void main() { clrscr(); int i,j,num,v,u; cout<<"enter the no of nodes in the graph : "<<endl; cin>>n; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) cost[i][j]=0; } cout<<"\nenter the weights of the graph : (Enter 1000 if no edge exists between 2 nodes) "; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) cin>>cost[i][j]; } //print the cost matrix in matrix form for(i=1;i<=n;i++) { cout<<endl; for(j=1;j<=n;j++) cout<<"\t"<>v; for(i=1;i<=n;i++) { dist[i]=cost[v][i]; b[v]=1; dist[v]=0; } for(num=2;num<=n-1;num++) { u=find(dist,b,n); b[u]=1; for(int w=1;w<=n;w++) { if((cost[u][w]!=1000 )&& b[w]==0) {
if(dist[w]> dist[u]+cost[u][w]) { dist[w]=dist[u]+cost[u][w]; } } } } cout<<"the distance matrix is :\n "; for(i=1;i<=n;i++) cout<<" "<
//PROGRAM FOR EUCLID'S ALGORITHM #include #include int euclid(int a,int b) { if(b==0) return a; else return euclid(b,a%b); } void main() { int a,b,gcd; clrscr(); cout<<"Enter 2 numbers whose gcd is to be found"; cin>>a>>b; gcd=euclid(a,b); cout<
//PROGRAM FOR EXTENDED EUCLID'S ALGORITHM #include #include int * exteuclid(int a,int b) { int *z; int d,x,y; if(b==0) { z[0]=a; z[1]=1; z[2]=0; cout<<"\n"; cout<>a>>b; gcd=exteuclid(a,b); cout<<"\n"; cout<< "GCD is"; cout<
//PROGRAM FOR KRUSHKAL'S ALGORITHM #include #include #define infinity 1000 int num_of_nodes; int cost[10][10]; int parent[10]; int solution[10][2]; int min_edge(int *, int *); int find(int); void unite(int, int); void main() { int i = 0; int j = 0; int k = 0; int u = 0; int v = 0; int min_cost = 0; int cost_of_uv = 0; clrscr(); cout<<"\nEnter the number of nodes in the graph: "; cin>>num_of_nodes; cout<<"\n!!!!!!!! Enter 1000 for a not connected link!!!!!!\n"; for(i=0;i>cost[i][j]; cost[j][i]=cost[i][j]; if(cost[i][j]>=infinity) cost[i][j]=infinity; } } i=0; while((i
i=i+1; } } if(i!=num_of_nodes-1) cout<<"\n No spanning tree "; else { cout<<"\nSpanning tree is: "; for(i=0;icost[i][j]) { min=cost[i][j]; u=i; v=j; } } } } cost[u][v] = -1; *x=u; *y=v; return min; } int find(int i) { while(parent[i]>=0) i = parent[i]; return i; } void unite(int i,int j) { parent[i]=j;}
//PROGRAM FOR LONGEST COMMON SUBSEQUENCE #include #include #include<string.h> #include<stdio.h> #define MAX 12 void LCS_Length(char[],char[],int,int); void print_LCS(char[MAX][MAX],char[],int,int); void main() { char X[10],Y[10],ans; int i,j; clrscr(); cout<<"\nEnter the first sequence(less then or equal to 10 charaters):"; gets(X); i=strlen(X); cout<<"\nEnter the second sequence:"; gets(Y); j=strlen(Y); LCS_Length(X,Y,i,j); getch(); } void LCS_Length(char X[10],char Y[10],int m,int n) { int i,j; int C[MAX][MAX]; char B[MAX][MAX]; for(i=0;i<MAX;i++) for(j=0;j<MAX;j++) B[i][j]='0'; for(i=1;i<=m;i++) C[i][0]=0; for(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+1][j+1]=C[i][j]+1; B[i+1][j+1]='\\';
} else if(C[i][j+1]>=C[i+1][j]) { C[i+1][j+1]=C[i][j+1]; B[i+1][j+1]='|'; } else { C[i+1][j+1]=C[i+1][j]; B[i+1][j+1]='-'; } } } cout<<"The C matrix is:\n"; for(i=0;i<=m;i++) { for(j=0;j<=n;j++) cout<<"\t"<
print_LCS(B,X,i-1,j-1); cout<<X[i-1]; } else if(B[i][j]=='|') print_LCS(B,X,i-1,j); else print_LCS(B,X,i,j-1); }
//PROGRAM FOR MATRIX CHAIN MULTIPLICATION ALGORITHM #include #include long int M[50][50], P[50], s[50][50]; void MatrixChain(int n) { long int i, j, k, l, q; 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]=20000; for(k=i;k<j;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; } } } } } void display(long int s[50][50],int i,int j) { if(i==j) cout<<"A"<> n; cout << "Enter the Order Array "; for(i=0;i<=n;i++) { cin >> P[i];
} MatrixChain(n); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { cout << M[i][j]<<" "; } cout<<"\n"; } cout<<"\n"; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { cout << s[i][j]<<" "; } cout<<"\n"; } display(s,1,n); getch(); }
//PROGRAM FOR MERGE SORT #include #include void mergesort(int[],int,int); void merge(int[],int,int,int); void main() { int a[10],p,q,r,i,n; clrscr(); cout<<"Enter the number of elements"; cin>>n; p=0; r=n-1; cout<<"Enter the array"; for(i=0;i>a[i]; } mergesort(a,p,r); cout<<"The sorted array is:"; for(i=0;i
k=k+1; } else { c[k]=a[j]; j=j+1; k=k+1; } } while(i<=q) { c[k] =a[i]; i=i+1; k=k+1; } while(j<=r) { c[k]=a[j]; j=j+1; k=k+1; } int l=p; while(l<=r) { a[l]=c[l]; l=l+1; } }
//PROGRAM FOR OPTIMAL BINARY SEARCH TREE #include #include float e[50][50], p[50], q[50],w[50][50]; int root[50][50]; void obst(int n,float p[],float q[]) { int i, j,l,r; float t; for(i=1;i<=n+1;i++) { e[i][i-1]=q[i-1]; w[i][i-1]=q[i-1]; } for(l=1;l<=n;l++) { for(i=1;i<=n-l+1;i++) { j=i+l-1; e[i][j]=10.0; w[i][j]=w[i][j-1]+p[j]+q[j]; for(r=i;r<=j;r++) { t=e[i][r-1] + e[r+1][j] + w[i][j]; if(t<e[i][j]) { e[i][j]=t; root[i][j]=r; } } } } } void main() { int n, i, j; clrscr(); cout << "Enter the no of keys : "; cin >> n; cout << "Enter the array p "; for(i=1;i<=n;i++) { cin >> p[i]; } cout << "Enter the array q "; for(i=0;i<=n;i++) { cin >> q[i]; }
obst(n,p,q); for(i=1;i<=n+1;i++) { for(j=0;j<=n;j++) { cout << e[i][j]<<" "; } cout<<"\n"; } cout<<"\n"; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { cout << root[i][j]<<" "; } cout<<"\n"; } getch(); }
//PROGRAM FOR PRIM'S ALGORITHM #include #include #define infinity 1000 int num_of_nodes; int nodes[10][10][2]; int near_edges[10]; int temp[50]; int solution[10][2]; void min_edge(int *, int *); int srch_min_near_edge(void); void main() { int i = 0; int j = 0; int k = 0; int u = 0; int v = 0; int min_cost = 0; clrscr(); cout<<"\nEnter the number of nodes in the graph: "; cin>>num_of_nodes; cout<<"\n!!!!!!!! Enter 1000 for a not connected link!!!!!!\n"; for(i=0;i>nodes[i][j][0]; nodes[j][i][0]=nodes[i][j][0]; if(nodes[i][j][0]>=infinity) { nodes[i][j][1]=1; nodes[j][i][1]=1; } else { nodes[i][j][1]=0; nodes[j][i][1]=1; } } } min_edge(&u, &v); min_cost=nodes[u][v][0]; solution[0][0]=u; solution[0][1]=v; for(i=0;i
{ if(nodes[i][u][0] < nodes[i][v][0]) near_edges[i] = u; else { if((nodes[i][u][0]==infinity) && (nodes[i][v][0]==infinity)) near_edges[i]=infinity; else near_edges[i]=v; } } near_edges[u] = -1; near_edges[v] = -1; for(i = 1; i < num_of_nodes-1; i++) { j=srch_min_near_edge(); solution[i][0]=j; solution[i][1]=near_edges[j]; min_cost=min_cost+nodes[j][near_edges[j]][0]; near_edges[j]=-1; for(k=0;knodes[k][j][0])) near_edges[k]=j; } else near_edges[k] = j; } } cout<<"\nMinimum cost spanning tree is: \n"; for(i=0;i
if(min>nodes[i][j][0]) { min=nodes[i][j][0]; u=i; v=j; } } } } nodes[u][v][1]=1; *x=u; *y=v; } int srch_min_near_edge(void) { int edge; int min=1000; int i=0; for(i=0;inodes[i][near_edges[i]][0]) && (nodes[i][near_edges[i]][0]!=infinity)) { min=nodes[i][near_edges[i]][0]; edge=i; } } } return edge; }
//PROGRAM FOR STRASSEN'S MATRIX MULTIPLICATION #include #include void main() { int a[2][2],b[2][2],c[2][2],i,j; int p1,p2,p3,p4,p5,p6,p7; clrscr(); cout << "Enter the first matrix : "; for(i=1;i<=2;i++) for(j=1;j<=2;j++) cin >> a[i][j]; cout << "Enter the second matrix : "; for(i=1;i<=2;i++) for(j=1;j<=2;j++) cin >> b[i][j]; p1=a[1][1]*(b[1][2]-b[2][2]); p2=(a[1][1]+a[1][2])*b[2][2]; p3=(a[2][1]+a[2][2])*b[1][1]; p4=a[2][2]*(b[2][1]-b[1][1]); p5=(a[1][1]+a[2][2])*(b[1][1]+b[2][2]); p6=(a[1][2]-a[2][2])*(b[2][1]+b[2][2]); p7=(a[1][1]-a[2][1])*(b[1][1]+b[1][2]); c[1][1]=p5+p4-p2+p6; c[1][2]=p1+p2; c[2][1]=p3+p4; c[2][2]=p5+p1-p3-p7; for(i=1;i<=2;i++) { for(j=1;j<=2;j++) { cout<< c[i][j]<<" "; } cout<<"\n"; } getch(); }
//PROGRAM FOR TASK SCHEDULING PROBLEM #include #include struct task { int deadl; int cost; }task[20],temp; void main() { int i,j,n,p[20],count=0,c=0,ans[20],ex[10],penalty=0,temp1=1,x=0; clrscr(); cout<<"Enter the number of tasks"; cin>>n; cout<<"\nEnter dead line and cost of each task\n" " dead line cost\n"; for(i=0;i>task[i].deadl>>task[i].cost; p[i]=-1; } for(i=0;i0) { if(p[c]==-1) {temp1=0; p[c]=0; ans[count++]=i; break; } c--;
} if(temp1==1) { ex[x++]=i; penalty=penalty+task[i].cost; } } } for(i=0;i=task[ans[j]].deadl) {temp1=ans[i]; ans[i]=ans[j]; ans[j]=temp1; } } } cout<<"\n The scheduled tasks are \n "; for(i=0;i
OUTPUT Enter the number of activities11 Enter the start point and end points of the activities 1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14 The set of activities selected are A1 A4 A8 A11
OUTPUT Enter the total number of elements in the array:5 Enter the elements in the array 2 4 1 3 5 21 41 43 The total number of counting inverse is 3
OUTPUT enter the no of nodes in the graph : 6 enter the weights of the graph : (Enter 1000 if no edge exists between 2 nodes) 0 50 45 10 1000 1000 1000 0 10 15 1000 1000 1000 1000 0 1000 30 1000 20 1000 1000 0 15 1000 1000 20 35 1000 0 1000 1000 1000 1000 1000 3 0 0 50 45 10 1000 1000 1000 0 10 15 1000 1000 1000 1000 0 1000 30 1000 20 1000 1000 0 15 1000 1000 20 35 1000 0 1000 1000 1000 1000 1000 3 0
input the source vertex : 1 the distance matrix is : 0 45 45 10 25 1000
OUTPUT Enter 2 numbers whose gcd is to be found21 9 3
OUTPUT Enter 2 numbers whose gcd is to be found99 78 3 0 3 6 3 3 15 6 3 21 15 3 78 21 3 99 78 3 GCD is3
1 0 1 -2 3 -11
0 1 -2 3 -11 14
OUTPUT Enter the lengh of the series5 Enter the series2 4 1 3 5 The total number of inversions is 3
OUTPUT Enter the number of nodes in the graph: 5 !!!!!!!! Enter 1000 for a not connected link!!!!!! Enter the cost from node 1 to node 2 1 Enter the cost from node 1 to node 3 2 Enter the cost from node 1 to node 4 2 Enter the cost from node 1 to node 5 1000 Enter the cost from node 2 to node 3 1 Enter the cost from node 2 to node 4 4 Enter the cost from node 2 to node 5 1000 Enter the cost from node 3 to node 4 6 Enter the cost from node 3 to node 5 3 Enter the cost from node 4 to node 5 5 Spanning tree is: 12 23 14 35 Cost of spanning tree: 7
OUTPUT Enter the first sequence(less then or equal to 10 charaters):abcbdab Enter the second sequence:bdcaba The C matrix is: 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 1 2 0 1 1 2 2 2 0 1 1 2 2 3 0 1 2 2 2 3 0 1 2 2 3 3 0 1 2 2 3 4 The B matrix is: | | | \ \ \ | \ | | \ | | \ | | | \ | \ | | | | | | | \ | \ \ | | | \ |
0 1 2 2 3 3 4 4
The combined Matrix C & B is 0000000 0|0|0|0\1-1\1 0\1-1-1|1\2-2 0|1|1\2-2|2|2 0\1|1|2|2\3-3 0|1\2|2|2|3|3 0|1|2|2\3|3\4 0\1|2|2|3\4|4 The length of the Longest Common Subsequence is 4 The Longest Sequence is : bcba
OUTPUT Enter the no of Matrices : 6 Enter the Order Array 30 35 15 5 10 20 25 0 15750 7875 9375 11875 15125 0 0 2625 4375 7125 10500 0 0 0 750 2500 5375 0 0 0 0 1000 3500 0 0 0 0 0 5000 000000 011333 002333 000333 000045 000005 000000 ((A1(A2A3))((A4A5)A6))
OUTPUT Enter the number of elements5 Enter the array21 12 3 1 2 The sorted array is: 1 2 3 12 21
OUTPUT Enter the no of keys : 5 Enter the array p .15 .10 .05 .10 .20 Enter the array q .05 .10 .05 .05 .05 .10 0.05 0.45 0.9 1.25 1.75 2.75 0 0.1 0.4 0.7 1.2 2 0 0 0.05 0.25 0.6 1.3 0 0 0 0.05 0.3 0.9 0 0 0 0 0.05 0.5 0 0 0 0 0 0.1 11222 02224 00345 00045 00005
OUTPUT Enter the number of nodes in the graph: 5 !!!!!!!! Enter 1000 for a not connected link!!!!!! Enter the cost from node 1 to node 2 1 Enter the cost from node 1 to node 3 2 Enter the cost from node 1 to node 4 6 Enter the cost from node 1 to node 5 3 Enter the cost from node 2 to node 3 1 Enter the cost from node 2 to node 4 4 Enter the cost from node 2 to node 5 1000 Enter the cost from node 3 to node 4 2 Enter the cost from node 3 to node 5 1000 Enter the cost from node 4 to node 5 5 Minimum cost spanning tree is: 1 2 3 2 4 3 5 1 Cost of spanning tree: 7
OUTPUT Enter the first matrix : 1 2 5 1 Enter the second matrix : 2 3 6 7 14 17 16 22
OUTPUT Enter the number of tasks7 Enter dead line and cost of each task dead line cost 4 70 2 60 4 50 3 40 1 30 4 20 6 10 The scheduled tasks are T2 T4 T3 T1 T7 T5 T6 Total penalty is50
OUTPUT Enter no of nodes : 5 Enter No of vertex connected to 1 :3 Enter Vertex No. connected to vertex 1 : 2 Enter Vertex No. connected to vertex 1 : 3 Enter Vertex No. connected to vertex 1 : 4 Enter No of vertex connected to 2 :3 Enter Vertex No. connected to vertex 2 : 1 Enter Vertex No. connected to vertex 2 : 3 Enter Vertex No. connected to vertex 2 : 4 Enter No of vertex connected to 3 :3 Enter Vertex No. connected to vertex 3 : 2 Enter Vertex No. connected to vertex 3 : 4 Enter Vertex No. connected to vertex 3 : 5 Enter No of vertex connected to 4 :4 Enter Vertex No. connected to vertex 4 : 1 Enter Vertex No. connected to vertex 4 : 2 Enter Vertex No. connected to vertex 4 : 3 Enter Vertex No. connected to vertex 4 : 5 Enter No of vertex connected to 5 :2 Enter Vertex No. connected to vertex 5 : 3 Enter Vertex No. connected to vertex 5 : 4 Enter the starting point of graph : 1 The Distance from source(1) to 1 is 0 The previous vertex of 1 is 0 The Distance from source(1) to 2 is 1 The previous vertex of 2 is 1 The Distance from source(1) to 3 is 1 The previous vertex of 3 is 1 The Distance from source(1) to 4 is 1 The previous vertex of 4 is 1 The Distance from source(1) to 5 is 2 The previous vertex of 5 is 3
OUTPUT Enter no of nodes : 5 Enter No of vertex connected to 1 :3 Enter Vertex No. connected to vertex 1 : 2 Enter Vertex No. connected to vertex 1 : 3 Enter Vertex No. connected to vertex 1 : 4 Enter No of vertex connected to 2 :3 Enter Vertex No. connected to vertex 2 : 1 Enter Vertex No. connected to vertex 2 : 3 Enter Vertex No. connected to vertex 2 : 4 Enter No of vertex connected to 3 :3 Enter Vertex No. connected to vertex 3 : 1 Enter Vertex No. connected to vertex 3 : 4 Enter Vertex No. connected to vertex 3 : 5 Enter No of vertex connected to 4 :4 Enter Vertex No. connected to vertex 4 : 1 Enter Vertex No. connected to vertex 4 : 2 Enter Vertex No. connected to vertex 4 : 3 Enter Vertex No. connected to vertex 4 : 5 Enter No of vertex connected to 5 :2 Enter Vertex No. connected to vertex 5 : 3 Enter Vertex No. connected to vertex 5 : 4 Starting/Ending time of Vertex 1 is 1/10 Starting/Ending time of Vertex 2 is 2/9 Starting/Ending time of Vertex 3 is 3/8 Starting/Ending time of Vertex 4 is 4/7 Starting/Ending time of Vertex 5 is 5/6
INDEX S.No.
Program
Date
Signature
ALGORITHM ANALYSIS AND DESIGN FILE
Submitted By : ANUP SINGH KUSHWAHA
Enrol
no: 0111645308
// Program to implement Breadth-First-Search (BFS) #include<stdio.h> #include
} printf("\nEnter the starting point of graph : "); scanf("%d",&s); bfs(n,s); for(i=1;i<=n;i++) { printf("\nThe Distance from source(%d) to %d is %d",s,i,d[i]); printf("\nThe previous vertex of %d is %d",i,pi[i]); } getch(); } void bfs(int n,int s) { int i,v,q[MAX],u; ver temp; for(i=1;i<=n;i++) { if(i==s) continue; color[i]=0; d[i]=32767; pi[i]=NULL; } color[s]=1; d[s]=0; pi[s]=NULL; for(i=0;i<=n;i++) q[i]='\0'; enqueue(q,s); while(q[0]!='\0') { u=dequeue(q); temp=adj_list[u]; while(temp!=NULL) { v=temp->ident; if(color[v]==0) { color[v]=1; d[v]=d[u]+1; pi[v]=u; enqueue(q,v); } temp=temp->next; } color[u]=2; } } void enqueue(int q[MAX],int m)
{ int i=0; while(q[i]!='\0') { i++; } q[i]=m; } int dequeue(int q[MAX]) { int i=0,ret; ret=q[i]; while(q[i]!='\0') { q[i]=q[i+1]; i++; } return ret; }
//PROGRAM FOR COUNTING INVERSION WITH O(n SQUARE) COMPLEXITY #include
//PROGRAM FOR COUNTING INVERSION #include
if(l>mid) { for(k=m;k<=high;k++) { b[h]=a[k]; h++; } } else { for(k=l;k<=mid;k++) { b[h]=a[k]; h++; } } for(i=low;i<=high;i++) a[i]=b[i]; d=counter; }
// Program to implement Depth-First-Search (DFS) #include<stdio.h> #include
dfs(n); for(i=1;i<=n;i++) { printf("\nStarting/Ending time of Vertex %d is %d/%d",i,d[i],f[i]); } getch(); } void dfs(int n) { int i; for(i=1;i<=n;i++) color[i]=0; time=0; for(i=1;i<=n;i++) { if(color[i]==0) dfs_visit(i); } } void dfs_visit(int u) { ver temp; color[u]=1; time++; d[u]=time; temp=adj_list[u]; while(temp!=NULL) { if(color[temp->ident]==0) dfs_visit(temp->ident); temp=temp->next; } color[u]=2; f[u]=++time; }
//PROGRAM FOR DIJKSTRA'S ALGORITHM #include
if(dist[w]> dist[u]+cost[u][w]) { dist[w]=dist[u]+cost[u][w]; } } } } cout<<"the distance matrix is :\n "; for(i=1;i<=n;i++) cout<<" "<
//PROGRAM FOR EUCLID'S ALGORITHM #include
//PROGRAM FOR EXTENDED EUCLID'S ALGORITHM #include
//PROGRAM FOR KRUSHKAL'S ALGORITHM #include
i=i+1; } } if(i!=num_of_nodes-1) cout<<"\n No spanning tree "; else { cout<<"\nSpanning tree is: "; for(i=0;i
//PROGRAM FOR LONGEST COMMON SUBSEQUENCE #include
} else if(C[i][j+1]>=C[i+1][j]) { C[i+1][j+1]=C[i][j+1]; B[i+1][j+1]='|'; } else { C[i+1][j+1]=C[i+1][j]; B[i+1][j+1]='-'; } } } cout<<"The C matrix is:\n"; for(i=0;i<=m;i++) { for(j=0;j<=n;j++) cout<<"\t"<
print_LCS(B,X,i-1,j-1); cout<<X[i-1]; } else if(B[i][j]=='|') print_LCS(B,X,i-1,j); else print_LCS(B,X,i,j-1); }
//PROGRAM FOR MATRIX CHAIN MULTIPLICATION ALGORITHM #include
} MatrixChain(n); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { cout << M[i][j]<<" "; } cout<<"\n"; } cout<<"\n"; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { cout << s[i][j]<<" "; } cout<<"\n"; } display(s,1,n); getch(); }
//PROGRAM FOR MERGE SORT #include
k=k+1; } else { c[k]=a[j]; j=j+1; k=k+1; } } while(i<=q) { c[k] =a[i]; i=i+1; k=k+1; } while(j<=r) { c[k]=a[j]; j=j+1; k=k+1; } int l=p; while(l<=r) { a[l]=c[l]; l=l+1; } }
//PROGRAM FOR OPTIMAL BINARY SEARCH TREE #include
obst(n,p,q); for(i=1;i<=n+1;i++) { for(j=0;j<=n;j++) { cout << e[i][j]<<" "; } cout<<"\n"; } cout<<"\n"; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { cout << root[i][j]<<" "; } cout<<"\n"; } getch(); }
//PROGRAM FOR PRIM'S ALGORITHM #include
{ if(nodes[i][u][0] < nodes[i][v][0]) near_edges[i] = u; else { if((nodes[i][u][0]==infinity) && (nodes[i][v][0]==infinity)) near_edges[i]=infinity; else near_edges[i]=v; } } near_edges[u] = -1; near_edges[v] = -1; for(i = 1; i < num_of_nodes-1; i++) { j=srch_min_near_edge(); solution[i][0]=j; solution[i][1]=near_edges[j]; min_cost=min_cost+nodes[j][near_edges[j]][0]; near_edges[j]=-1; for(k=0;k
if(min>nodes[i][j][0]) { min=nodes[i][j][0]; u=i; v=j; } } } } nodes[u][v][1]=1; *x=u; *y=v; } int srch_min_near_edge(void) { int edge; int min=1000; int i=0; for(i=0;i
//PROGRAM FOR STRASSEN'S MATRIX MULTIPLICATION #include
//PROGRAM FOR TASK SCHEDULING PROBLEM #include
} if(temp1==1) { ex[x++]=i; penalty=penalty+task[i].cost; } } } for(i=0;i
OUTPUT Enter the number of activities11 Enter the start point and end points of the activities 1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14 The set of activities selected are A1 A4 A8 A11
OUTPUT Enter the total number of elements in the array:5 Enter the elements in the array 2 4 1 3 5 21 41 43 The total number of counting inverse is 3
OUTPUT enter the no of nodes in the graph : 6 enter the weights of the graph : (Enter 1000 if no edge exists between 2 nodes) 0 50 45 10 1000 1000 1000 0 10 15 1000 1000 1000 1000 0 1000 30 1000 20 1000 1000 0 15 1000 1000 20 35 1000 0 1000 1000 1000 1000 1000 3 0 0 50 45 10 1000 1000 1000 0 10 15 1000 1000 1000 1000 0 1000 30 1000 20 1000 1000 0 15 1000 1000 20 35 1000 0 1000 1000 1000 1000 1000 3 0
input the source vertex : 1 the distance matrix is : 0 45 45 10 25 1000
OUTPUT Enter 2 numbers whose gcd is to be found21 9 3
OUTPUT Enter 2 numbers whose gcd is to be found99 78 3 0 3 6 3 3 15 6 3 21 15 3 78 21 3 99 78 3 GCD is3
1 0 1 -2 3 -11
0 1 -2 3 -11 14
OUTPUT Enter the lengh of the series5 Enter the series2 4 1 3 5 The total number of inversions is 3
OUTPUT Enter the number of nodes in the graph: 5 !!!!!!!! Enter 1000 for a not connected link!!!!!! Enter the cost from node 1 to node 2 1 Enter the cost from node 1 to node 3 2 Enter the cost from node 1 to node 4 2 Enter the cost from node 1 to node 5 1000 Enter the cost from node 2 to node 3 1 Enter the cost from node 2 to node 4 4 Enter the cost from node 2 to node 5 1000 Enter the cost from node 3 to node 4 6 Enter the cost from node 3 to node 5 3 Enter the cost from node 4 to node 5 5 Spanning tree is: 12 23 14 35 Cost of spanning tree: 7
OUTPUT Enter the first sequence(less then or equal to 10 charaters):abcbdab Enter the second sequence:bdcaba The C matrix is: 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 1 2 0 1 1 2 2 2 0 1 1 2 2 3 0 1 2 2 2 3 0 1 2 2 3 3 0 1 2 2 3 4 The B matrix is: | | | \ \ \ | \ | | \ | | \ | | | \ | \ | | | | | | | \ | \ \ | | | \ |
0 1 2 2 3 3 4 4
The combined Matrix C & B is 0000000 0|0|0|0\1-1\1 0\1-1-1|1\2-2 0|1|1\2-2|2|2 0\1|1|2|2\3-3 0|1\2|2|2|3|3 0|1|2|2\3|3\4 0\1|2|2|3\4|4 The length of the Longest Common Subsequence is 4 The Longest Sequence is : bcba
OUTPUT Enter the no of Matrices : 6 Enter the Order Array 30 35 15 5 10 20 25 0 15750 7875 9375 11875 15125 0 0 2625 4375 7125 10500 0 0 0 750 2500 5375 0 0 0 0 1000 3500 0 0 0 0 0 5000 000000 011333 002333 000333 000045 000005 000000 ((A1(A2A3))((A4A5)A6))
OUTPUT Enter the number of elements5 Enter the array21 12 3 1 2 The sorted array is: 1 2 3 12 21
OUTPUT Enter the no of keys : 5 Enter the array p .15 .10 .05 .10 .20 Enter the array q .05 .10 .05 .05 .05 .10 0.05 0.45 0.9 1.25 1.75 2.75 0 0.1 0.4 0.7 1.2 2 0 0 0.05 0.25 0.6 1.3 0 0 0 0.05 0.3 0.9 0 0 0 0 0.05 0.5 0 0 0 0 0 0.1 11222 02224 00345 00045 00005
OUTPUT Enter the number of nodes in the graph: 5 !!!!!!!! Enter 1000 for a not connected link!!!!!! Enter the cost from node 1 to node 2 1 Enter the cost from node 1 to node 3 2 Enter the cost from node 1 to node 4 6 Enter the cost from node 1 to node 5 3 Enter the cost from node 2 to node 3 1 Enter the cost from node 2 to node 4 4 Enter the cost from node 2 to node 5 1000 Enter the cost from node 3 to node 4 2 Enter the cost from node 3 to node 5 1000 Enter the cost from node 4 to node 5 5 Minimum cost spanning tree is: 1 2 3 2 4 3 5 1 Cost of spanning tree: 7
OUTPUT Enter the first matrix : 1 2 5 1 Enter the second matrix : 2 3 6 7 14 17 16 22
OUTPUT Enter the number of tasks7 Enter dead line and cost of each task dead line cost 4 70 2 60 4 50 3 40 1 30 4 20 6 10 The scheduled tasks are T2 T4 T3 T1 T7 T5 T6 Total penalty is50
OUTPUT Enter no of nodes : 5 Enter No of vertex connected to 1 :3 Enter Vertex No. connected to vertex 1 : 2 Enter Vertex No. connected to vertex 1 : 3 Enter Vertex No. connected to vertex 1 : 4 Enter No of vertex connected to 2 :3 Enter Vertex No. connected to vertex 2 : 1 Enter Vertex No. connected to vertex 2 : 3 Enter Vertex No. connected to vertex 2 : 4 Enter No of vertex connected to 3 :3 Enter Vertex No. connected to vertex 3 : 2 Enter Vertex No. connected to vertex 3 : 4 Enter Vertex No. connected to vertex 3 : 5 Enter No of vertex connected to 4 :4 Enter Vertex No. connected to vertex 4 : 1 Enter Vertex No. connected to vertex 4 : 2 Enter Vertex No. connected to vertex 4 : 3 Enter Vertex No. connected to vertex 4 : 5 Enter No of vertex connected to 5 :2 Enter Vertex No. connected to vertex 5 : 3 Enter Vertex No. connected to vertex 5 : 4 Enter the starting point of graph : 1 The Distance from source(1) to 1 is 0 The previous vertex of 1 is 0 The Distance from source(1) to 2 is 1 The previous vertex of 2 is 1 The Distance from source(1) to 3 is 1 The previous vertex of 3 is 1 The Distance from source(1) to 4 is 1 The previous vertex of 4 is 1 The Distance from source(1) to 5 is 2 The previous vertex of 5 is 3
OUTPUT Enter no of nodes : 5 Enter No of vertex connected to 1 :3 Enter Vertex No. connected to vertex 1 : 2 Enter Vertex No. connected to vertex 1 : 3 Enter Vertex No. connected to vertex 1 : 4 Enter No of vertex connected to 2 :3 Enter Vertex No. connected to vertex 2 : 1 Enter Vertex No. connected to vertex 2 : 3 Enter Vertex No. connected to vertex 2 : 4 Enter No of vertex connected to 3 :3 Enter Vertex No. connected to vertex 3 : 1 Enter Vertex No. connected to vertex 3 : 4 Enter Vertex No. connected to vertex 3 : 5 Enter No of vertex connected to 4 :4 Enter Vertex No. connected to vertex 4 : 1 Enter Vertex No. connected to vertex 4 : 2 Enter Vertex No. connected to vertex 4 : 3 Enter Vertex No. connected to vertex 4 : 5 Enter No of vertex connected to 5 :2 Enter Vertex No. connected to vertex 5 : 3 Enter Vertex No. connected to vertex 5 : 4 Starting/Ending time of Vertex 1 is 1/10 Starting/Ending time of Vertex 2 is 2/9 Starting/Ending time of Vertex 3 is 3/8 Starting/Ending time of Vertex 4 is 4/7 Starting/Ending time of Vertex 5 is 5/6
INDEX S.No.
Program
Date
Signature
Related Documents
Algorithm Analysis And Design Complete File
April 2020 7
54109-mt----algorithm Analysis & Design
October 2019 14
Csc 323: Algorithm Design And Analysis
May 2020 12
Design And Analysis Of Algorithm Project.docx
June 2020 13
Definition About Analysis And Design Algorithm
April 2020 15
Algorithm Design
June 2020 6More Documents from ""
Blu Ray Term Paper
June 2020 8
Rajeev Ranjan Project Mca 3rd Sem
June 2020 6
Practical Fileof C
June 2020 9
Algorithm Analysis And Design Complete File
April 2020 7
09.project-hospital Management System
April 2020 28