Daa Pracs5-12.docx

Design & Analysis of Algorithm Lab Manual

PRACTICAL : 5 Aim: Implementation of a knapsack problem using dynamic programming. Answer: #include<stdio.h> #define MAX 100 int main() { int n,flag[MAX]={0},v[MAX],w[MAX],m[MAX][MAX],W,i,j,k; printf("Enter the number of elements: "); scanf("%d",&n); printf("\nEnter the values:"); for(i=1;i<=n;i++) scanf("%d",&v[i]); printf("\nEnter the weights: "); for(i=1;i<=n;i++) scanf("%d",&w[i]); printf("Enter the capacity of knapsack: "); scanf("%d",&W); for(j=0;j<=W;j++) m[0][j]=0; for(i=1;i<=n;i++) { for(j=0;j<=W;j++) { if(w[i]<=j) { if( m[i-1][j] > (m[i-1][j-w[i]]+v[i]) ) m[i][j]=m[i-1][j]; else m[i][j]=m[i-1][j-w[i]]+v[i]; } else m[i][j]=m[i-1][j]; } } i=n;k=W; while(i>0 && k>0) { if(m[i][k]!=m[i-1][k]) { flag[i]=1; Government Engineering College, Gandhinagar

22

Design & Analysis of Algorithm Lab Manual

k=k-w[i]; i=i-1; } else i--; } printf("\n\t"); for(i=0;i<=W;i++) printf("%d\t",i); printf("\n"); for(i=0;i<=10*W;i++) printf("-"); printf("\n"); for(i=0;i<=n;i++) { printf("%d |\t", i); for(j=0;j<=W;j++) printf("%d\t",m[i][j]); printf("\n"); } printf("\nThe resultant vector is "); printf("( "); for(i=1;i<=n;i++) printf("%d ",flag[i]); printf(")\n\nThe total profit is %d",m[n][W]); return 0; }

OUTPUT:

Sign:- ____________ Government Engineering College, Gandhinagar

23

Design & Analysis of Algorithm Lab Manual

PRACTICAL : 6 Aim: Implementation of Chain Matrix Multiplication using Dynamic Programming Answer: #include<stdio.h> #include #define INFY 999999999 long int m[20][20]; int s[20][20]; int p[20],i,j,n; void print_optimal(int i,int j) { if (i == j) printf(" A%d ",i); else { printf(" [ "); print_optimal(i, s[i][j]); print_optimal(s[i][j] + 1, j); printf(" ] "); } } void matmultiply(void) { long int q; int k; for(i=n;i>0;i--) { for(j=i;j<=n;j++) { if(i==j) m[i][j]=0; else { for(k=i;k<j;k++) { q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]; Government Engineering College, Gandhinagar

24

Design & Analysis of Algorithm Lab Manual

if(q<m[i][j]) { m[i][j]=q; s[i][j]=k; } } } } } } void main() { int k; printf("Enter the no. of Matrices: "); scanf("%d",&n); for(i=1;i<=n;i++) for(j=i+1;j<=n;j++) { m[i][i]=0; m[i][j]=INFY; s[i][j]=0; } printf("\nEnter the dimensions: \n"); for(k=0;k<=n;k++) { printf("P%d: ",k); scanf("%d",&p[k]); } matmultiply(); printf("\nCost Matrix M:\n"); for(i=1;i<=n;i++) for(j=i;j<=n;j++) printf("m[%d][%d]: %ld\n",i,j,m[i][j]); i=1,j=n; printf("\nMULTIPLICATION SEQUENCE : "); print_optimal(i,j); getch(); } Government Engineering College, Gandhinagar

25

Design & Analysis of Algorithm Lab Manual

Output:

Sign:- ____________ Government Engineering College, Gandhinagar

26

Design & Analysis of Algorithm Lab Manual

PRACTICAL : 7 Aim: Implementation of making a Change Problem using dynamic programming Answer: #include #include #include using namespace std; int changeMaking(int coin[], int n, int sum) { int i,j; int x,y; int dp[n+1][sum+1]; for(j=0;j<=sum;j++) dp[0][j]=INT_MAX; for(i=1;i<=n;i++) dp[i][0]=0; for(i=1;i<=n;i++) { for(j=1;j<=sum;j++) { if(j>=coin[i-1]) { x=dp[i-1][j]; y=1+dp[i][j-coin[i-1]]; dp[i][j]=min(x,y); } else dp[i][j]=dp[i-1][j]; } } return dp[n][sum]; } int main() { int i; int n,sum; cout<<"Enter the amount whose change is required"<<endl; cin>>sum; Government Engineering College, Gandhinagar

27

Design & Analysis of Algorithm Lab Manual

cout<<"Enter the number of coins available"<<endl; cin>>n; int coin[n]; cout<<"Enter the values of coins"<<endl; for(i=0;i>coin[i]; cout<<"The least number of coins whose sum is equal to required sum is"<<endl; cout<
Output:

Sign:- ____________ Government Engineering College, Gandhinagar

28

Design & Analysis of Algorithm Lab Manual

PRACTICAL : 8 Aim: Implementation of a Knapsack problem using Greedy algorithm. Answer: #include<stdio.h> #include void knapsack(float capacity, int n, float weight[], float profit[]) { float x[20], totalprofit,y; int i,j; y=capacity; totalprofit=0; for(i=0;i < n;i++) x[i]=0.0; for(i=0;i < n;i++) { if(weight[i] > y) break; else { x[i]=1.0; totalprofit=totalprofit+profit[i]; y=y-weight[i]; } } if(i < n) x[i]=y/weight[i]; totalprofit=totalprofit+(x[i]*profit[i]); printf("\nThe selected elements are:-"); for(i=0;i < n;i++) if(x[i]==1.0) printf("\nProfit is %.3f with weight %.3f ", profit[i], weight[i]); else if(x[i] > 0.0) printf("\n%.3f part of Profit %.3f with weight %.3f", x[i], profit[i], weight[i]); printf("\nTotal profit for %d objects = %.3f\n\n", n, totalprofit); }

Government Engineering College, Gandhinagar

29

Design & Analysis of Algorithm Lab Manual

int main() { float weight[20],profit[20],ratio[20], t1,t2,t3; int n; time_t start,stop; float capacity; int i,j; printf("Enter number of objects: "); scanf("%d", &n); printf("Enter the capacity of knapsack: "); scanf("%f", &capacity); for(i=0;i < n;i++) { printf("\nEnter %d profit: ", (i+1)); scanf("%f", &profit[i]); printf("Enter %d weight: ", (i+1)); scanf("%f", &weight[i]); ratio[i]=profit[i]/weight[i]; } for(i=0;i < n;i++) for(j=0;j < n;j++) { if(ratio[i] > ratio[j]) { t1=ratio[i]; ratio[i]=ratio[j]; ratio[j]=t1; t2=weight[i]; weight[i]=weight[j]; weight[j]=t2; t3=profit[i]; profit[i]=profit[j]; profit[j]=t3; } } knapsack(capacity,n,weight,profit); getch(); return 0; }

Government Engineering College, Gandhinagar

30

Design & Analysis of Algorithm Lab Manual

Output:

Sign:- ____________ Government Engineering College, Gandhinagar

31

Design & Analysis of Algorithm Lab Manual

PRACTICAL : 9 Aim: Implementation of Graph and searching (DFS and BFS). Answer: #include #include<list> using namespace std; class Graph { int V; list *adj; void DFSUtil(int v, bool visited[]); public: Graph(int V); void addEdge(int v, int w); void DFS(int v); void BFS(int v); }; Graph::Graph(int V) { this->V = V; adj = new list[V]; } void Graph::addEdge(int v, int w) { adj[v].push_back(w); } void Graph::DFSUtil(int v, bool visited[]) { visited[v] = true; cout << v << " "; list::iterator i; for (i = adj[v].begin(); i != adj[v].end(); ++i) if (!visited[*i]) DFSUtil(*i, visited); } void Graph::DFS(int v) { bool *visited = new bool[V]; for (int i = 0; i < V; i++) Government Engineering College, Gandhinagar

32

Design & Analysis of Algorithm Lab Manual

visited[i] = false; DFSUtil(v, visited); } void Graph::BFS(int s) { bool *visited = new bool[V]; for(int i = 0; i < V; i++) visited[i] = false; list queue; visited[s] = true; queue.push_back(s); list::iterator i; while(!queue.empty()) { s = queue.front(); cout << s << " "; queue.pop_front(); for(i = adj[s].begin(); i != adj[s].end(); ++i) { if(!visited[*i]) { visited[*i] = true; queue.push_back(*i); } } } } int main() { Graph g(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 3); //g.addEdge(2, 0); g.addEdge(2, 3); //g.addEdge(3, 3); cout << "Following is Depth First Traversal "; g.DFS(0); cout <<endl<<endl<< "Following is Breadth First Traversal "; g.BFS(0); return 0; }

Government Engineering College, Gandhinagar

33

Design & Analysis of Algorithm Lab Manual

Output:

Sign:- ____________ Government Engineering College, Gandhinagar

34

Design & Analysis of Algorithm Lab Manual

PRACTICAL : 10 Aim: Implement prim’s algorithm. Answer: #include<stdio.h> #include int a,b,u,v,n,i,j,ne=1; int visited[10]={0},min,mincost=0,cost[10][10]; int main() { printf("\nEnter the number of nodes:"); scanf("%d",&n); printf("\nEnter 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]=999; } visited[1]=1; printf("\n"); while(ne < n) { for(i=1,min=999;i<=n;i++) for(j=1;j<=n;j++) if(cost[i][j]< min) if(visited[i]!=0) { min=cost[i][j]; a=u=i; b=v=j; } if(visited[u]==0 || visited[v]==0) { printf("\n Edge %d:(%d %d) cost:%d",ne++,a,b,min); mincost+=min; visited[b]=1; } cost[a][b]=cost[b][a]=999; } printf("\n Minimun cost=%d",mincost); Government Engineering College, Gandhinagar

35

Design & Analysis of Algorithm Lab Manual

return 0; }

Output:

Sign:- ______________ Government Engineering College, Gandhinagar

36

Design & Analysis of Algorithm Lab Manual

PRACTICAL : 11 Aim: Implement Kruskal’s algorithm. Answer: #include<stdio.h> #include #include<stdlib.h> int i,j,k,a,b,u,v,n,ne=1; int min,mincost=0,cost[9][9],parent[9]; int find(int); int uni(int,int); int main() { i=5;j=5;n=5; printf("\n\tImplementation of Kruskal's algorithm\n"); printf("\nEnter the no. of vertices:"); scanf("%d",&n); printf("\nEnter the cost 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]=999; } } printf("The edges of Minimum Cost Spanning Tree are\n"); while(ne < n) { for(i=1,min=999;i<=n;i++) { for(j=1;j <= n;j++) { if(cost[i][j] < min) { min=cost[i][j]; a=u=i; b=v=j; } } } u=find(u); Government Engineering College, Gandhinagar

37

Design & Analysis of Algorithm Lab Manual

v=find(v); if(uni(u,v)) { printf("%d edge (%d,%d) =%d\n",ne++,a,b,min); mincost +=min; } cost[a][b]=cost[b][a]=999; } printf("\n\tMinimum cost = %d\n",mincost); return 0; } int find(int i) { while(parent[i]) i=parent[i]; return i; } int uni(int i,int j) { if(i!=j) { parent[j]=i; return 1; } return 0; }

Government Engineering College, Gandhinagar

38

Design & Analysis of Algorithm Lab Manual

Output:

Sign:- ______________ Government Engineering College, Gandhinagar

39

Design & Analysis of Algorithm Lab Manual

PRACTICAL : 12 Aim: Implement a LCS problem. Answer: #include<stdio.h> #include<string.h> int i,j,m,n,c[20][20]; char x[20],y[20],b[20][20]; void print(int i,int j) { if(i==0 || j==0) return; if(b[i][j]=='c') { print(i-1,j-1); printf("%c",x[i-1]); } else if(b[i][j]=='u') print(i-1,j); else print(i,j-1); } void lcs() { m=strlen(x); n=strlen(y); for(i=0;i<=m;i++) c[i][0]=0; for(i=0;i<=n;i++) c[0][i]=0; for(i=1;i<=m;i++) for(j=1;j<=n;j++) { if(x[i-1]==y[j-1]) { c[i][j]=c[i-1][j-1]+1; b[i][j]='c'; } else if(c[i-1][j]>=c[i][j-1]) Government Engineering College, Gandhinagar

40

Design & Analysis of Algorithm Lab Manual

{ c[i][j]=c[i-1][j]; b[i][j]='u'; } else { c[i][j]=c[i][j-1]; b[i][j]='l'; } } } int main() { printf("Enter 1st sequence:"); scanf("%s",x); printf("Enter 2nd sequence:"); scanf("%s",y); printf("\nThe Longest Common Subsequence is "); lcs(); print(m,n); return 0; }

Output:

Sign:- ______________ Government Engineering College, Gandhinagar

41