Program 1.

Write a program to sort a list of N elements using Selection Sort

Technique.
#include<stdio.h>
#include<conio.h>
void main()
{
int a[20];
int i, j, n, temp, pos;
clrscr();
printf("\n Enter the value of n : \n");
scanf("%d",&n);
printf("\n Enter the elements of the array : \n");

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

scanf("%d",&a[i]);

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

{
pos=i;
for( j=i+1; j<=n-1; j++)
{
if ( a[ j ] < a[pos] )
pos = j;
}

temp=a[pos];
a[pos]=a[i];
a[i]=temp;
}
printf("\n The sorted elements of the array are :\n ");

for(i=0;i<n;i++)
{
printf("\n %d",a[i]);
}
getch();
}
Output:

Enter the value of n :

Enter the elements of the array :

3
9
56
20
16
7
10
25

The sorted elements of the array are :

3
7
9
10
16
20
25
56
Program 2: Write a program to perform Travelling Sales man Problem.

#include<stdio.h>
int matrix[10][10],completed[10],n,cost=0;

void mincost(int city)

{
int i,ncity;
completed[city]=1;
printf("%d--->",city+1);
ncity=least(city);

if(ncity==999)
{
ncity=0;
printf("%d",ncity+1);
cost=cost+matrix[city][ncity];
return;
}
mincost(ncity);
}

int least(int c)
{
int i,nc=999;
int min=999,kmin;

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

{
if((matrix[c][i]!=0) && (completed[i]==0))
if(matrix[c][i]+matrix[i][c] < min)
{
min=matrix[i][0]+matrix[c][i];
kmin=matrix[c][i];
nc=i;
}
}

if(min!=999)
cost=cost+kmin;
return nc;
}
int main()
{
int i,j;

printf("Enter the number of cities : ");

scanf("%d",&n);
printf("\nEnter the Cost Matrix\n");

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

{
printf("\nEnter Elements of Row: %d\n",i+1);
for( j=0;j < n;j++)
scanf("%d",&matrix[i][j]);
completed[i]=0;
}

printf("\n\nThe cost list is:");

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

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

printf("\n\nThe Path is:\n");

mincost(0); //passing 0 because starting vertex

printf("\n\nMinimum cost is : %d\n ",cost);

return 0;
}
Output

Enter the number of cities: 4

Enter Elements of Row: 1

0413

Enter Elements of Row: 2

4021

Enter Elements of Row: 3

1205

Enter Elements of Row: 4

3150

The cost list is:

0 4 1 3
4 0 2 1
1 2 0 5
3 1 5 0

The Path is:

1--->3--->2--->4--->1

Minimum cost is : 7
Program 3. Write program to implement Dynamic Programming
algorithm for the 0/1 Knapsack problem.
#include <stdio.h>
int max(int a, int b)
{
if ( a>b )
return a;
else
return b;
}
// Returns the maximum value that can be put in a knapsack of capacity W

int knapsack(int cap, int wt[], int prf[], int n)

{
int i, w;
int knap[5][50];

// Build table knap[][] in bottom up manner

for (i = 0; i <= n; i++)
{
for (w = 0; w <= cap; w++)
{
if (i==0 || w==0)
knap[i][w] = 0;
else if (wt[i-1] <= w)
knap[i][w] = max(prf[i-1] + knap[i-1][w-wt[i-1]], knap[i-1][w]);
else
knap[i][w] = knap[i-1][w];
}
}
return knap[n][cap];
}
int main()
{
int prf[] = {60, 100, 120};
int wt[] = {10, 20, 30};
int cap = 50;
int n = sizeof(prf)/sizeof(prf[0]);
clrscr();
printf("\nProfit = %d", knapsack(cap, wt, prf, n));
return 0;
}

Output

Profit = 220
Program 4 .Write program to implement the DFS and BFS algorithm for a graph.
#include<stdio.h>
int q[20],top=-1,front=-1,rear=-1,a[20][20],vis[20],stack[20];
int delete();
void add(int item);
void bfs(int s,int n);
void dfs(int s,int n);
void push(int item);
int pop();
void main()
{
int i,n,s,ch,j;
char c,dummy;
clrscr();
printf("\n Enter the number of vertices : ");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf(" Enter 1 if %d has a node with %d else 0 : ",i,j);
scanf("%d",&a[i][j]);
}
}
printf("\n The adjacency matrix \n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%d ",a[i][j]);
}
printf("\n");
}
do
{
for(i=1;i<=n;i++)
vis[i]=0;
printf("\n MENU");
printf("\n [Link]");
printf("\n [Link]");
printf("\n Enter your choice : ");
scanf("%d",&ch);
printf("\n Enter the source vertex :");
scanf("%d",&s);
switch(ch)
{
case 1:
bfs(s,n);
break;
case 2:
dfs(s,n);
break;
}
 printf("\n Do u want to continue(y/n)? : ");
scanf("%c",&dummy);
scanf("%c",&c);
}while((c=='y') || (c=='Y'));
getch();
}

//BFS
void bfs(int s,int n)
{
int p,i;
add(s);
vis[s]=1;
p=delete();
if(p!=0)
printf("%d ",p);
while(p!=0)
{
for(i=1;i<=n;i++)
if((a[p][i]!=0) && (vis[i]==0))
{
add(i);
vis[i]=1;
}
p=delete();
if(p!=0)
printf("%d ",p);
}

for(i=1;i<=n;i++)
if(vis[i]==0)
bfs(i,n);
}

void add(int item)

{
if(rear==19)
printf("Queue full");
else
{
if(rear==-1)
{
q[++rear]=item;
front++;
}
else
q[++rear]=item;
}
}
int delete()
{
int k;
if((front>rear) || (front==-1))
return(0);
else
{
k=q[front++];
return(k);
}
}
//DFS
void dfs(int s,int n)
{
int i,k;
push(s);
vis[s]=1;
k=pop();
if(k!=0)
printf("%d ",k);
while(k!=0)
{
for(i=1;i<=n;i++)
if((a[k][i]!=0) && (vis[i]==0))
{
push(i);
vis[i]=1;
}
k=pop();
if(k!=0)
printf("%d ",k);
}
for(i=1;i<=n;i++)
if(vis[i]==0)
dfs(i,n);
}
void push(int item)
{
if(top==19)
printf("\n Stack Overflow ");
else
stack[++top]=item;
}

int pop()
{
int k;
if(top==-1)
return(0);
else
{
k=stack[top--];
return(k);
}
}
Output

Enter 1 if 1 has a node with 1 else 0 : 0

Enter 1 if 1 has a node with 2 else 0 : 1
Enter 1 if 1 has a node with 3 else 0 : 1
Enter 1 if 1 has a node with 4 else 0 : 1

Enter 1 if 2 has a node with 1 else 0 : 1

Enter 1 if 2 has a node with 2 else 0 : 0
Enter 1 if 2 has a node with 3 else 0 : 1
Enter 1 if 2 has a node with 4 else 0 : 0

Enter 1 if 3 has a node with 1 else 0 : 1

Enter 1 if 3 has a node with 2 else 0 : 1
Enter 1 if 3 has a node with 3 else 0 : 0
Enter 1 if 3 has a node with 4 else 0 : 1

Enter 1 if 4 has a node with 1 else 0 : 1

Enter 1 if 4 has a node with 2 else 0 : 0
Enter 1 if 4 has a node with 3 else 0 : 1
Enter 1 if 4 has a node with 4 else 0 : 0

The adjacency matrix

0111
1010
1101
1010

MENU
[Link]
[Link]
Enter your choice : 1

Enter the source vertex :1

1234

Do u want to continue(y/n)? : y

MENU
[Link]
[Link]
Enter your choice : 2

Enter the source vertex :1

1432

Do u want to continue(y/n)? : n
Program 5: Write n program to find minimum and maximum value in an
array using divide and conquer.

#include<stdio.h>
#include<conio.h>
int max, min, i, j, mid, a[10], n;
void maxmin (int i, int j)
{
int min1,min2,max1,max2;
if(i==j)
min=max=a[i];
else if (i==j-1)
{
if(a[i]>a[j])
{
max=a[i];
min=a[j];
}
else
{
max=a[j];
min=a[i];
}
}
else
{
mid=(i+j)/2;
maxmin(i,mid);
min1=min;
max1=max;
maxmin(mid+1,j);
min2=min;
max2=max;
if(max1<max2)
max=max2;
else
max=max1;
if(min1>min2)
min=min2;
else
min=min1;
}
}
void main()
{
int n;
clrscr();
printf("Enter the limit\n");
scanf("%d",&n);
printf("Enter the elements \n");
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
maxmin (1,n);
printf("\n\n Max=%d\n Min=%d\n",max,min);
getch();
}
Output

Enter the limit

5

Enter the elements

20
22
30
2
50

Max=50
Min=2
Program 6: Write a test program to implement Divide and Conquer Strategy. Eg:
Quick sort algorithm for sorting list of integers in ascending order.

#include<stdio.h>
#include<conio.h>
int key, a[20];
void quicksort(int,int);
int partition(int,int);
void exchange(int,int);

void main()
{
int i,n;
clrscr();
printf("Enter the Limit\n");
scanf("%d",&n);
printf("Enter the elements ...\n");
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
quicksort(1,n);
printf("sorted list\n");

for(i=1;i<=n;i++)
printf("%d\n",a[i]);
getch();
}

void quicksort(int low,int high)

{
int i,j;
if(low<high)
{
j=partition(low,high+1);
quicksort(low,j-1);
quicksort(j+1,high);
}
}

void exchange(int i,int j)

{
int p=a[i];
a[i]=a[j];
a[j]=p;
}
int partition(int first,int last)
{
int i,j;
key=a[first];
i=first;
j=last;

do
{
do
{
i++;
} while(a[i]<key);

do
{
j--;
} while(a[j]>key);

if(i<j)
exchange(i,j);
}while(i<j);
a[first]=a[j];
a[j]=key;
return j;
}
Output

Enter the Limit

10

Enter the elements ...

4
50
34
20
14
10
5
67
80
15

sorted list

4
5
10
14
15
20
34
50
67
80
Program 7 : Write a program to implement Merge sort algorithm for
sorting a list of integers in ascending order.

#include<stdio.h>
#include<conio.h>
int i,j,k,a[20];
void mergesort(int,int);
void merge(int,int,int);
void main()
{
int n;
clrscr();
printf("enter the size of an array\n");
scanf("%d",&n);
printf("enter the elements of an array\n");
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=1;i<=n;i++)
mergesort(1,n);
printf("the sorted list is\n");
for(i=1;i<=n;i++)
printf("%d\n",a[i]);
getch();
}

void mergesort(int low,int high)

{
int mid;
if(low<high)
{
mid=(low+high)/2;
mergesort(low,mid);
mergesort(mid+1,high);
merge(low,mid,high);
}
}

void merge(int low,int mid,int high)

{
int b[20],h=low,i=low,j=mid+1;
while((h<=mid)&&(j<=high))
{
if(a[h]<=a[j])
{
b[i]=a[h];
i=i+1;
h=h+1;
}
 else
{
b[i]=a[j];
i=i+1;
j=j+1;
}
}
if(h>mid)
{
for(k=i;k<=high;k++)
{
b[i]=a[k];
i=i+1;
}
}
else
{
for(k=h;k<=mid;k++)
{
b[i]=a[k];
i=i+1;
}
}
for(k=low;k<=high;k++)
a[k]=b[k];
}
output

enter the size of an array

5
enter the elements of an array

4
3
5
2
6

the sorted list is

2
3
4
5
6
Program 8. Write a program that accepts the vertices and edges for a
graph and stores it as an adjacency matrix.

int main()
{
int adjmatrix[20][20] = {0}; // Initialize the adjacency matrix with zeros
int numvert, numedges;
int i, j, u, v;

clrscr();
printf("Enter the number of vertices in the graph: ");
scanf("%d", &numvert);
printf("Enter the number of edges in the graph: ");
scanf("%d", &numedges);
// Accept the edges from the user and store them in the adjacency matrix
printf("Enter the edges (u, v):\n");

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

{
scanf("%d %d", &u, &v);
adjmatrix[u][v] = 1;
adjmatrix[v][u] = 1; // If the graph is undirected, set both vertices as adjacent

// Display the adjacency matrix

printf("\nAdjacency Matrix:\n");

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

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

Enter the number of vertices in the graph: 4

Enter the number of edges in the graph: 4
Enter the edges (u, v):
0 1
1 2
0 3
2 0

Adjacency Matrix:
0 1 1 1
1 0 1 0
1 1 0 0
1 0 0 0
Program 9: Implement function to print In-Degree, Out-Degree and to
display that adjacency matrix

#include<stdio.h>
#include<conio.h>
#define MAX 10
void accept_graph(int G[][MAX], int n)
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("Edge (V%d,V%d) exists? (Yes=1, No=0):",i,j);
scanf("%d",&G[i][j]);
}
}
}

void disp_adj_mat(int G[][MAX], int n)

{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%4d",G[i][j]);
}
printf("\n");
}
}

void calc_out_degree(int G[][MAX], int n)

{
int i,j,sum;
for(i=1;i<=n;i++)
{
sum=0;
for(j=1;j<=n;j++)
{
sum += G[i][j];
}
printf("out-deg(V%d)=%d\n",i,sum);
}
}
void calc_in_degree(int G[][MAX], int n)
{
int i,j,sum;
for(i=1;i<=n;i++)
{
sum=0;
for(j=1;j<=n;j++)
{
sum += G[j][i];
}
printf("in-deg(V%d)=%d\n",i,sum);
}
}

void main()
{
int G[MAX][MAX],n; clrscr();
printf("Enter no. of vertices:");
scanf("%d",&n);
accept_graph(G,n);
printf("\n\n Adjacency Matrix:\n");
disp_adj_mat(G,n);
printf("\n Out degree:\n");
calc_out_degree(G,n);
printf("\n In degree:\n");
calc_in_degree(G,n);
getch();
}
Output:

Enter no. of vertices: 4

Edge (V1,V1) exists? (Yes=1, No=0):0

Edge (V1,V2) exists? (Yes=1, No=0):1
Edge (V1,V3) exists? (Yes=1, No=0):1
Edge (V1,V4) exists? (Yes=1, No=0):0
Edge (V2,V1) exists? (Yes=1, No=0):0
Edge (V2,V2) exists? (Yes=1, No=0):0
Edge (V2,V3) exists? (Yes=1, No=0):1
Edge (V2,V4) exists? (Yes=1, No=0):0
Edge (V3,V1) exists? (Yes=1, No=0):0
Edge (V3,V2) exists? (Yes=1, No=0):0
Edge (V3,V3) exists? (Yes=1, No=0):0
Edge (V3,V4) exists? (Yes=1, No=0):1
Edge (V4,V1) exists? (Yes=1, No=0):0
Edge (V4,V2) exists? (Yes=1, No=0):1
Edge (V4,V3) exists? (Yes=1, No=0):0
Edge (V4,V4) exists? (Yes=1, No=0):0

Adjacency Matrix:
0 1 1 0
0 0 1 0
0 0 0 1
0 1 0 0

Out degree:
out-deg(V1)=2
out-deg(V2)=1
out-deg(V3)=1
out-deg(V4)=1

In degree:
in-deg(V1)=0
in-deg(V2)=2
in-deg(V3)=2
in-deg(V4)=1
10. Write a program to perform Knapsack Problem using Greedy Solution.

#include<stdio.h>
#include<conio.h>
#include<math.h>
void knapsack(int n,float p[30],float w[30],float c);
void main()
{
float m,p[30],w[30],r[30],temp;
int n,i,j;
clrscr();
printf("enter the number of object\n");
scanf("%d",&n);
printf("enter the capacity\n");
scanf("%f",&m);
printf("enter the weight\n");
for(i=0;i<n;i++)
{
scanf("%f",&w[i]);
}
printf("enter the profit\n");

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

for(i=0;i<n;i++)
{
r[i]=p[i]/w[i];
}

for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(r[i]<r[j])
{
temp=r[j];
r[j]=r[i];
r[i]=temp;

temp=w[j];
w[j]=w[i];
w[i]=temp;

temp=p[j];
p[j]=p[i];
p[i]=temp;
}
}
}
knapsack(n,w,p,m);
getch();
}
void knapsack(int n,float w[30],float p[30],float c)
{
float x[30],tp=0;
int i,j,m;
m=c;
for(i=0;i<n;i++)
x[i]=0.0;
for(i=0;i<n;i++)
{
if(w[i]>m)
break;
else
{
x[i]=1.0;
tp=tp+p[i];
m=m-w[i];
}
}
if(i<n)
{
x[i]=m/w[i];
tp=tp+(x[i]*p[i]);
}
printf("______________________________________________________\n");
printf("object[i]\tw[i]\tp[i]\tx[i]\tp[i]*x[i]\tcapacity\n");
printf("________________________________________________________\n");
for(i=0;i<n;i++)
{
printf("%d\t\t%.2f\t%.2f\t %.2f\t %.2f\t %.2f\n",i+1,w[i],p[i],x[i],p[i]*x[i],c=c-w[i]*x[i]);
}
printf("total profit= %.2f\n",tp);
}
Output

enter the number of object

enter the capacity

40

enter the weight

20 25 10

enter the profit

30 40 35

______________________________________________________

object[i] w[i] p[i] x[i] p[i]*x[i] capacity

________________________________________________________

1 10.00 35.00 1.00 35.00 30.00

2 25.00 40.00 1.00 40.00 5.00

3 20.00 30.00 0.25 7.50 0.00

total profit= 82.50

Program 11: Write a program to implement backtracking algorithm for
solving problems like N Queens.

#include<stdio.h>
#include<conio.h>
#include<math.h>
#define true 1
#define false 0
int x[10],q[10];
int place(int k,int i)
{
int j;
for(j=1;j<k;j++)
{
if((x[j]==i)||abs(x[j]-i)==abs(j-k))
return false;
}
return true;
}

void nqueens(int k,int n)

{
int i,j;
for(i=1;i<=n;i++)
{
if(place(k,i))
{
x[k]=i;
if(k==n)
{
for(j=1;j<=n;j++)
q[j]=x[j];
return;
}
else
nqueens(k+1,n);
}
}
}
void main()
{
int i,j,n,b[10][10];
clrscr();
printf("Enter the number of queens:\n");
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
b[i][j]='x';
nqueens(1,n);
printf("\n\n");
for(j=1;j<=n;j++)
printf("\t%d",q[j]);

printf("\n\n");
printf("The Queens are arranged as \n\n ");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(i==q[j])
printf("\tQ");
else
printf("\t%c",b[i][j]);
}
printf("\n");
}
getch();
}
Output

Enter the number of queens:

5 3 1 4 2

The Queens are arranged as

x x Q x x

x x x x Q

x Q x x x

x x x Q x

Q x x x x
Program 12. Write a program to implement the backtracking algorithm for
the sum of subsets problem.
#include <stdio.h>
#include <stdlib.h>
static int total_nodes;
void printval(int A[], int size)
{
int i;
for ( i = 0; i < size; i++)
{
printf("%*d", 5, A[i]);
}
printf("\n");
}

void subset_sum(int s[], int t[], int s_size, int t_size, int sum, int ite, int const target_sum)
{
int i;
total_nodes++;
if (target_sum == sum)
{
printval(t, t_size);
subset_sum(s, t, s_size, t_size - 1, sum - s[ite], ite + 1, target_sum);
return;
}
else
{
for ( i = ite; i < s_size; i++)
{
t[t_size] = s[i];
subset_sum(s, t, s_size, t_size+1, sum + s[i], i+1, target_sum);
}
}
}

void generateSubsets(int s[], int size, int target_sum)

{
int* tuplet_vector = (int*)malloc(size * sizeof(int));
subset_sum(s, tuplet_vector, size, 0, 0, 0, target_sum);
free(tuplet_vector);
}

int main()
{
int set[] = { 5, 6, 12 , 54, 2 , 20 , 15 };
int size = sizeof(set) / sizeof(set[0]);
printf("The set is ");
printval(set , size);
generateSubsets(set, size, 25);
printf("Total Nodes generated %d\n", total_nodes);
return 0;
}

Output
The set is 5 6 12 54 2 20 15
5 6 12 2
5 20
Total Nodes generated 127
Program 13: Write program to implement greedy algorithm for job
sequencing with deadlines.

#include<stdio.h>
#include<conio.h>
int p[50],job[50],x[10],d[50];
int tot;

void swap(int j)
{
int temp;
temp=p[j+1];
p[j+1]=p[j];
p[j]=temp;

temp=d[j+1];
d[j+1]=d[j];
d[j]=temp;

temp=job[j+1];
job[j+1]=job[j];
job[j]=temp;
}

void profitsort()
{
int i,j;
for(i=0;i<=tot;i++)
for(j=1;j<=tot;j++)
if(p[j]<p[j+1])
swap(j);
}

int jobseq()
{
int i,r,q,k;
d[0]=x[0]=0;
x[1]=1;
k=1;

for(i=2;i<=tot;i++)
{
r=k;
while(d[x[r]] && d[x[r]]!=r)
r--;
if(d[x[r]]<=d[i] && d[i]>r)
{
for(q=k;q>=r;q--)
 x[q+1]=x[q];
x[r+1]=i;
}
k++;
}
return k;
}

void main()
{
int i,a,prf;
clrscr();
for(i=0;i<10;i++)
job[i]=i;
printf("\nEnter how many jobs? \n ");
scanf("%d",&tot);
printf("\nEnter deadline and profit\n");
for(i=1;i<=tot;i++)
{
printf("\n job NO: %d:\t",i);
scanf("%d%d",&d[i],&p[i]);
}
profitsort();
printf("\nJob No . Deadline profit \n");
for(i=1;i<=tot;i++)
printf("\n %-3d %-8d %-6d\n", i,d[i],p[i]);
jobseq();
printf("\nBelow is the optional solution\n");
prf=0;
printf("\nSlot Job [Link] Profit\n");
for(i=1;x[i];i++)
{
printf("\n %-4d %-7d %-8d %d\n",i,job[x[i]],d[x[i]],p[x[i]]);
prf+=p[x[i]];
}
printf("\n Maximum profit :%d",prf);
getch();
}
Output

Enter how many jobs?

4
Enter deadline and profit

job NO: 1: 2 20
job NO: 2: 3 25
job NO: 3: 1 10
job NO: 4: 2 25

Job No . Deadline profit

1 3 25
2 2 25
3 2 20
4 1 10

Below is the optional solution

Slot Job No. Deadline Profit

1 1 2 20
2 4 2 25
3 2 3 25

Maximum Profit: 70
Program : 14 Write program to implement Dynamic Programming algorithm for
the Optimal Binary Search Tree Problem

#include <stdio.h>
#include <limits.h>
int sum(int freq[], int i, int j);
int cost[20][20];
int i,j,k,L,r;
int OBST(int keys[], int freq[], int n)
{
int off_set_sum;
for ( i = 0; i < n; i++)
cost[i][i] = freq[i];
for ( L=2; L<=n; L++)
{
for ( i=0; i<=n-L+1; i++)
{
j = i+L-1;
off_set_sum = sum(freq, i, j);
cost[i][j] = INT_MAX;
for ( r=i; r<=j; r++)
{
int c = ( (r > i)? cost[i][r-1]:0) +((r < j)? cost[r+1][j]:0) +off_set_sum;
if (c < cost[i][j])
cost[i][j] = c;
}
}
}
return cost[0][n-1];
}

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

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

int main()
{
int keys[] = {10, 12, 20};
int freq[] = {34, 8, 50};
int n = sizeof(keys)/sizeof(keys[0]);
printf("Cost of Optimal BST is %d ", OBST(keys, freq, n));
return 0;
}

Output
Cost of Optimal BST is 142
Program 15 : Write a program that implements Prim’s algorithm to

generate minimum cost spanning Tree.

#include<stdio.h>
#include<conio.h>
int a,b,u,v,n,i,j,ne=1;
int visited[10]={0},min,mincost=0,cost[10][10];
void main()
{
clrscr();
printf("enter the number of nodes\n");
scanf("%d",&n);
printf("enter the adjacency of 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;
while(ne<n)
{
min=999;
for(i=1;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("\nedge= %d:(%d,%d)cost=%d\n",ne++,a,b,min);
mincost+=min;
visited[b]=1;
}
cost[a][b]=cost[b][a]=999;
}
printf("\nminimum cost=%d",mincost);
getch();
}
Output

enter the number of nodes

enter the adjacency of matrix

0 3 999 20
3 0 10 5
999 10 0 6
20 5 6 0

edge= 1:(1,2)cost=3

edge= 2:(2,4)cost=5

edge= 3:(4,3)cost=6

minimum cost=14
Program 16: Write a program that implements Kruskal’s algorithm to
generate minimum cost spanning tree.

#include<stdio.h>
#include<conio.h>
int parent[10]={0},min,ne=1,mincost=0;
int i, j, a, b, u, v, n, cost[10][10]={0};
void main()
{
clrscr();
printf("Enter the number of vertex:\n");
scanf("%d",&n);
printf("Enter the graph data\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;
}
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;
}
while(parent[u])
u=parent[u];
while(parent[v])
v=parent[v];
if(u!=v)
{
printf("\n%5d edge(%d %d)=%5d",ne++,a,b,min);
mincost+=min;
parent[v]=u;
}
cost[a][b]=cost[b][a]=999;
}
printf("\n\n\t\t MIN COST:%5d",mincost);
getch();
}
Output

Enter the number of vertex:

4

Enter the graph data

0 3 999 20
3 0 10 5
999 10 0 6
20 5 6 0

1 edge(1 2)= 3
2 edge(2 4)= 5
3 edge(3 4)= 6

MIN COST: 14