DAA

LAB PROGRAMS
write a program to sort a lsit of N elements using selection sort technique
01
02 write a program to perform travelling salesman problem

03 write program to implement dynamic programming algorithm for the 0/1

knapsack problem

04 write a program to implement the dfs and bfs algorithm for a graph

write a program to find the minimum and maximum value in an array using
05 divide & conquer
write a test program to implement divide and conquer strategy (quick
06 sort)
write a program to implement merge sort algorithm for sorting a list of
07 integeres in ascending order
write a program that accepts the vertices and edges for a graph and stores it
08 as an adjacency matrix
implement function to print in-degree, out-degree and to display the
09 adjacency matrix matrix
write a program to perform knapsack problem using greedy solution
10 technique
write a program to implement the backtracking algorithm for solving
11 problem like nqueens
write a program to implement the backtracking algorithm for the sum of
12 subsets problem
write program to implement greedy algorithm for job sequencing with
13 deadlines
write program to implement dynamic programming algorithm for the optimal
14 binary search tree problem
write a program that implements prim's algorithm to generate minimum cost
15 spanning tree
write a program that implements kruskal's algorithm to generate minimum
16 spanning tree

DARK_SOUL
 DARK_SOUL
DAA PROGRAMS

PROGRAM - 01

WRITE A PROGRAM TO SORT A LIST OF N ELEMENTS USING

SELECTION SORT TECHNIQUE.
#include<stdio.h>
#include<conio.h>
main()
{
int n,j,temp,pos,i,a[10];
clrscr();

printf("ENTER THE LIMIT : ");

scanf("%d",&n);
printf("ENTER THE ARRAY ELEMNET : \n");

for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<n;i++)
{
pos=i;
for(j=i+1;j<n;j++)
{
if(a[j]<a[pos])
{
pos = j;
}
}
temp = a[i];
a[i] = a[pos];
a[pos] = temp;
}

printf("SORTED ARRAY IS \n",a[i]);

for(i=0;i<n;i++)
{
printf("%d \n",a[i]);
}
getch();
return 0;
}
 DARK_SOUL
PROGRAM - 02
WRITE A PROGRAM TO SOLVE TRAVELING SALESMAN
PROBLEM.
#include<stdio.h>
int ar[10][10], completed[10], n, cost = 0;

void takeinput()
{
int i, j;
printf("ENTER THE NUMBER OF CITIES : ");
scanf("%d", &n);
printf("ENTER THE COST MATRIX : \n");
for(i = 0; i < n; i++)
{
printf("ENTER THE ELEMENTS OF THE ROW : %d\n", i + 1);
for(j = 0; j < n; j++)
{
scanf("%d", &ar[i][j]);
completed[i] = 0;
}
}

printf("THE COST LIST IS : \n");

for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
{
printf("%d ", ar[i][j]);
}
printf("\n");
}
}

void mincost(int city)

{
int ncity;
completed[city] = 1;
printf("%d --> ", city + 1);
ncity = least(city);
 DARK_SOUL
if(ncity == 999)
{
ncity = 0;
printf("%d", ncity + 1);
cost = cost + ar[city][ncity];
return;
}
mincost(ncity);
}
int least(int c)
{
int i, nc = 999;
int min = 999, kmin;
for(i = 0; i < n; i++)
{
if((ar[c][i] != 0) && (completed[i] == 0))
{
if(ar[c][i] + ar[i][c] < min)
{
min = ar[c][i] + ar[c][i];
kmin = ar[c][i];
nc = i;
}
}
}
if(min != 999)
{
cost = cost + kmin;
}
return nc;
}
int main()
{
clrscr();
takeinput();
printf("\nTHE PATH IS : \n");
mincost(0);
printf("\nMINIMUM COST IS : %d \n", cost);
getch();
return 0;
}
 DARK_SOUL
PROGRAM - 03
WRITE A TO IMPLEMENT DYNAMIC PROGRAMMING
ALGORITHM FOR THE 0/1 KNAPSACK PROBLEM.
#include <stdio.h>
#include <conio.h>

int max(int a, int b)

{
if (a > b)
{
return a;
}
else
{
return b;
}
}

int knapsack(int W, int wt[], int val[], int n)

{
int i, w;
int knap[10][100];
for (i = 0; i <= n; i++)
{
for (w = 0; w <= W; w++)
{
if (i == 0 || w == 0)
{
knap[i][w] = 0;
}
else if (wt[i - 1] <= w)
{
knap[i][w] = max(val[i - 1] + knap[i - 1][w - wt[i - 1]], knap[i - 1][w]);
}
else
{
knap[i][w] = knap[i - 1][w];
}
}
}
return knap[n][W];
}
 DARK_SOUL
int main()
{
int val[] = {20, 25, 40};
int wt[] = {25, 20, 30};
int w = 50;
int n = sizeof(val) / sizeof(val[0]);

clrscr(); // Clear the screen

printf("THE SOLUTION IS: %d", knapsack(w, wt, val, n));
getch();
return 0;
}
 DARK_SOUL
PROGRAM - 04
WRITE A PROGRAM TO IMPLEMENT THE DFS AND BFS
ALGORITHM FOR A GRAPH
#include <stdio.h>

int a[10][10], v[10], n;

void dfs(int x)
{
int i;
printf("%d ", x);
v[x] = 1;
for (i = 0; i < n; i++)
{
if (a[x][i] && !v[i])
{
dfs(i);
}
}
}

void bfs(int x)
{
int q[10], f = 0, r = 0, i;
q[r++] = x;
v[x] = 1;
while (f < r)
{
x = q[f++];
printf("%d ", x);
for (i = 0; i < n; i++)
{
if (a[x][i] && !v[i])
{
q[r++] = i;
v[i] = 1;
}
}
}
}
 DARK_SOUL
void main()
{
int start, i, j;
clrscr();
printf("Enter number of vertices: ");
scanf("%d", &n);

printf("Enter adjacency matrix:\n");

for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
scanf("%d", &a[i][j]);
}
}

printf("Enter starting vertex: ");

scanf("%d", &start);

printf("DFS: ");
dfs(start);

for (i = 0; i < n; i++)

{
v[i] = 0; // Reset visited array for BFS
}

printf("\nBFS: ");
bfs(start);
getch();
}
 DARK_SOUL
PROGRAM - 05
WRITE A PROGRAM TO FIND THE MINIMUM AND MAXIMUM
VALUE IN AN ARRAY USING DIVIDE AND CONQUER.
#include<stdio.h>
int max,min;
int a[50];
void maxmin(int i,int j)
{
int max1, min1, mid;
if(i == j)
{
max = min = a[i];
}
else
{
if (i == j-1)
{
if (a[i] < a[j])
{
max = a[j];
min = a[i];
}
else
{
max = a[i];
min = a[j];
}
}
else
{
mid = (i+j)/2;
maxmin(i,mid);
max1 = max;
min1 = min;
maxmin(mid+1,j);
if (max < max1)
{
max = max1;
}
if (min > min1)
{
min = min1;
}
 DARK_SOUL
}
}
}
int main()
{
int i, num;
clrscr();
printf("ENTER THE TOTAL NUMBER OF ELEMENTS : ");
scanf("%d",&num);
printf("ENTER THE NUMBERS : \n");
for(i=1;i<=num;i++)
{
scanf("%d",&a[i]);
}
max = a[0];
min = a[0];
maxmin(1,num);
printf("MINIMUM ELEMENT IN AN ARRAY : %d \n",min);
printf("MAXIMUM ELEMENT IN AN ARRAY : %d \n",max);
getch();
return 0;
}
 DARK_SOUL
PROGRAM - 06
WRITE A PROGRAM TO IMPLEMENT DIVIDE AND CONQUER
STRATEGY EG: QUICK SORT
#include<stdio.h>
#include<conio.h>

int partition(int a[], int low, int high)

{
int i, j, temp, key;
key = a[low];
i = low + 1;
j = high;

while (i <= j)
{
while (i <= high && a[i] <= key)
i++;
while (j >= low && a[j] > key)
j--;

if (i < j)
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}

temp = a[low];
a[low] = a[j];
a[j] = temp;

return j;
}
 DARK_SOUL
void quicksort(int a[], int low, int high)
{
int j;
if (low < high)
{
j = partition(a, low, high);
quicksort(a, low, j - 1);
quicksort(a, j + 1, high);
}
}
void main()
{
int i, n, a[500];
clrscr();
printf("ENTER THE NUMBER OF ELEMENTS: ");
scanf("%d", &n);
printf("ENTER %d NUMBERS TO BE SORTED:\n", n);
for (i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
quicksort(a, 0, n - 1);
printf("THE SORTED NUMBERS ARE:\n");
for (i = 0; i < n; i++)
{
printf("%d\n", a[i]);
}
getch();
}
 DARK_SOUL
PROGRAM - 07
WRITE A PROGRAM TO IMPLEMENT MERGE SORT ALGORITHM
FOR SORTING A LIST OF INTEGERS IN ASCENDING ORDER.

#include<stdio.h>
#include<conio.h>
void merge(int a[], int low, int mid, int high)
{
int i, j, k, c[10];
i = low;
j = mid + 1;
k = low;

while (i <= mid && j <= high)

{
if (a[i] < a[j]) {
c[k++] = a[i++];
} else {
c[k++] = a[j++];
}
}

while (i <= mid)

{
c[k++] = a[i++];
}

while (j <= high)

{
c[k++] = a[j++];
}

for (i = low; i <= high; i++)

{
a[i] = c[i];
}
}
 DARK_SOUL
void mergesort(int a[], int low, int high)
{
int mid;
if (low < high)
{
mid = (low + high) / 2;
mergesort(a, low, mid);
mergesort(a, mid + 1, high);
merge(a, low, mid, high);
}
}
void main()
{
int n, i, a[10];
clrscr();
printf("ENTER THE NUMBER OF ELEMENTS : \n");
scanf("%d", &n);
printf("ENTER THE ELEMENTS : \n");
for (i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
mergesort(a, 0, n - 1);
printf("THE SORTED NUMBERS ARE :\n");
for (i = 0; i < n; i++)
{
printf("%d \n", a[i]);
}
getch();
}
 DARK_SOUL
PROGRAM - 08
WRITE A C PROGRAM THAT ACCEPTS THE VERTICES AND
EDGES FOR A GRAPH AND STORES IT AS AN ADJACENCY
MATRIX.
#include<stdio.h>
#define max 5
int adjmat[max][max];
void addedge(int i,int j)
{
adjmat[i][j] = 1;
adjmat[j][i] = 1;
}
void main()
{
int i,j;
clrscr();
for ( i = 0; i < max; i++)
{
for ( j = 0; j < max; j++)
{
adjmat[i][j] = 0;
}
}
printf("INITIALIZING......\n");
addedge(0,1);
addedge(0,2);
addedge(0,3);
addedge(0,2);
addedge(2,3);
addedge(2,4);
printf("THE GIVEN GRAPH's ADJACENCY MATRIX IS :\n");
for ( i = 0; i < max; i++)
{
for ( j = 0; j < max; j++)
{
printf("%d",adjmat[i][j]);
}
printf("\n");
}
getch();
}
 DARK_SOUL
PROGRAM - 09

WRITE A PROGRAM FOR IMPLEMENTING FUNCTION TO PRINT

IN-DEGREE ,OUT-DEGREE AND TO DISPLAY THAT
ADJACENCY MATRIX
#include<stdio.h>
#define max 5
int adjmat[max][max];
void main()
{
int i, j, sumin, sumout;
clrscr();
for(i = 0; i < max; i++)
{
for(j = 0; j < max; j++)
{
if(i == j)
{
adjmat[i][j] = 0;
}
else
{
printf("EDGE V (%d, %d) EXISTS...? (YES=1, NO=0): ", i, j);
scanf("%d", &adjmat[i][j]);
}
}
}

printf("THE GIVEN GRAPH ADJACENCY MATRIX IS:\n");

for(i = 0; i < max; i++)
{
for(j = 0; j < max; j++)
{
printf("%d ", adjmat[i][j]);
}
printf("\n");
}
 DARK_SOUL
for(i = 0; i < max; i++)
{
sumin = 0;
for(j = 0; j < max; j++)
{
sumin += adjmat[j][i];
}
printf("IN DEGREE OF VERTEX (%d) = %d \n", i, sumin);
}
getch();
}
 DARK_SOUL
PROGRAM - 10
WRITE A C PROGRAM TO PERFORM KNAPSACK PROBLEM
USING GREEDYSOLUTION.
#include<stdio.h>
#include<conio.h>
void knapsack(int n,float weight[],float profit[],float capacity)
{
float x[20],tp = 0;
int i,j,u;
u = capacity;

for(i = 0; i < n; i++)

{
x[i] = 0.0;
}
for ( i = 0; i < n; i++)
{
if(weight[i] > u)
break;
else
{
x[i] = 1.0;
tp = tp + profit[i];
u = u - weight[i];
}
}
if (i<n)
{
x[i] = u / weight[i];
}
tp = tp + (x[i] * profit[i]);
printf("\n THE RESULT VECTOR IS : ");
for(i = 0;i < n;i++)
{
printf("%f \t",x[i]);
}
printf("\n MAXIMUM PROFIT IS : %f",tp);
}
 DARK_SOUL
int main()
{
float weight[20],profit[20],capacity;
int num,i,j;
float ratio[20],temp;
clrscr();
printf("\n ENTER THE NO. OF OBJECTS :");
scanf("%d",&num);

printf("\n ENTER THE WEIGHTS AND PROFITS OF EACH OBJECT : ");

for(i = 0;i < num;i++)
{
scanf("%f%f",&weight[i],&profit[i]);
}
printf("\n ENTER THE CAPACITY OF KNAPSACK :");
scanf("%f",&capacity);
for ( i = 0; i < num; i++)
{
ratio[i] = profit[i] / weight[i];
}
for ( i = 0; i < num; i++)
{
for ( j = i+1; j < num; j++)
{
if (ratio[i] < ratio[i])
{
temp = ratio[j];
ratio[j] = ratio[i];
ratio[i] = temp;
temp = weight[j];
weight[j] = weight[i];
weight[j] = temp;
temp = profit[j];
profit[j] = profit[i];
profit[i] = temp;
}
}
}
knapsack(num,weight,profit,capacity);
getch();
return(0);
}
 DARK_SOUL
PROGRAM - 11
WRITE A C PROGRAM TO IMPLEMENT BACKTRACKING
ALGORITHM FOR SOLVING PROBLEM LIKE NQUEENS.
#include<stdio.h>
#define N 8
void printsolution(int board[N][N])
{
int i,j;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
if(board[i][j])
{
printf("Q");
}
else
{
printf(".");
}
}
printf("\n");
}
}
int issafe(int board[N][N],int row,int col)
{
int i,j;
for(i=0;i<col;i++)
{
if(board[row][i])
{
return 0;
}
}
for (i=row,j=col;i >=0 && j >= 0;i--,j--)
{
if(board[i][j])
{
return 0;
}
}
return 1;
}
 DARK_SOUL
int solve(int board[N][N],int col)
{
int i;
if(col >= N)
return 1;
for(i=0;i<N;i++)
{
if(issafe(board,i,col))
{
board[i][col] = 1;
if(solve(board,col+1))
{
return 1;
}
board[i][col] = 0;
}
}
return 0;
}
int solveNQ()
{
int board[N][N] = {{0,0,0,0},
{0,0,0,0},
{0,0,0,0},
{0,0,0,0},
};
if(solve(board,0)==0)
{
printf("SOLUTION DOES NOT EXISTS");
return 0;
}
printsolution(board);
return 1;
}
void main()
{
clrscr();
solveNQ();
getch();
}
 DARK_SOUL
PROGRAM - 12

WRITE A PROGRAM FOR IMPLEMENT THE BACKTRACKING

ALGORITHM FOR THE SUM OF SUBSETS PROBLEM

#include<stdio.h>
void printsubset(int subset[],int size)
{
int i;
printf("SUBSET : f ");
for(i=0;i<size;i++)
{
printf("%d",subset[i]);
}
printf(")\n");
}
void sumofsubset(int wt[],int tsum,int n,int subset[],int subsetsize,int sum,int index)
{
int i;
if(sum == tsum)
{
printsubset(subset,subsetsize);
return;
}
for(i=index;i<n;i++)
{
if(sum+wt[i] <= tsum)
{
subset[subsetsize] = wt[i];
sumofsubsets(wt,tsum,n,subset,subsetsize+1,sum+wt[i],i+1);
}
}
}
 DARK_SOUL
void main()
{
int n,i,tsum;
int wt[20],subset[20];
clrscr();
printf("ENTER THE NUMBER OF ELEMENTS : ");
scanf("%d",&n);
printf("\n ENTER THE ELEMENTS : ");
for(i=0;i<n;i++)
{
scanf("%d",&wt[i]);
}
printf("\n ENTER THE TARGET SUM : ");
scanf("%d",&tsum);
sumof(subset(wt,tsum,n,subset,0,0,0));
getch();
}
 DARK_SOUL
PROGRAM - 13
WRITE A C PROGRAM TO IMPLEMENT GREEDY ALGORITHM
FOR JOB SEQUENCING WITH DEADLINES.
#include<stdio.h>
#include<conio.h>

void job(int profit[], int deadline[], int n, int maxdead)

{
int result[20] = {0}, total = 0, i, j;

for(i = 0; i < n; i++)

{
if(result[deadline[i] - 1] == 0)
{
result[deadline[i] - 1] = profit[i];
total += profit[i];
}
else
{
for(j = deadline[i] - 1; j >= 0; j--)
{
if(result[j] == 0)
{
result[j] = profit[i];
total += profit[i];
break;
}
}
}
}

printf("TOTAL PROFIT IS: %d\n", total);

printf("OUTPUT ARRAY IS:\n");
for(i = 0; i < maxdead; i++)
{
printf("AT INDEX %d -> %d\n", i + 1, result[i]);
}
}
 DARK_SOUL
void main()
{
int profit[20], deadline[20], n, i, maxdead;
clrscr();
printf("JOB SEARCHING\n");
printf("ENTER THE NUMBER OF ELEMENTS:\n");
scanf("%d", &n);

printf("ENTER THE PROFIT IN DESCENDING ORDER:\n");

for(i = 0; i < n; i++)
{
scanf("%d", &profit[i]);
}

printf("ENTER THE DEADLINE ACCORDING TO THE ORDERED PROFITS ENTERED:\n");

for(i = 0; i < n; i++)
{
scanf("%d", &deadline[i]);
}

printf("ENTER THE MAX DEADLINE:\n");

scanf("%d", &maxdead);

job(profit, deadline, n, maxdead);

getch();
}
 DARK_SOUL
PROGRAM - 14
WRITE A C PROGRAM TO IMPLEMENT DYNAMIC
PROGRAMMING ALGORITHM FOR THE OPTIMAL BINARY
SEARCH TREE
#include<stdio.h>
#include<conio.h>

int add(int freq[], int i, int j)

{
int k, s = 0;
for (k = i; k <= j; k++)
{
s += freq[k];
}
return s;
}

int opticost(int freq[], int i, int j)

{
int freqsum, min = 999, r, opcost;
if (j < i)
{
return 0;
}
if (i == j)
{
return freq[i];
}
freqsum = add(freq, i, j);
for (r = i; r <= j; ++r)
{
opcost = opticost(freq, i, r - 1) + opticost(freq, r + 1, j);
if (opcost < min)
{
min = opcost;
}
}
return min + freqsum;
}
 DARK_SOUL
void main()
{
int key[] = {10, 12, 20};
int freq[] = {50, 8, 64};
int n = sizeof(key) / sizeof(key[0]);
clrscr();
printf("COST OF OBTS IS %d", opticost(freq, 0, n - 1));
getch();
}
 DARK_SOUL
PROGRAM - 15
WRITE A C PROGRAM TO IMPLEMENT PRIM’S ALGORITHM TO
GENERATE MINIMUM COST SPANNING TREE
#include<stdio.h>
#include<limits.h>
#define vertices 5
int minimum_key(int k[],int mst[])
{
int minimum = INT_MAX,min,i;
for(i = 0;i < vertices; i++)
{
if (mst[i] == 0 && k[i] < minimum)
{
minimum = k[i],min = i;
}
}
return min;
}
void prim(int g[vertices][vertices])
{
int parent[vertices];
int k[vertices];
int mst[vertices];
int i,count,edge,v;
for(i = 0;i < vertices;i++)
{

k[i] = INT_MAX;
mst[i] = 0;
}
k[0] = 0;
parent[0] = -1;
for(count = 0;count < vertices-1; count++)
{
edge = minimum_key(k,mst);
mst[edge] = 1;
for ( v = 0; v < vertices; v++)
{
if(g[edge][v] && mst[v] == 0 && g[edge][v] < k[v])
{
parent[v] = edge,k[v] = g[edge][v];
}
}
}
 DARK_SOUL
printf("\n EDGE \t WEIGHT \n");
for(i=1;i<vertices;i++)
{
printf("%d <-> %d %d \n",parent[i],i,g[i][parent[i]]);
}
}
int main()
{
int g[vertices][vertices] = {{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}};
prim(g);
getch();
return 0;
}
 DARK_SOUL
PROGRAM - 16
WRITE A C PROGRAM TO IMPLEMENT KRUSHKAL’S
ALGORITHM TO GENERATE MINIMUM COST SPANNING TREE
/#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

int i, j, k, a, b, n, v, u, ne = 1;
int min, mincost = 0, cost[9][9], parent[9];

int find(int);
int uni(int, int);

void main()
{
clrscr();
printf("\n \t IMPLEMENTATION OF KRUSKAL'S ALGORITHM \n");
printf("\n ENTER THE NUMBER OF VERTICES : ");
scanf("%d", &n);

printf("\n ENTER THE COST ADJACENCY MATRIX : \n \t");

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++)
{
 DARK_SOUL
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 edge (%d, %d) = %d\n", ne++, a, b, min);
mincost += min;
}

cost[a][b] = cost[b][a] = 999;

}

printf("\n \t MINIMUM COST = %d\n", mincost);

getch();
}

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;
}