Algorithms

Laboratory
Manual[Sub Code:07MCA48]

Department Of MCA

Malnad College of Engineering

1. Implement Recursive Binary search and linear search and determine the
time required to search an element. Repeat the experiment for different
values of n, the number of elements in the list to be searched and plot a
graph of the time taken versus n.

#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);
 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
2. Sort a given set of elements using the Heapsort method and determine the
time required to sort the elements. Repeat the experiment for different
values of n, the number of elements in the list to be sorted and plot a graph
of the time taken versus n.
#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++;
}

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]);
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
3. Sort a given set of elements using Merge sort method and determine the
time required to sort the elements. Repeat the experiment for different
values of n, the number of elements in the list to be sorted and plot a graph
of the time taken versus n.

#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);
}
}
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
4. Sort a given set of elements using Selection sort and determine the time
required to sort elements. Repeat the experiment for different values of n,
the number of elements in the list to be sorted and plot a graph of the time
taken versus n.

#include<stdio.h>
#include<conio.h>
#include<time.h>
void selection_sort(int a[],int n)
{
int i,j,small,pos,temp;
for(i=0;i<n-1;i++)
{
small=a[i];
pos=i;
for(j=i+1;j<n;j++)
{
if(a[j]<small)
{
small=a[j];
pos=j;
}
}
temp=a[i];
a[i]=a[pos];
a[pos]=temp;
}
}
int main()
{
int i, n, a[20];
clock_t st, end;
clrscr();
st=clock();
printf("Enter the no of elements: ");
scanf("%d",&n);
printf("Enter the elements: \n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
selection_sort(a,n);
end=clock();
printf(“The sorted elements are :\n”);
for(i=0;i<n;i++)
printf("%d\t\n",a[i]);
 printf("Time taken required is %f\n",(end-st)/CLK_TCK);
getch();
}

Output:

Enter the no of elements: 5

Enter the elements:

53618

The sorted elements are

13568

Time taken is 16.868132

5. Implement 0/1 Knapsack problem using dynamic programming
#include<stdio.h>
#include<conio.h>

int max(int a,int b)

{
return a>b?a:b;
}

void knapsack(int n,int w[],int m,int p[])

{
int i,j,v[10][10],x[10];
for(i=0; i<=n; i++)
{
for(j=0; j<=m; j++)
{
if(i==0 || j==0)
v[i][j]=0;
else if(j<w[i])
v[i][j]=v[i-1][j];
else
v[i][j]=max(v[i-1][j],v[i-1][j-w[i]]+p[i]);
}
}
printf("The output is\n");
for(i=0; i<=n; i++)
{
for(j=0; j<=m; j++)
printf("%d\t",v[i][j]);
printf("\n");
}
printf("The optimal solution is %d\n",v[n][m]);
for(i=0; i<=n; i++)
{
x[i]=0, i=n, j=m;
while(i!=0 && j!=0)
{
if(v[i][j]!=v[i-1][j])
{
x[i]=1, j=j-w[i];
}
i=i-1;
}
for(i=1; i<=n; i++)
 printf("x[%d] ",i);
printf("=");
for(i=1; i<=n; i++)
printf("%d ",x[i]);
}}

void main()
{
int m,i,j,n,w[10],p[10],v[10][10];
clrscr();
printf("Enter the no.of objects\n");
scanf("%d",&n);
printf("Enter the weights of n objects\n");
for(i=1; i<=n; i++)
scanf("%d",&w[i]);
printf("Enter the profit of n objects\n");
for(i=1; i<=n; i++)
scanf("%d",&p[i]);
printf("Enter the capacity of knapsack\n");
scanf("%d",&m);
knapsack(n,w,m,p);
getch();
}

OUTPUT
Enter the no.of objects
5
Enter the weights of n objects
32145
Enter the profit of n objects
25 20 15 40 50
Enter the capacity of knapsack
6
The output is
0 0 0 0 0 0 0
0 0 0 25 25 25 25
0 0 20 25 25 45 45
0 15 20 35 40 45 60
0 15 20 35 40 55 60
0 15 20 35 40 55 65
The optimal solution is 65
x[1] x[2] x[3] x[4] x[5] =0 0 1 0 1
6. 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 main()
{
int i,j,a[10][10],s[10],d[10],k,min,u,v,n;
clrscr();
printf("Enter the no of vertices\n");
scanf("%d",&n);
printf("Enter the cost adjacency matrix\n");
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
scanf("%d",&a[i][j]);
}
printf("Enter the source matrix\n");
scanf("%d",&v);
for(i=1; i<=n; i++)
{
s[i]=0, d[i]=a[v][i];
}
d[v]=0, s[v]=1;
for(k=2; k<=n; k++)
{
min=999;
for(i=1; i<=n; i++)
if(s[i]==0 && d[i]<min)
{
min=d[i], u=i;
}
s[u]=1;
for(i=1; i<=n; i++)
if(s[i]==0)
{
if(d[i]>(d[u]+a[u][i]))
d[i]=d[u]+a[u][i];
}
}
printf("The shortest distance from %d is \n",v);
for(i=1; i<=n; i++)
printf("%d--->%d=%d\n",v,i,d[i]);
getch();
}
OUTPUT
Enter the no of vertices
5
Enter the cost adjacency matrix
999 3 999 7 999
3 999 999 5 6
7 2 5 999 4
999 999 6 4 999
999 7 999 3 999
Enter the source matrix
1
The shortest distance from 1 is
1--->1=0
1--->2=3
1--->3=13
1--->4=7
1--->5=9
7. Sort a given set of elements using Quick sort method and determine the
time required sort the elements. Repeat the experiment for different values
of n, the number of elements in the list to be sorted and plot a graph of the
time taken versus n.
#include<stdio.h>
#include<conio.h>
#include<time.h>
#include<dos.h>

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

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

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

{
int pivot,i,j,temp;
pivot=a[low];
i=low;
j=high+1;
delay(1000);
while(i<j)
{
do
{
i++;
}
while(pivot>=a[i]);
do
{
j--;
}
while(pivot<a[j]);
if(i<j)
{
temp=a[j];
a[i]=a[j];
a[j]=temp;
}
}
a[low]=a[j];
a[j]=pivot;
return j;
}

void main()
{
int i,a[100],n,low,high;clock_t st,end;
clrscr();
printf("Enter no.of elements\n");
scanf("%d",&n);
printf("Enter the array elements\n");
for(i=0; i<n; i++)
scanf("%d",&a[i]);
low=0;
high=n-1;
delay(1000);
st=clock();
quicksort(a,low,high);
end=clock();
printf("Sorted array is\n");
for(i=0; i<n; i++)
printf("%d\n",a[i]);
printf("The time required is %f\n",(end-st)/CLK_TCK);
getch();
}
OUTPUT
Enter no.of elements
5
Enter the array elements
33 11 22 55 44
Sorted array is
11
22
33
44
55
The time required is 2.967033
8. 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];
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
9 a. Print all the nodes reachable from a given starting node in a digraph
using BFS
method.

b. Check whether a given graph is connected or not using DFS

method.
#include<conio.h>
#include<stdio.h>
int a[20][20], q[20], visited[20], n, i,j,f=0,r=-1,t;
void bfs(int v)
{
for(i=1;i<=n;i++)
if(a[v][i]&&!visited[i])
q[++r]=i;
if(f<=r)
visited[q[f]]=1, bfs(q[f++]);
}
void main()
{
int v;
printf("Enter the number of vertices: ");
scanf("%d",&n);
for(i=1;i<=n;i++)
q[i]=0,visited[i]=0;
printf("Enter the graph data in the matrix form:\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
printf("Enter the starting vertex: ");
scanf("%d",&v);
bfs(v);
printf("The nodes which are reachable are:\n");
for(i=1;i<=n;i++)
{
if(visited[i])
printf("%d\n",i);
}
}

/*
Output:
Enter the number of vertices: 5
Enter the graph data in the matrix form:
01010
00011
10010
00001
00000
Enter the starting vertex: 1
The nodes which are reachable are:
2
4
5

b.

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

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
10. Find a subset of a given set S = {sl, s2,.....,sn} of n positive integers
whose sum is equal to a given positive integer d. For example, if S= {1, 2, 5,
6, 8} and d = 9 there are two solutions{1,2,6}and{1,8}.A suitable message is
to be displayed if the given problem instance doesn't have a solution.
#include<stdio.h>
#include<conio.h>

void subset(int n,int d,int w[])

{
int i,k,s,x[10];
for(i=1; i<=n; i++)
x[i]=0, s=0, k=1, x[k]=1;
while(1)
{
if(k<=n && x[k]==1)
{
if(s+w[k]==d)
{
printf("Solution is\n");
for(i=1; i<=n; i++)
{
if(x[i]==1)
printf("%d",w[i]);
}
printf("\n");
x[k]=0;
}
else if(s+w[k]<d)
{
s+=w[k];
}
else
{
x[k]=0;
}}
else
{
k--;
while(k>0 && x[k]==0)
{
k--;
}
if(k==0) break;
x[k]=0;
s=s-w[k];
}
k=k+1;
x[k]=1;
}
}
void main()
{
int d,i,n,w[10];
clrscr();
printf("Enter the value of n\n");
scanf("%d",&n);
printf("Enter the set in increasing order\n");
for(i=1; i<=n; i++)
scanf("%d",&w[i]);
printf("Enter the maximum subset value of d\n");
scanf("%d",&d);
subset(n,d,w);
getch();
}
OUTPUT
Enter the value of n
5
Enter the set in increasing order
12345
Enter the maximum subset value of d
9
Solution is
135
Solution is
234
Solution is
45
11. a. Implement Horspool algorithm for String Matching.

b. Find the Binomial Co-efficient using Dynamic Programming.

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

void shift_table(char p[],int t[])

{
int i,m;
m=strlen(p);
for(i=0; i<128; i++)
t[i]=m;
for(i=0; i<=m-2; i++)
t[p[i]]=m-1-i;
}

int horspool(char p[],char t[])

{
int i,k,m,n,s[256];
shift_table(p,s);
m=strlen(p);
n=strlen(t);
i=m-1;
while(i<=n-1)
{
k=0;
while(k<=m-1 && t[i-k]==p[m-1-k])
{
k=k+1;
}
if(k==m)
return i-m+1;
i=i+s[t[i]];
}
return -1;
}

void main()
{
char p[20],t[40];
int pos;
clrscr();
printf("Enter the text string\n");
scanf("%s",&t);
printf("Enter the pattern string\n");
scanf("%s",&p);
pos=horspool(p,t);
if(pos==-1)
printf("Pattern string not found\n");
else
printf("Pattern string found at %dth position\n",pos+1);
getch();
}
OUTPUT

11.Enter the text string

raghuvansham
Enter the pattern string
vansham
Pattern string found at 6th position

12.Enter the text string

raghuvanham
Enter the pattern string
vasham
Pattern string not found
b.

#include<stdio.h>
#include<conio.h>
void main()
{
int n,k,i,j,min,c[10][10];
printf("Enter the size of n and k\n");
scanf("%d %d",&n,&k);
for(i=0;i<n;i++)
for(j=0;j<k;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("The binomial coefficient matrix form:\n");
for(i=0;i<n;i++)
{
for(j=0;j<k;j++)
if(i>=j)
printf("%d ",c[i][j]);
printf("\n");
}
}
else
printf("n must be greater than k\n");
}
/* Output:
Enter the size of n and k
54
The binomial coefficient matrix form:
1
11
121
1331
1464
12. Find 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,n,j,ne=1;
int vis[10],min,mincost=0,cost[10][10];
void main()
{
printf("Enter the no of vertices and graph data\n");
scanf("%d",&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++)
vis[i]=0;
printf("The edges of spanning tree are\n");
vis[1]=1;
while(ne<n)
{
for(i=1,min=999;i<=n;i++)
for(j=1;j<=n;j++)
if(cost[i][j]<min)
if(vis[i]==0)
continue;
else
{
min=cost[i][j];
a=u=i,b=v=j;
}
if(vis[u]==0||vis[v]==0)
{
printf("%d\t edge\t (%d, %d)=%d\n",ne++,a,b,min);
mincost+=min;
vis[b]=1;
}
cost[a][b]=cost[b][a]=999;
}
printf("\n\t MINCOST=%d\n",mincost);
}
Output:
Enter the no of vertices and graph data
7
00 28 00 00 00 10 00
28 00 16 00 00 00 14
00 16 00 12 00 00 00
00 00 12 00 22 00 18
00 00 00 22 00 25 24
10 00 00 00 25 00 00
00 14 00 18 24 00 00
The edges of spanning tree are
1 Edge (1,6) = 10
2 Edge (6,5) = 25
3 Edge (5,4) = 22
4 Edge (4,3) = 12
5 Edge (3,2) = 16
6 Edge (2,7) = 14

MINCOST=99
13. a. Implement Floyd’s algorithm for the All-Pairs- Shortest-Paths problem.
b. Compute the transitive closure of a given directed graph using Warshall’s
algorithm.

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

B.

#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();
}

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
14. Implement N Queen's 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);

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