DAA Record

1. Aim: To implement Knapsack problem to find max. profit (Using Greedy Method
approach)
Source Code:
#include<stdio.h>
int main(){
int n, m, i, j, t;
int p[100],w[100];
printf("Enter size: ");
scanf("%d",&n);
printf("Enter maximum capacity: ");
scanf("%d",&m);
printf("Enter the profits: ");
for(i=0;i<n;i++)
scanf("%d",&p[i]);
printf("Enter the weights: ");
for(i=0;i<n;i++)
scanf("%d",&w[i]);
for(i=0;i<n;i++) {
for(j=0;j<n-i-1;j++) {
float t1 = (float) p[j]/w[j];
float t2 = (float) p[j+1]/w[j+1];
if(t1<t2) {
t=w[j];
w[j]=w[j+1];
w[j+1]=t;
t=p[j];
p[j]=p[j+1];
p[j+1]=t;
}
}
}
float result[100];
for(i=0;i<n;i++)
result[i]=0;
float profit = 0;
for (i = 0; i < n; i++) {
if (w[i] > m)
break;
result[i] = 1;
m = m - w[i];
profit += p[i];
}
if (i <= n) {
result[i] = (float) m / w[i];
profit += p[i] * result[i];
}
printf("\nTotal profit = %.2f",profit);
}
Output 1:
Enter size: 3
Enter capacity: 20
Enter profits: 25 24 15
Enter weights: 18 15 10
Total profit: 31.50
Output 2:
Enter size: 7
Enter capacity: 15
Enter profits: 10 5 15 7 6 18 3
Enter weights: 2 3 5 7 1 4 1
Total profit: 55.33

2. Aim: To implement Job Sequencing with deadlines problem.

Source Code:
#include <stdio.h>
int maxi(int a[],int n){
int i,m=a[0];
for(i=0;i<n;i++)
if(a[i]>m)
m=a[i];
return m;
}
int main(){
int i,j,n;
printf("Enter the value of n: ");
scanf("%d",&n);
int profits[n],dead[n];
printf("Enter the profits: ");
for(i=0;i<n;i++)
scanf("%d",&profits[i]);
printf("Enter the dead lines: ");
for(i=0;i<n;i++)
scanf("%d",&dead[i]);
for(i=0;i<n;i++){
for(j=i+1;j<n;j++){
if(profits[i]<profits[j]){
int temp=profits[i];
profits[i]=profits[j];
profits[j]=temp;
temp=dead[i];
dead[i]=dead[j];
dead[j]=temp;
}
}
}
int max=maxi(dead,n);
int profit=0,w;
int visited[max];
for(i=0;i<max;i++)
visited[i]=0;
 for(i=0;i<n;i++){
w=dead[i];
for(j=w-1;j>=0;j--){
if(visited[j]==0){
visited[j]=1;
profit+=profits[i];
break;
}
}
}
printf("Total Profit = %d",profit);
return 0;
}
Output 1:
Enter the value of n: 7
Enter the profits: 3 5 20 18 1 6 30
Enter the dead lines: 1 3 4 3 2 1 2
Total Profit = 74
Output 2:
Enter the value of n: 5
Enter the profits: 20 15 10 5 1
Enter the dead lines: 2 2 1 3 3
Total Profit = 40

3. Aim: To implement Prim’s Algorithm to find MCST.

Source Code:
#include<stdio.h>
#define INF 9999999
int main() {
int no_edge,V,cost=0,i,j;
int selected[V];
printf("Enter number of edges: ");
scanf("%d",&V);
int G[V][V];
printf("Enter the adjacency matrix:\n");
for(i=0;i<V;i++)
for(j=0;j<V;j++)
scanf("%d",&G[i][j]);
for(i=0;i<V;i++)
selected[i]=0;
no_edge = 0;
selected[0] = 1;
int x;
int y;
printf("Edge: Weight\n");
while (no_edge < V - 1) {
int min = INF;
x = 0;
y = 0;
for (int i = 0; i < V; i++) {
if (selected[i]) {
 for (int j = 0; j < V; j++) {
if (!selected[j] && G[i][j]){
if (min > G[i][j]) {
min = G[i][j];
x = i;
y = j;
}
}
}
}
}
printf("%d - %d: %d\n", x, y, G[x][y]);
cost+=G[x][y];
selected[y] = 1;
no_edge++;
}
printf("Minimum Cost = %d",cost);
return 0;
}
Output 1:
Enter number of edges: 5
Enter the adjacency matrix:
0 0 3 0 0
0 0 10 4 0
3 10 0 2 6
0 4 2 0 1
0 0 6 1 0
Edge: Weight
0-2: 3
2-3: 2
3-4: 1
3-1: 4
Minimum Cost = 10
Output 2:
Enter number of edges: 4
Enter the adjacency matrix:
0 5 0 6
5 0 10 0
0 10 0 2
6 0 2 0
Edge: Weight
0-1: 5
0-3: 6
3-2: 2
Minimum Cost = 13
4. Aim: To implement Kruskal’s Algorithm to find MCST.
Source Code:
#include<stdio.h>
int i,j,k,a,b,u,v,n,ne=1;
int min,mincost=0,cost[9][9],parent[9];
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;
}
int main(){
printf("\nEnter the no. of vertices: ");
scanf("%d",&n);
printf("\nEnter the cost adjacency matrix:\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++){
scanf("%d",&cost[i][j]);
if(cost[i][j]==0)
cost[i][j]=999;
}
printf("Edge: Cost\n");
while(ne<n){
for(i=0,min=999;i<n;i++){
for(j=0;j<n;j++){
if(cost[i][j]<min){
min=cost[i][j];
a=u=i;
b=v=j;
}
}
}
u=find(u);
v=find(v);
if(uni(u,v)){
printf("%d - %d : %d\n", a, b, min);
mincost +=min;
}
ne++;
cost[a][b]=cost[b][a]=999;
}
printf("Minimum cost = %d",mincost);
return 0;
}
Output 1:
Enter number of edges: 4
Enter the adjacency matrix:
0 5 0 6
5 0 10 0
0 10 0 2
6 0 2 0
Edge: Weight
2-3: 2
0-1: 5
0-3: 6
Minimum Cost = 13
Output 2:
Enter number of edges: 5
Enter the adjacency matrix:
0 0 3 0 0
0 0 10 4 0
3 10 0 2 6
0 4 2 0 1
0 0 6 1 0
Edge: Weight
3-4: 1
2-3: 2
0-2: 3
1-3: 4
Minimum Cost = 10

5. Aim: To implement Mini-Max Problem using Divide & Conquer Strategy.

Source Code:
#include<stdio.h>
int max,min,a[100];
void min_max(int low, int high){
int i,max1,min1;
if(low==high)
min=max=a[low];
else if(low==high-1){
if(a[low]<a[high]){
min=a[low];
max=a[high];
}
else{
max=a[low];
min=a[high];
}
}
else{
int mid=(high+low)/2;
min_max(low,mid);
max1=max;
min1=min;
min_max(mid+1,high);
 if(max<max1)
max=max1;
if(min>min1)
min=min1;
}
}
int main() {
int i,n;
printf("\nEnter the size of array: ");
scanf("%d",&n);
printf("\nEnter the array: ");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
max=min=a[0];
min_max(0,n-1);
printf("\nMaximum element in the array = %d",max);
printf("\nMinimum element in the array = %d",min);
return 0;
}
Output 1:
Enter the size of array: 3
Enter the array: 9 1 8
Maximum element in the array = 9
Minimum element in the array = 1
Output 2:
Enter the size of array: 1
Enter the array: 7
Maximum element in the array = 7
Minimum element in the array = 7

6. Aim: To implement Strassen’s Matrix Multiplication using Divide & Conquer

Strategy.
Source Code:
#include <stdio.h>
#include <string.h>
void strassen(int n, int A[][n], int B[][n], int C[][n]) {
if (n == 1) {
C[0][0] = A[0][0] * B[0][0];
return;
}
int i, j, half = n / 2;
int A11[half][half], A12[half][half], A21[half][half], A22[half][half];
int B11[half][half], B12[half][half], B21[half][half], B22[half][half];
int C11[half][half], C12[half][half], C21[half][half], C22[half][half];
int P1[half][half], P2[half][half], P3[half][half], P4[half][half], P5[half][half], P6[half][half],
P7[half][half];
for (i = 0; i < half; i++)
for (j = 0; j < half; j++) {
A11[i][j] = A[i][j];
A12[i][j] = A[i][j + half];
A21[i][j] = A[i + half][j];
 A22[i][j] = A[i + half][j + half];
B11[i][j] = B[i][j];
B12[i][j] = B[i][j + half];
B21[i][j] = B[i + half][j];
B22[i][j] = B[i + half][j + half];
}
strassen(half, A11, B11, P1);
strassen(half, A12, B21, P2);
strassen(half, A11, B12, P3);
strassen(half, A12, B22, P4);
strassen(half, A21, B11, P5);
strassen(half, A22, B21, P6);
strassen(half, A21, B12, P7);
strassen(half, A22, B22, C22);
for (i = 0; i < half; i++)
for (j = 0; j < half; j++) {
C11[i][j] = P1[i][j] + P2[i][j];
C12[i][j] = P3[i][j] + P4[i][j];
C21[i][j] = P5[i][j] + P6[i][j];
C22[i][j] = P7[i][j] + C22[i][j];
}
for (i = 0; i < half; i++)
for (j = 0; j < half; j++) {
C[i][j] = C11[i][j];
C[i][j + half] = C12[i][j];
C[i + half][j] = C21[i][j];
C[i + half][j + half] = C22[i][j];
}
}
int main() {
int N,i,j;
printf("***Note that n value must be power of 2***\n");
printf("Enter the value of n: ");
scanf("%d",&N);
int A[N][N],B[N][N],C[N][N];
memset(C, 0, N*N*sizeof(int));
printf("Enter first matrix:\n");
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
scanf("%d",&A[i][j]);
printf("Enter second matrix:\n");
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
scanf("%d",&B[i][j]);
strassen(N, A, B, C);
printf("Result Matrix:\n");
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++)
printf("%d ", C[i][j]);
printf("\n");
}
 return 0;
}
Output 1:
***Note that n value must be power of 2***
Enter the value of n: 4
Enter first matrix:
1111
2222
3333
2222
Enter second matrix:
1111
2222
3333
2222
Result Matrix:
8888
16 16 16 16
24 24 24 24
16 16 16 16
Output 2:
***Note that n value must be power of 2***
Enter the value of n: 4
Enter first matrix:
2310
7410
9 -2 1 0
0000
Enter second matrix:
9 -2 -1 0
5730
8100
0000
Result Matrix:
41 18 7 0
91 15 5 0
79 -31 -15 0
0000

7. Aim: To implement Single Source Shortest Path – Dijkstra’s Algorithm (Using

Greedy Method Approach)
Source Code:
#include<stdio.h>
#include<string.h>
#define INF 9999999
int minCost(int cost[],int visited[],int v){
int min=INF;
int mi=0;
for(int i=0;i<v;i++){
if(cost[i]<min && !visited[i]){
min=cost[i];
 mi=i;
}
}
return mi;
}
int main() {
int no_edge,V,i,j;
printf("Enter number of edges: ");
scanf("%d",&V);
int visited[V];
memset(visited,0,V*sizeof(int));
int G[V][V];
int cost[V];
memset(cost,INF,V*sizeof(int));
printf("Enter the adjacency matrix:\n");
for(i=0;i<V;i++)
for(j=0;j<V;j++)
scanf("%d",&G[i][j]);
no_edge = 0;
cost[0] = 0;
while (no_edge < V - 1){
int u=minCost(cost,visited,V);
visited[u]=1;
for (i = 0; i < V; i++)
if (G[u][i] && cost[u]+G[u][i]<cost[i] && !visited[i])
cost[i]=cost[u]+G[u][i];
no_edge++;
}
printf("Vertex Cost\n");
for(i=0;i<V;i++)
printf("%d %d\n",i+1,cost[i]);
return 0;
}
Output 1:
Enter number of edges: 4
Enter the adjacency matrix:
0506
5 0 10 0
0 10 0 2
6020
Vertex Cost
1 0
2 5
3 8
4 6
Output 2:
Enter number of edges: 5
Enter the adjacency matrix:
00300
0 0 10 4 0
3 10 0 2 6
04201
00610

Vertex Cost
1 0
2 9
3 3
4 5
5 6

8. Aim: To implement All Source Shortest Path – Flyod Warshall’s Algorithm.

Source Code:
#include <stdio.h>
#include<limits.h>
#define INF 999999999
int V;
void floydWarshall(int dist[][V]){
int i, j, k;
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];
}
}
}
printf("The following matrix shows the shortest distances"
" between every pair of vertices \n");
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][j] == INF)
printf("%7s", "INF");
else
printf("%7d", dist[i][j]);
}
printf("\n");
}
}
int main(){
int i,j;
printf("Enter number of vertices: ");
scanf("%d",&V);
printf("Enter the cost matrix:\n");
int graph[V][V];
for(i=0;i<V;i++)
for(j=0;j<V;j++){
scanf("%d",&graph[i][j]);
if(graph[i][j]==0 && i!=j)
graph[i][j]=INF;
}
 floydWarshall(graph);
return 0;
}

Output 1:
Enter number of vertices: 4
Enter the cost matrix:
0506
5 0 10 0
0 10 0 2
6020
The following matrix shows the shortest distances between every pair of vertices
0 5 8 6
5 0 10 11
8 10 0 2
6 11 2 0
Output 2:
Enter number of vertices: 5
Enter the cost matrix:
00300
0 0 10 4 0
3 10 0 2 6
04201
00610
The following matrix shows the shortest distances between every pair of vertices
0 9 3 5 6
9 0 6 4 5
3 6 0 2 3
5 4 2 0 1
6 5 3 1 0

9. Aim: To implement String Editing Problem using Dynamic Method approach

Source Code:
#include <stdio.h>
#include <string.h>
int ic,dc,cc;
int min(int a, int b, int c){
return (a<b && a<c)?a:((b<c)?b:c);
}
int C(char x1, char x2){
if(x1==x2)
return 0;
return cc;
}
void StringEdit(char* s1, char* s2){
int n1=strlen(s1);
int n2=strlen(s2);
int res[n1+1][n2+1];
memset(res, -1, (n2+1)*(n1+1)*sizeof(res[0][0]));
int i=1,j=1;
res[0][0]=0;
 while(i<=n2){
res[0][i]=res[0][i-1]+1;
i++;
}
while(j<=n1+1){
res[j][0]=res[j-1][0]+1;
j++;
}
for(i=1;i<=n1;i++){
for(j=1;j<=n2;j++){
res[i][j]=min(res[i-1][j]+dc,res[i-1][j-1]+C(s1[i-1],s2[j-1]),res[i][j-1]+ic);
}
}
printf("\nThe Cost Matrix is:\n");
for(i=0;i<=n1;i++){
for(j=0;j<=n2;j++){
printf("%d\t",res[i][j]);
}
printf("\n");
}
printf("The Total Cost is: %d",res[n1][n2]);
}
int main() {
char s1[100], s2[100];
printf("Enter First String: ");
scanf("%s",s1);
printf("Enter Second String: ");
scanf("%s",s2);
printf("Enter Insertion, Deletion and Change Cost: ");
scanf("%d %d %d",&ic,&dc,&cc);
StringEdit(s1,s2);
return 0;
}
Output 1:
Enter First String: aabab
Enter Second String: babb
Enter Insertion, Deletion and Change Cost: 1 1 2

The Cost Matrix is:

0 1 2 3 4
1 2 1 2 3
2 3 2 3 4
3 2 3 2 3
4 3 2 3 4
5 4 3 2 3
The Total Cost is: 3
Output 2:
Enter First String: aabaababaa
Enter Second String: babaabab
Enter Insertion, Deletion and Change Cost: 1 1 2
The Cost Matrix is:
0 1 2 3 4 5 6 7 8
1 2 1 2 3 4 5 6 7
2 3 2 3 2 3 4 5 6
3 2 3 2 3 4 3 4 5
4 3 2 3 2 3 4 3 4
5 4 3 4 3 2 3 4 5
6 5 4 3 4 3 2 3 4
7 6 5 4 3 4 3 2 3
8 7 6 5 4 5 4 3 2
9 8 7 6 5 4 5 4 3
10 9 8 7 6 5 6 5 4
The Total Cost is: 4

10. Aim: To implement Knapsack problem to find max. profit (Using Dynamic
Programming approach)
Source Code:
#include <stdio.h>
#include<string.h>
int findMax(int a,int b){
return (a>b)?a:b;
}
void knapsack(int profit[],int W,int n,int weight[]){
int c[n+1][W+1];
memset(c,0,n*n*sizeof(int));
int i,w,j;
for(i=1;i<=n;i++){
for(j=0;j<=W;j++){
if(weight[i-1]>j){
c[i][j]=c[i-1][j];
}
else{
c[i][j]=findMax(profit[i-1]+c[i-1][j- weight[i-1]],c[i-1][j]);
}

}
}
for(i=0;i<=n;i++){
for(j=0;j<=W;j++){
printf("%d ",c[i][j]);
}
printf("\n");
}
int arr[n];
memset(arr,0,n*sizeof(int));
i=n;
j=W;
while(i>0 && j>0){
if(c[i][j]!=c[i-1][j]){
arr[i]=1;
j=j-weight[i-1];
 i--;
}
else{
i--;
}
}
printf("Included Weights & their respective Profits are: ");
for(i=n;i>0;i--){
if(arr[i]==1)
printf("(%d, %d) ",weight[i-1],profit[i-1]);
}
printf("\nMaximum Profit Obtained: %d\n",c[n][W]);
}

int main()
{
int n,m,i;
printf("Enter the size of n: ");
scanf("%d",&n);
int profits[n],weights[n];
printf("Enter the size of knapsack: ");
scanf("%d",&m);
printf("Enter the profits: ");
for(i=0;i<n;i++)
scanf("%d",&profits[i]);
printf("Enter the weights: ");
for(i=0;i<n;i++)
scanf("%d",&weights[i]);
knapsack(profits,m,n,weights);
return 0;
}
Output 1:
Enter the size of n: 3
Enter the size of knapsack: 6
Enter the profits: 10 15 40
Enter the weights: 1 2 3
0000000
0 10 10 10 10 10 10
0 10 15 25 25 25 25
0 10 15 40 50 55 65
Included Weights & their respective Profits are: (3, 40), (2, 15), (1, 10)
Maximum Profit Obtained: 65
Output 2:
Enter the size of n: 4
Enter the size of knapsack: 8
Enter the profits: 2 3 1 4
Enter the weights: 3 4 6 5
000000000
000222222
000233355
000233355
000234456
Included Weights & their respective Profits are: (5, 4) (3, 2)
Maximum Profit Obtained: 6

11. Aim: To implement Single Source Shortest Path – General Weights – Bellman Ford
Algorithm (Using Dynamic Programming approach)
Source Code:
#include<stdio.h>
#define INF 9999999
void GeneralWeights(int V,int G[][3],int E){
int dist[V],i,j;
for(int i=0;i<V;i++)
dist[i]=INF;
dist[0]=0;
for(i=0;i<V-1;i++){
for(j=0;j<E;j++){
if(dist[G[j][0]]!=INF && dist[G[j][0]]+G[j][2]<dist[G[j][1]])
dist[G[j][1]]=dist[G[j][0]]+G[j][2];
}
}
for(i=0;i<E;i++){
int x=G[i][0],y=G[i][1],weight=G[i][2];
if(dist[x]!=INF && dist[x]+weight<dist[y])
printf("\nGraph Contains Negative Cyceles.");
}
printf("Vertex Distance\n");
for(i=0;i<V;i++)
printf("%d %d\n",i,dist[i]);
}
int main() {
int V,E,i,j;
printf("Enter number of vertices: ");
scanf("%d",&V);
printf("Enter number of edges: ");
scanf("%d",&E);
int G[E][3];
printf("Enter the adjacency matrix in the form(Vertex 1 - Vertex 2 - Cost of V(1,2):\n");
for(i=0;i<E;i++)
for(j=0;j<3;j++)
scanf("%d",&G[i][j]);
GeneralWeights(V,G,E);
}
Output 1:
Enter number of vertices: 5
Enter number of edges: 8
Enter the adjacency matrix in the form(Vertex 1 - Vertex 2 - Cost of V(1,2):
0 1 -1
0 2 4
1 2 3
1 3 2
1 4 2
3 2 5
3 1 1
4 3 -3
Vertex Distance
0 0
1 -1
2 2
3 -2
4 1
Output 2:
Enter number of vertices: 4
Enter number of edges: 5
Enter the adjacency matrix in the form(Vertex 1 - Vetrex 2 - Cost of V(1,2):
0 1 5
0 2 4
1 3 3
2 1 6
3 2 2
Vertex Distance
0 0
1 5
2 4
3 8

12. To implement Travelling Sales Person Problem using Dynamic Programming

approach.
Source Code:
#include <stdio.h>
#include <limits.h>
#define MAX 10
int tsp(int n, int dist[MAX][MAX], int visited, int current){
if (visited == (1 << n) - 1)
return dist[current][0];
int min_cost = INT_MAX;
for (int i = 0; i < n; i++)
{
if ((visited & (1 << i)) == 0)
{
int cost = dist[current][i] + tsp(n, dist, visited | (1 << i), i);
min_cost = (cost < min_cost) ? cost : min_cost;
}
}
return min_cost;
}
int main(){
int n;
int dist[MAX][MAX];
printf("Enter number of nodes: ");
scanf("%d",&n);
printf("Enter the adjacency matrix:\n");
for(int i=0;i<n;i++)
 for(int j=0;j<n;j++)
scanf("%d",&dist[i][j]);
int visited = 1;
int start_city = 0;
int min_cost = tsp(n, dist, visited, start_city);
printf("Minimum cost: %d\n", min_cost);
return 0;
}
Output 1:
Enter number of nodes: 4
Enter the adjacency matrix:
0 10 15 20
5 0 9 10
6 13 0 12
8890
Minimum cost: 35
Output 2:
Enter number of nodes: 4
Enter the adjacency matrix:
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0
Minimum cost: 80