ALGORITHMS LAB

SOURCE CODE: #include<stdio.h> int main(){ int n,rmin=999,cmin=999,rsum=0,csum=0,i,j; printf("Enter # of vertices :\n"); scanf("%d",&n); int arr[n][n]; printf("Enter adjacency matrix :\n"); for(i=0;i<n;i++) for(j=0;j<n;j++){ scanf("%d",&arr[i][j]); if(arr[i][j]==0) arr[i][j]=999; } for(i=0;i<n;i++){ rmin=999; for(j=0;j<n;j++){ if(arr[i][j] < rmin) rmin=arr[i][j]; } rsum+=rmin; for(j=0;j<n;j++) if(arr[i][j]!=999) arr[i][j]=arr[i][j]-rmin; } for(i=0;i<n;i++){ cmin=999; for(j=0;j<n;j++){ if(arr[j][i] < cmin) cmin=arr[j][i]; } csum+=cmin; for(j=0;j<n;j++) if(arr[j][i]!=999) arr[j][i]=arr[j][i]-cmin; } printf("\nsolved matrix is :\n"); for(i=0;i<n;i++,printf("\n")) for(j=0;j<n;j++) printf("%d\t",arr[i][j]); printf("Value of L at root node is %d\n",rsum+cs...

SOURCE CODE: #include<stdio.h> int sum=0,w[10],p[10],i,m,n; int max(int a,int b){ return (a>b)?a:b; } void knapsack(){ int x[10]={0},v[100][100],i,j,sum; for(i=1;i<=n;i++) for(j=0;j<=m;j++){ if(j >= w[i]) v[i][j]=max(v[i-1][j],v[i-1][j-w[i]]+p[i]); else v[i][j]=v[i-1][j]; } for(i=n,j=m;i>0&&j>0;i--){ if(v[i][j]!=v[i-1][j]){ x[i]=1; j=j-w[i]; } } printf("The Optimal solution is :\n"); for(i=1;i<=n;i++){ if(x[i]==1){ printf("X%d=1\t",i); sum=sum+p[i]; } else printf("X%d=0\t",i); } printf("\nTotal profit = %d",sum); } int main() { printf("ENTER THE NUMBER OF ITEMS: "); scanf("%d",&n); printf("ENTER THE WEIGHTS AND PROFITS OF THE ITEMS:\n"); for(i=1;i<=n;i++) scanf("%d%d",&w[i],&p[i]); printf("ENTER THE CAPACITY OF KNAPSACK: "); scanf("%d",&m); knapsa...

SOURCE CODE: #include<stdio.h> int x[20]={0},G[20][20]={0},n; void nextValue(int k){ int j; while(1){ x[k]=(x[k]+1)%(n+1); if(x[k]==0) return ; if(G[x[k-1]][x[k]] != 0){ for(j=1;j<=k-1;j++){ if(x[j] == x[k]) break;} if((j==k)&&((k<n)||((k==n)&&(G[x[n]][x[1]]!=0)))) return; } } } void hamiltonian(int k){ int i; while(1){ nextValue(k); if(x[k]==0) return; if(k==n){ printf("\n"); for(i=1;i<=n;i++) printf("%d->",x[i]); printf("%d",x[1]); } else{ hamiltonian(k+1); } } } int main(){ int i,j,v1,v2,edge; printf("Enter # of vertices:\n"); scanf("%d",&n); printf("Enter # of edges :\n"); scanf("%d",&edge); /* for(i=1;i<=n;i++) for(j=1;j<=n;j++){ G[i][j]=0; x[i]=0; }*/ for(i=1;i<=edge;i++){ printf("\nEnter edge %d :",i); scanf("%d%d...

Source code: #include<stdio.h> #include<math.h> int board[20]; int place(int r,int c){ int i; for(i=1;i<=r-1;i++){ if((board[i]==c) || (abs(board[i]-c) == abs(i-r))) return 0; } return 1; } void display(int n){ int i,j; printf("Solution :\n"); for(i=1;i<=n;i++,printf("\n")){ for(j=1;j<=n;j++){ if(board[i] == j) printf("Q\t"); else printf("-\t"); } } } void queen(int r,int n){ int c; for(c=1;c<=n;c++){ if(place(r,c)){ board[r]=c; if(r == n) display(n); else queen(r+1,n); } } } int main(){ int n; printf("Enter # of queens:\n"); scanf("%d",&n); queen(1,n); return 0; } Output: Enter # of queens: 4 Solution : -       Q       -       - -       -       -       Q Q       -       -      ...

SOURCE CODE: #include<stdio.h> int s[20],d,x[20],count=0;//x[n] acts as selected number for present interation void subset(int ks,int k,int total){ int i,wk; x[k]=1; if(ks+s[k]==d){ printf("\nsubset %d \n",++count); for(i=0;i<=k;i++) if(x[i]==1) printf("%d\t",s[i]); } else if(ks+s[k]+s[k+1] <= d) subset(ks+s[k],k+1,total-s[k]); if(ks+total-s[k] >= d && ks+s[k] <= d){ x[k]=0; subset(ks,k+1,total-s[k]); } /* if(count == 0) printf("NO SOLUTION\n");*/ } int main(){ int n,i,sum=0; printf("Enter # of integers :\n"); scanf("%d",&n); printf("Enter elements in ascending order :\n"); for(i=0;i<n;i++){ scanf("%d",&s[i]); sum+=s[i]; } printf("Enter the value of d :\n"); scanf("%d",&d); if(sum < d){ printf("NO SOLUTION\n"); return 0; } else subset(0,0,sum); if(count == 0) ...

SOURCE CODE: #include<stdio.h> int n,p[20],q[20],w[20][20],c[20][20],r[20][20],i,j,min,min1,temp=0,k,b; void obst(){ for(i=0;i<=n;i++) for(j=0;j<=n;j++) if(i==j){ w[i][j]=q[i];c[i][j]=0;r[i][j]=0; printf("W[%d][%d] : %d\tC[%d][%d] : %d\tR[%d][%d] : %d\n",i,j,w[i][j],i,j,c[i][j],i,j,r[i][j]); } for(b=0;b<n;b++){ for(i=0,j=b+1;i<n+1&&j<n+1;i++,j++){ if(i!=j&&i<j){ w[i][j]=p[j]+q[j]+w[i][j-1]; min=9999;//assuming that 9999 is the minimum value for(k=i+1;k<=j;k++){ min1=c[i][k-1]+c[k][j]+w[i][j]; if(min > min1){ min=min1; temp=k; } c[i][j]=min; r[i][j]=temp; } printf("W[%d][%d] : %d\tC[%d][%d] : %d\tR[%d][%d] : %d\n",i,j,w[i][j],i,j,c[i][j],i,j,r[i][j]); } } printf("\n"); } } int main(){ printf("Enter # of elements :"); scanf("%d",&n); for(i=1;i<=n;i++){ printf("E...

SOURCE CODE: #include<stdio.h> int n,i,j,m[20][20],s[20][20],p[20]; void print(int i,int j){ if(i==j) printf("A%d",i); else{ printf("("); print(i,s[i][j]); print(s[i][j]+1,j); printf(")"); } } void mul(){ int q,k; for(i=n;i>0;i--) for(j=i;j<=n;j++){ if(i==j) m[i][j]=0; else{ for(k=1;k<j;k++){ q=m[i][k]+m[k+1][j]+p[i-1]*p[j]*p[k]; if(q < m[i][j]){ m[i][j]=q; s[i][j]=k; } } } } } int chain(int p[],int i,int j){ if(i==j) return 0; int k,count,min=9999;//assuming 9999 is the max value for(k=i;k<j;k++){ count = chain(p,i,k)+chain(p,k+1,j)+p[i-1]*p[j]*p[k]; if(count < min){ min = count; } } return min; } int main(){ int k; printf("Enter # of elements :\n"); scanf("%d",&n); for(i=1;i<=n;i++) for(j=i+1;j<=n;j++){ m[i][i]=0; m[i][j]=9999;//assuming that 9999 is the maximum possible value ...

SOURCE CODE: #include<stdio.h> int j,n,t; int check(int s[],int p) { int ptr=0,i;     for(i=0;i<n;i++) {if(s[i]==p)     ptr++;     }                      if(ptr==0)             return 1;             else             return 0;         } int main() { printf("Enter # of jobs :\n"); scanf("%d",&n); int slot[n],p[n],d[n],i; printf("Enter profits & deadlines : \n"); for(i=0;i<n;i++){ slot[i]=0; scanf("%d%d",&p[i],&d[i]); } for(i=0;i<n;i++) for(j=i+1;j<n;j++) if(p[i]<p[j]) { t=p[i];p[i]=p[j];p[j]=t; t=d[i];d[i]=d[j];d[j]=t; } for(i=0;i<n;i++) for(j=d[i];j>0;j--){ if(check(slot,j)==1){ slot[i]=j; break; } } printf("\nPROFIT DEADLINE SLOT\n"); for(i=0;i<n;i++){ if(slot[i]>0)...

SOURCE CODE: #include<stdio.h> int cost[20][20],visited[20],d[20],n; void dijikstra(int source){ int i,j,min,u,v; for(i=1;i<=n;i++){ visited[i]=0; d[i]=cost[source][i]; } visited[source]=0;d[source]=0; for(j=2;j<=n;j++){ min=9999;//assuming is the max value for(i=1;i<=n;i++){ if(!visited[i]) if(d[j]<min){ min=d[i]; u=i; } } visited[u]=1; for(v=1;v<=n;v++){ if(cost[u][v]!=9999 && visited[v]==0){ if(d[v]>cost[u][v]+d[u]) d[v]=cost[u][v]+d[u]; } } } } int main(){ int i,j,source; printf("Enter # of vertices : \n"); scanf("%d",&n); printf("Enter source vertex: \n"); scanf("%d",&source);//generally 1 printf("Enter the adjacency matrix :\n"); for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ scanf("%d",&cost[i][j]); if(cost[i][j]==0) cost[i][j]=9999; } } dijikstra(source); prin...

SOURCE CODE: #include<stdio.h> int visited[20]={0},arr[20][20]; int i,j,n,near=0,min,mincost=0,i_store,j_store; int prims(){ while(near < n){ near++; for(i=0,min=9999;i<n;i++) for(j=0;j<n;j++) if(arr[i][j] < min) if(visited[i]!=0){ min=arr[i][j]; i_store=i; j_store=j; } if(visited[i_store]==0 || visited[j_store]==0){ printf("Edge %d : %d--->%d cost is %d\n",near,i_store+1,j_store+1,min); mincost+=min; visited[j_store]=1; } arr[i_store][j_store]=9999; arr[j_store][i_store]=9999; } return mincost; } int main(){ printf("Enter # of vertices :\n"); scanf("%d",&n); printf("Enter the adjacency matrix :\n"); for(i=0;i<n;i++) for(j=0;j<n;j++) { scanf("%d",&arr[i][j]); if(arr[i][j]==0) arr[i][j]=9999;//assuming max value } visited[0]=1; printf("Mininum cost = %d\n",prims()); return 0; } OUTPUT :...

SOURCE CODE: #include<stdio.h> typedef struct{ int u,v,cost; }edge; edge E[20],e; int n,near,parent[20],t[20][3]; void adjust(int i){ int j=2*i; edge temp=E[i]; while(j<=near){ if((j<near) && (E[j].cost > E[j+1].cost)) j++; if(temp.cost < E[j].cost) break; E[j/2]=E[j]; j*=2; } E[j/2]=temp; } void Union(int i, int j){ parent[i]=j; } int find(int i){ while(parent[i]>=0) i=parent[i]; return i; } void heapify(){ for(int i=near/2;i>=1;i--) adjust(i); } edge deletemin() { edge temp=E[1]; E[1]=E[near]; near--; adjust(1); return temp; } int main(){ int i,j,mincost,k; printf("Enter # os vertices and edges :\n"); scanf("%d%d",&n,&near); printf("Enter edge details:\nFIRST_EDGE LAST_EDGE COST\n"); for(i=1;i<=near;i++){ scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].cost); parent[i]=-1;} heapify(); i=0;mincost=0; while((i<(n-1)...