1

ADA LAB
PROGRAMS
2

01: Implementation of recursive binary and linear search and calculate the time required to
search the key.

#include<stdio.h>
#include<conio.h>
#include<time.h>
#define MAX 10

int linsearch(int a[],int n,int key)

{
if(n<0)
return -1;
if(a[n-1]==key)
return n;
else
return linsearch(a,n-1,key);
}

int binsearch(int a[],int n,int low,int high,int key)

{
int mid;
if(low>high)
return -1;
mid=(low+high)/2;
if(key==a[mid])
return mid;
if(key<a[mid])
return binsearch(a,n,low,mid-1,key);
else
return binsearch(a,n,mid+1,high,key);
}

void main()
{
clock_t st1,et1,st2,et2;
int a[MAX],i,n,fd1,fd2,key;
clrscr();

st1=clock();
printf("Enter the size:");
scanf("%d",&n);
3

printf("Enter the array\n");

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

st2=clock();
printf("Enter the key:");
scanf("%d",&key);

fd1=linsearch(a,n,key);
et1=clock();

if(fd1==-1)
printf("\nLinear search unsuccessful:\n");
else
printf("\nLinear search successful\n");
printf("Time taken for Linear search= %f ns",(et1-st1)/CLOCKS_PER_SEC);

fd2=binsearch(a,n,0,n-1,key);
et2=clock();

if(fd2==-1)
printf("\nBinary search unsuccessful\n");
else
printf("\nBinary search successful\n");
printf("\nTime taken for Binary search= %f ns",(et2-st2)/CLOCKS_PER_SEC);

getch();
}

Output:
Enter the size: 5
Enter the elements:
34 59 108 26 45
Enter the key: 59
Linear search successful
Time taken for Linear search: 8.1330000 ns
Binary search successful
Time taken for Binary search: 1.813400 ns
4

02: Sort a given list of elements using heap sort and calculate the time required to sort the
elements.

#include<stdio.h>
#include<conio.h>
#include<time.h>

void heapify(int a[],int n)

{
int x,y,z,it;
for(z=0;z<=n;z++)
{
it=a[z];
x=z;
y=x/2;
while(y!=0 && it>a[y])
{
a[x]=a[y];
x=y;
y=x/2;
}
a[x]=it;
}
}

void adjust(int a[],int n)

{
int it,x,y;
y=1;
it=a[y];
x=2*y;
while(x<n)
{
if((x+1)<n)
{
if(a[x]<a[x+1])
x++;
}
5

if(it<a[x])
{
a[y]=a[x];
y=x;
x=2*y;
}
else
break;
}
a[y]=it;
}

void heaps(int a[],int n)

{
int i,temp;
heapify(a,n);
for(i=n;i>=1;i--)
{
temp=a[1];
a[1]=a[i];
a[i]=temp;
adjust(a,i);
}
}

void main()
{
int i,n,a[100];
clock_t st,et;
clrscr();

st=clock();

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

scanf("%d",&n);

printf("Enter the elements:\n");

for(i=1;i<=n;i++)
scanf("%d",&a[i]);
6

heaps(a,n);
et=clock();

printf("The sorted array is\n");

for(i=0;i<n;i++)
printf("%d\t",a[i]);

printf("\nTime taken=%f",(et-st)/CLOCKS_PER_SEC);
getch();
}

Output:
Enter the number of elements: 5
Enter the elements:
10 8 6 3 1
The sorted array is:
1 3 6 8 10
Time taken is: 5.6530541 ns
7

03: Sort a given list using merge sort technique and calculate the time required to sort the
elements.

#include<stdio.h>
#include<conio.h>
#include<time.h>

int c[20],a[20];

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

{
int i,j,k;
k=i=low;
j=mid+1;
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<=k-1;i++)
a[i]=c[i];
}

void merge_sort(int low,int high)

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

void main()
{
int i,n;
clock_t st,et;
clrscr();

st=clock();

printf("Enter the size:");

scanf("%d",&n);

printf("Entre the elements\n");

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

merge_sort(0,n-1);
et=clock();

printf("The sorted array is:\n");

for(i=0;i<n;i++)
printf("%d\t",a[i]);

printf("\nTime taken by merge sort=%f ns",(et-st)/CLOCKS_PER_SEC);

getch();
}

Output:
Enter the size: 5
Enter the elements:
3 6 1 8 4
The sorted array:
1 3 4 6 8
The time taken: 6.125847 ns
9

04: Sort the given list of elements using selection sort and calculate the time required to sort
the elements.

#include<stdio.h>
#include<conio.h>
#include<time.h>

int min(int a[],int i,int n)

{
int j,loc,min;
min=a[i];
loc=i;
for(j=i+1;j<n;j++)
if(a[j]<min)
{
min=a[j];
loc=j;
}
return loc;
}

void main()
{
int a[10],n,i,loc,temp;
clock_t st,et;

st=clock();

printf("Enter the size:");

scanf("%d",&n);

printf("Enter the elements\n");

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

for(i=0;i<n;i++)
{
loc=min(a,i,n);
temp=a[i];
a[i]=a[loc];
10

a[loc]=temp;
}
et=clock();

printf("The sorted array\n");

for(i=0;i<n;i++)
printf("%d\t",a[i]);

printf("\nTime taken=%f",(et-st)/CLOCKS_PER_SEC);
getch();
}

Output:
Enter the size: 5
Enter the elements:
29 64 36 89 12
The sorted array:
12 29 36 64 89
Time taken: 11.7054821 ns
11

05: Implement 0/1 Knapsack problem using dynamic programming.

#include<stdio.h>
#include<conio.h>

int w[10],p[10],n,i,capacity,maxprofit;

int maximum(int x,int y)

{
if(x>y)
return x;
else
return y;
}

knapsac(int i,int c)
{
if(i==n)
return((c<w[n])? 0:p[n]);

if(c<w[i])
return knapsac(i+1,c);

return maximum(knapsac(i+1,c),knapsac(i+1,c-w[i])+p[i]);
}

void main()
{
clrscr();

printf("Entre the objects:");

scanf("%d",&n);

printf("Entre the weigts:\n");

for(i=1;i<=n;i++)
scanf("%d",&w[i]);
12

printf("Entre the profits:\n");

for(i=1;i<=n;i++)
scanf("%d",&p[i]);

printf("Entre the capacity:");

scanf("%d",&capacity);

maxprofit=knapsac(0,capacity);
printf("The maximum profit=%d",maxprofit);

getch();
}

Output:
Enter the objects: 3
Enter weights:
100 14 10
Enter the profit:
20 18 15
Enter the capacity: 116

Maxprofit=38
13

06: From a given vertex in a weighted connected graph, find shortest paths to other vertices
using Dijkstra’s algorithm

#include<stdio.h>
#include<conio.h>

void dij(int n,int v,int cost[10][10],int dist[])

{
int count,u,i,w,flag[10],min;
for(i=1;i<=n;i++)
{
flag[i]=0;
dist[i]=0;
dist[i]=cost[v][i];
}
flag[v]=1;
dist[v]=1;
count=2;
while(count<=n)
{
min=999;
for(w=1;w<=n;w++)
if(dist[w]<min && !flag[w])
{
min=dist[w];
u=w;
}
flag[u]=1;
count++;

for(w=1;w<=n;w++)
if(dist[u]+cost[u][w]<dist[w] && !flag[w])
dist[w]=dist[u]+cost[u][w];
}
}
14

void main()
{
int n,v,cost[10][10],dist[10],i,j;
clrscr();
printf("Entre the number of node:");
scanf("%d",&n);
printf("\nEntre the cost 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;
}
printf("Entre the source vertex:");
scanf("%d",&v);
dij(n,v,cost,dist);
printf("\nShortest path from\n");
for(j=1;j<=n;j++)
if(j!=v)
printf("\n%d==>%d=%d",v,j,dist[j]);

getch();
}

Output:
Enter the number of node: 5
Enter the cost matrix:
0 60 100 0 10
0 0 0 50 0
0 0 0 0 20
0 0 20 0 0
0 0 0 5 0

Enter the source vertex: 1

Shortest path from:
12=60
13=35
14=15
15=10
15

07: Sort a given list of elements using Quick sort method and determine the time required to
sort

#include<stdio.h>
#include<conio.h>
#include<time.h>

int a[10];

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

{
int i,j,k,temp;
k=a[low];
i=low+1;
j=high;
while(1)
{
while(i<high && k>=a[i])
i++;
while(k<a[j])
j--;
if(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
else
{
temp=a[low];
a[low]=a[j];
a[j]=temp;
}
return j;
}
}
16

void quicksort(int a[],int low,int high,int n)

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

void main()
{
int n,i;
clock_t st,et;
st=clock();
printf("Enter the size:");
scanf("%d",&n);
printf("Enter the element:\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
quicksort(a,0,n-1,n-1);
et=clock();
printf("The sorted array\n");
for(i=0;i<n;i++)
printf("%d\t",a[i]);
printf("\nTime taken=%f ns",(et-st)/CLOCKS_PER_SEC);

getch();
}

Output:
Enter the size: 5
Enter the elements:
10 48 86 40 56
The sorted array
10 40 48 56 86
Time taken=11.671245 ns
17

08: Find Minimum Cost Spanning Tree of a given undirected graph using Kruskal’s algorithm.

#include<stdio.h>
#include<conio.h>

int parent[10],min,n,i,no_of_edge=1,mincost=0,cost[10][10];

void main()
{
int a,u,b,v,j;
clrscr();

printf("Entre the number of node:");

scanf("%d",&n);

printf("Entre the cost 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;
}

while(no_of_edge<n)
{
for(i=1,min=99;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];
18

if(u!=v)
{
no_of_edge++;
printf("\n %d\tEdges\t(%d,%d)=%d",no_of_edge,a,b,min);
mincost+=min;
parent[v]=u;
}
cost[a][b]=cost[b][a]=999;
}

printf("\n\tMinimum cost=%d",mincost);
getch();
}

Output:
Enter the number of node: 5
Enter the cost matrix:
0 11 9 7 8
11 0 15 14 13
9 15 0 12 14
7 14 12 0 6
8 13 14 6 0

2 edges (4,5)=6
3 edges (1,4)=7
4 edges (1,3)=9
5 edges (1,2)=11

Minimum cost=33
19

09 a: Print all the nodes reachable from a given starting node in a digraph using BFS method

#include<stdio.h>
#include<conio.h>

int q[10],f=-1,r=-1;

void qins(int x)
{
if(f==-1 && r==-1)
{
f++;
q[++r]=x;
}
else
q[++r]=x;
}

int qdel()
{
int x=q[f];
if(f==r)
f=r=-1;
else
f++;

return x;
}

void main()
{
int n,i,s[10]={0},src,j,cost[10][10],u;

printf("Entre the number of vertices:");

scanf("%d",&n);
printf("Entre the adjacency matrix:\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&cost[i][j]);
20

printf("Enter the source vertex:");

scanf("%d",&src);
s[src]=1;
qins(src);

while(f!=-1 && r!=-1)

{
u=qdel();
printf("%d\t",u);

for(i=1;i<=n;i++)
if(cost[u][i]==1 && s[i]==0)
{
s[i]=1;
qins(i);
}
}

printf("\nThe nodes reachable from %d are :\n",src);

for(i=1;i<=n;i++)
if(s[i])
printf("%d\t",i);

getch();
}

Output:
Enter the number of vertices: 5
Enter the adjacency matrix
0 1 0 1 0
0 0 0 1 1
1 0 0 1 0
0 0 0 0 1
0 0 0 0 0

Enter the source vertex: 1

1 2 4 5
The nodes reachable from 1 are
1 2 4 5
21

09 b: Check whether a given graph is connected or not using DFS method

#include<stdio.h>
#include<conio.h>

void dfs(int n,int cost[10][10],int u,int s[])

{
int v;
s[u]=1;

for(v=1;v<=n;v++)
if(cost[u][v]==1 && s[v]==0)
dfs(n,cost,v,s);
}

void main()
{
int n,cost[10][10],s[10],i,j,connected,flag;

printf("Entre the number of vertices:");

scanf("%d",&n);

printf("Entre the adjacency matrix\n");

for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&cost[i][j]);

connected=0;
for(j=1;j<=n;j++)
{
for(i=1;i<=n;i++)
s[i]=0;

dfs(n,cost,j,s);
flag=0;

for(i=1;i<=n;i++)
if(s[i]==0)
flag=1;
22

if(flag==0)
connected=1;
}

if(connected==1)
printf("Graph is connected");

else
printf("graph is not connected");

getch();
}

Output:
Enter the number of vertices: 4
Enter the adjacency matrix:
0 1 1 0
1 0 1 1
1 1 0 0
0 1 0 0

Graph is connected
23

10: Find the subset of the given set S={s1,s2,…..sn} of n positive intergers whose sum is equal
to a given positive integer d

#include<stdio.h>
#include<conio.h>

int w[10],d,n,count,x[10],i;

void sum_of_subset(int s,int k,int r)

{
x[k]=1;
if(s+w[k]==d)
{
printf("\nsubset %d=",++count);
for(i=0;i<=k;i++)
if(x[i])
printf("%d\t",w[i]);
}
else if(s+w[k]+w[k+1]<=d)
sum_of_subset(s+w[k],k+1,r-w[k]);

if((s+r-w[k]>=d)&&(s+w[k+1]<=d))
{
x[k]=0;
sum_of_subset(s,k+1,r-w[k]);
}
}

void main()
{
int sum=0;
clrscr();

printf("Entre the number of element:");

scanf("%d",&n);
printf("Entre the element in ascending order\n");
for(i=0;i<n;i++)
scanf("%d",&w[i]);
24

printf("Entre the sum:");

scanf("%d",&d);

for(i=0;i<n;i++)
sum=sum+w[i];

if(sum<d || w[0]>d)
printf("No of subset possible \n");

else
sum_of_subset(0,0,sum);

getch();
}

Output:
Enter the number of element: 6
Enter the elements in ascending order
1 7 14 22 23 30

Enter the sum: 30

Subset 1= 1 7 22
2= 7 23
3= 30
25

11 a: Implement Horspool algorithm for String Matching.

#include<stdio.h>
#include<string.h>
#include<conio.h>
#define MAX 256

char pat[MAX],text[MAX],table[MAX];
int m,n,i,j,k;

void shifttable()
{
int in;
for(i=0;i<MAX;i++)
table[i]=m;
for(j=0;j<m-1;j++)
{
in=(int)pat[j]-'0';
table[in]=m-1-j;
}
}

int horspool()
{
int index;
shifttable();
i=m-1;
for(;i<=n-1;)
{
k=0;
while((k<=m-1)&&(pat[m-1-k]==text[i-k]))
k++;
if(k==m)
return i-m+1;
else
{
index=(int)text[i]-'0';
i=i+table[index];
26

}
}
return -1;
}

void main()
{
int found;
clrscr();

printf("Entre the Text:");

gets(text);

printf("Entre the Pattern:");

scanf("%s",&pat);

n=strlen(text);
m=strlen(pat);

found=horspool();

if(found==-1)
printf("Patern not found");
else
printf("patern found at %d pos",found);

getch();
}

Output:
Enter the text: welcome
Enter the pattern: come
Pattern found at 3th position
27

11 b: Find the Binomial Co-efficient using Dynamic programming

#include<stdio.h>
#include<conio.h>

void main()
{
int i,j,k,n,min,c[10][10];
clrscr();

printf("Enter the n and k values:");

scanf("%d%d",&n,&k);

for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
c[i][j]=0;

if(n>k)
{
for(i=0;i<=n;i++)
{
min=(i<j)?i:j;

for(j=0;j<=min;j++)
if(j==0 || i==j)
c[i][j]=1;

else
c[i][j]=c[i-1][j-1]+c[i-1][j];
}

printf("\nThe binomial co-efficient matrix is\n");

for(i=0;i<=n;i++)
{
for(j=0;j<=k;j++)
if(i>=j)
printf("%d\t",c[i][j]);

printf("\n");
28

printf("\nThe val of c(%d,%d)=%d",n,k,c[n-1][k-1]+c[n-1][k]);

}

else
printf("n must be greater than k");

getch();
}

Output:

Enter the value for n & k:

6 5
The Binomial Co-efficient matrix is
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6

The value for c(6,5) is 6

29

12: Find the Minimum Cost Spanning Tree of a given undirected graph using Prim’s algorithm

#include<stdio.h>
#include<conio.h>

int a,b,u,v,i,j,n,no_of_edge=1;
int visited[10],min,mincost=0,cost[10][10];

void main()
{
clrscr();

printf("Entre the number of vertices:");

scanf("%d",&n);

printf("Entre the cost 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;
}

for(i=2;i<=n;i++)
visited[i]=0;

printf("\nThe edges of spanning tree\n");

visited[1]=1;

while(no_of_edge<n)
{
for(i=1,min=999;i<=n;i++)
for(j=1;j<=n;j++)
if(cost[i][j]<min)
if(visited[i]==0)
continue;
30

else
{
min=cost[i][j];
a=u=i;
b=v=j;
}

if(visited[u]==0 || visited[v]==0)
{
no_of_edge++;
printf("\n%d\tEdge\t(%d,%d)=%d",no_of_edge,a,b,min);
mincost+=min;
visited[b]=1;
}
cost[a][b]=cost[b][a]=999;
}
printf("\n\tMinimum cost=%d",mincost);

getch();
}

Output:
Enter the number of vertices: 4
Enter the cost matrix:
0 2 9 1
2 5 1 11
7 4 1 22
11 4 7 2

The edges of spanning tree

2 Edges (1,4)=1
3 Edges (1,2)=2;
4 Edges (2,3)=1

Minimum cost=4
31
32

13 a: Implementation of Floyd’s algorithm for the All-Paris-Shortest-Paths problem

#include<stdio.h>
#include<conio.h>

int a[20][20],i,j,k,n;

floyds()
{
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(a[i][k]+a[k][j]<a[i][j])
a[i][j]=a[i][k]+a[k][j];

return 0;
}

void main()
{

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

scanf("%d",&n);

printf("Entre the weighted matrix\n");

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

floyds();

for(i=1;i<=n;i++)
a[i][i]=0;
33

printf("The required distance matrix is\n");

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

printf("\n");
}
getch();
}

Output:
Enter the number of vertices: 4
Enter the weighted matrix:
0 0 2 0
3 0 0 0
0 5 0 1
6 0 0 0

The required distance matrix is:

0 7 2 3
3 0 5 6
7 5 0 1
6 13 8 0
34

13 b: Compute the Transitive Closure of given directed graph using Warshall’s algorithm

#include<stdio.h>
#include<conio.h>

void warshall(int c[10][10],int n)

{
int i,j,k;

for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
if(c[i][k]==1)
for(j=0;j<=n;j++)
c[i][j]=c[i][j] || c[k][j];
}

void main()
{
int c[10][10],i,j,n;
clrscr();

printf("Entre the number of vertices:");

scanf("%d",&n);

printf("Entre the adjacency matrix\n");

for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&c[i][j]);

warshall(c,n);

printf("The required transitive closure is:\n");

for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d\t",c[i][j]);
printf("\n");
}
getch();
}
35
36

Output:
Enter the number of vertices: 4
Enter the adjacency matrix:
0 1 0 0
0 0 0 1
0 0 0 0
1 0 1 0

The required transitive closure is:

1 1 1 1
1 1 1 1
0 0 0 0
1 1 1 1
37

14: Implementation of N Queen problem using Back Tracking.

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

int s[50][50];

void disp(int m[],int n)

{
register int i,j;
for(i=0;i<n;i++)
s[i][m[i]]=1;

for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
if(s[i][j])
printf("Q");
else
printf("X");
printf("\n");
}
exit(1);
}

int place(int m[],int k)

{
int i;
for(i=0;i<k;i++)
if(m[i]==m[k] || (abs(m[i]-m[k])==abs(i-k)))
return 0;
return 1;
}

void main()
{
int m[25],n,k;

printf("Entre the number of Queens:");

scanf("%d",&n);
38

printf("The solution to Queen problem is\n");

n--;

for(m[0]=0,k=0;k>=0;m[k]+=1)
{
while(m[k]<=n && !place(m,k))
m[k]+=1;
if(m[k]<=n)
if(k==n)
disp(m,n+1);
else
{
k++;
m[k]=-1;
}
else
k--;
}
getch();
}

Output:
Enter the number of Queen: 4
The solution to N Queen problem is:
X Q X X
X X X Q
Q X X X
X X Q X
39

OOPS
LAB
PROGRAMS