Design and Analysis of algorithm BBIT makaut

WRITE A PROGRAM FOR LINEAR SEARCH
SOURCE CODE
#include<stdio.h>
#include<conio.h>
int main()
{
int i,n,a[20];
int num,pos,f=0;
printf(” enter the number of elementsn”);
scanf(“%d”,&n);
for(i=0;i<n;i++)
{
printf(” n a[%d] =”,i);
scanf(“%d”,&a[i]);
}
printf(“n enter number to be searched”);
scanf(“%d”,&num);
for(i=0;i<n;i++)
{
if(a[i]==num)
{
f=1;
pos=i;
printf(“n %d is found at pos=%d”,num,i);
break;
}
}
if(f==0)
{
printf(“n %d does not exist in the array”);
}
getch();
}
OUTPUT
enter the number of elements
5
a[0] =5
a[1] =2
a[2] =3
a[3] =4
a[4] =9
enter number to be searched4
4 is found at pos=3
WRITE A PROGRAM FOR BINARY SEARCH
SOURCE CODE
#include<stdio.h>
#include<conio.h>
int main()
{ int i,n,a[20];
int num,pos=-1,f=0;
int b,m,e;
printf(” enter the number of elementsn”);
scanf(“%d”,&n);
for(i=0;i<n;i++)
{
printf(” n a[%d] =”,i);
scanf(“%d”,&a[i]);
}
printf(“n enter number to be searched”);
scanf(“%d”,&num);
b=0;
e=n-1;
while(b<=e)
{
m=(b+e)/2;
if(a[m]==num)
{
printf(“n %d is found at pos=%d”,num,m);
f=1;
break;
}
if(a[m]>num)
e=m-1;
else if(a[m]<num)
b=m+1;
}
if(b>e&&f==0)
printf(“n %d doesnot exist in the array”);
getch();
return 0;
}
OUTPUT
enter the number of elements 5
a[0] =2
a[1] =3
a[2] =5
a[3] =4
a[4] =1
enter number to be searched5
5 is found at pos=2
WRITE A PROGRAM TO SORT ELEMENTS USING BUBBLE SORT
SOURCE CODE
#include<stdio.h>
#include<conio.h>
int main()
{
int i,n,a[20];
int j,t;
printf(” enter the number of elementsn”);
scanf(“%d”,&n);
for(i=0;i<n;i++)
{
printf(” n a[%d] =”,i);
scanf(“%d”,&a[i]);
}
for(i=0;i<n;i++)
{
for(j=0;j<n-i-1;j++)
{
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
printf(“n the array in sorted in acsending order”);
for(i=0;i<n;i++)
{ printf(“n a[%d]=%d”,i,a[i]);
}
getch();
return 0;
}
OUTPUT
enter the number of elements
5
a[0] =26
a[1] =12
a[2] =35
a[3] =98
a[4] =2
the array in sorted in acsending order
a[0]=2
a[1]=12
a[2]=26
a[3]=35
a[4]=98
WRITE A PROGRAM TO SORT ELEMENTS USING MERGE SORT
SOURCE CODE
#include<stdio.h>
#include<conio.h>
void merge(int a[],int b,int mid,int e);
void mergesort(int a[],int b ,int e );
int main()
{
int a[10],i,n,j,k;
printf(” enter the number of elements in arrayn”);
scanf(“%d”,&n);
printf(“n enter the elements of the array”);
for(i=0;i<n;i++)
{
printf(“n a[%d]=”,i);
scanf(“%d”,&a[i]);
}
mergesort(a,0,n-1);
printf(“n the sorted array is:n”);
for(i=0;i<n;i++)
{
printf(“%dt”,a[i]);
}
getch();
return 0;
}
void merge(int a[],int b,int mid,int e)
{
int i=b,j=mid+1,index=b,t[10],k;
while((i<=mid)&&j<=e)
{ if(a[i]<a[j])
{
t[index]=a[i];
i++;
} else
{ t[index]=a[j];
j++;
} index++;
}
if(i>mid)
{ while(j<=e)
{
t[index]=a[j];
j++;
index++;
}
} else
{ while(i<=mid)
{
t[index]=a[i];
i++;
index++;
}
} for(k=b;k<index;k++)
a[k]=t[k];
}
void mergesort(int a[],int b,int e)
{
int mid;
if(b<e)
{ mid=(b+e)/2;
mergesort(a,b,mid);
mergesort(a,mid+1,e);
merge(a,b,mid,e);
}
}
OUTPUT
enter the number of elements in array
5
enter the elements of the array
a[0]=12
a[1]=5
a[2]=35
a[3]=7
a[4]=8
the sorted array is:
5 7 8 12 35
WRITE A PROGRAM TO SORT ELEMENTS USING QUICK SORT
SOURCE CODE
#include<stdio.h>
#include<conio.h>
void quicksort(int [10],int,int);
int main(){
int x[20],size,i;
printf(“Enter size of the array: “);
scanf(“%d”,&size);
printf(“Enter %d elements: “,size);
for(i=0;i<size;i++)
scanf(“%d”,&x[i]);
quicksort(x,0,size-1);
printf(“Sorted elements: “);
for(i=0;i<size;i++)
printf(” %d”,x[i]);
return 0;
}
void quicksort(int x[10],int first,int last){
int pivot,j,temp,i;
if(first<last){
pivot=first;
i=first;
j=last;
while(i<j){
while(x[i]<=x[pivot]&&i<last)
i++;
while(x[j]>x[pivot])
j–;
if(i<j){
temp=x[i];
x[i]=x[j];
x[j]=temp;
}
}
temp=x[pivot];
x[pivot]=x[j];
x[j]=temp;
quicksort(x,first,j-1);
quicksort(x,j+1,last);
}
}
OUTPUT
Enter size of the array: 5
Enter 5 elements: 3
5
6
1
2
Sorted elements: 1 2 3 5 6

Experiment no 8

Write a program to implement Activity selection

Algorithm

Activity(a,s,f):
Sort a by finish times stored f
S= {a[1]}
K=1
N=a.length
For i=2 to n
If s[i]>=f[k]
S=s u {a[i]}
K=i
Return s

Source code

#include<stdio.h>
#include<conio.h>
void activity(int s[],int f[],int n);
int main()
{
int s[20],f[20],i,j,n,t;
printf(“n enter the size of the arrayn”);
scanf(“%d”,&n);
printf(“n enter the value in starting arrayn”);
for(i=0;i<n;i++)
{
scanf(“%d”,&s[i]);
}
printf(“n enter the value in finishing arrayn”);
for(i=0;i<n;i++)
{
scanf(“%d”,&f[i]);
}
for(i=0;i<=n;i++)
{
for(j=i+1;j<=n;j++)
{
if(f[i]>f[j])
{
t=f[i];
f[i]=f[j];
f[j]=t;
t=s[i];
s[i]=s[j];
s[j]=t;
}
}
}
printf(“n the starting arrayn”);
for(i=0;i<n;i++)
{
printf(“%dt”,s[i]);
}
printf(“n the finishing arrayn”);
for(i=0;i<n;i++)
{
printf(“%dt”,f[i]);
}
activity(s,f,n);
getch();
return 0;
}
void activity(int s[],int f[],int n)
{
int i,j;
j=0;
for(i=1;i<n;i++)
{
if(s[i]>=f[j])
{
printf(” value of i =%d & t value of j=%dn”,i,j);
}
j=I;
}
}

Output:

following activities are seleceted
0 1 3 4
k

experiment no 12

Write a program to implement kruskal’s algorithm

Algorithm:

Kruskal(g,w)
A<-NULL
For each vertex v V[g]
Do MAKE-SET(v)
Sort the edges in decreasing order
For each edge(u,v)E,in decreasing order
Do if FIND SET(u)!=FIND-SET(v)
Then A<-A{(u,v)}
UNION(u,v)
Return A

Source code:

#include<stdio.h>
#include<conio.h>
int parent[9]={0};
int main()
{
int cost[9][9],mincost=0;
int i,j,n,ne=1,min,u,v,a,b;
printf(“n enter the number of nodes”);
scanf(“%d”,&n);
printf(“n the adjacency matrix is”);
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(“n the adjacency matrix isn”);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf(“%dt(%d)(%d)”,cost[i][j]
}printf(“n”);
}
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;
}
}
}
u=find(u);
v=find(v);
if(uni(u,v))
{
printf(“%d: (%d->%d) cost=%d”,ne++,a,b,min);
mincost=mincost+min;
}
cost[a][b]=cost[b][a]=999;
}
printf(“n minimum cost is =%d”,mincost);
getch();
}
int find(int i)
{
while(parent[i]!=0)
{
i=parent[i];
}
return i;
}
int uni(int i,int j)
{
if(i!=j)
{
parent[j]=i;
return 1;
}
else
return 0;
}

Output

Enter the no of vertices: 6
Enter the cost adjacency matrix
0 3 1 6 0 0
3 0 5 0 3 0
1 5 0 5 6 4
6 0 5 0 0 2
0 3 6 0 0 6
0 0 4 2 6 0
The edges of minimum cost spanning tree are
1 edge(1,3) =1
2 edge(4,6) =2
3 edge(1,2) =3
4 edge(2,5) =3
5 edge(3,6) =4
Minimum cost = 13

Experiment no 13

Write a program to impement disjoint set

Source code:

#include<stdio.h>
#include<conio.h>
int a[100];
int uni(int i,int j)
{
if(i!=j)
{
a[j]=i;
return(1);
}
return(0);
}
int find(int sc)
{
while(a[sc])
{
sc=a[sc];
}
if(sc==-1)
return(1);
else
return(0);
}
int main()
{
int i,j,k,n,x;
printf(“enter the no. of elementn”);
scanf(“%d”,&n);
// k=j;
printf(“enter the parent noden”);
for(i=0;i<n;i++)
{
scanf(“%d”,&a[i]);
}
printf(“enter the root noden”);
scanf(“%d %d”,&i,&j);
uni(i,j);
printf(“enter the number to be searchedn”);
scanf(“%d”,&x);
k=find(x);
printf(“the element %d is found in set %d”,n,k);
getch();
}

Output

enter the no of elements 6
enter the parent node
1
2
3
5
7
9
enter the root node
8
4
enter the element to be searched 5
the element is found

WRITE A PROGRAM FOR MAXIMUM & MINIMUM ELEMENT IN ARRAY
SOURCE CODE
#include<stdio.h>
#include<conio.h>
int main()
{
int i,n,a[20],l,s;
printf(” enter the number of elementsn”);
scanf(“%d”,&n);
for(i=0;i<n;i++)
{
printf(” n a[%d] =”,i);
scanf(“%d”,&a[i]);
}
l=a[0];
for(i=0;i<n;i++)
{
if(a[i]>l)
l=a[i];
}
s=a[0];
for(i=0;i<n;i++)
{
if(a[i]<l)
s=a[i];
}
printf(“n the largest of number is %d”,l);
printf(“n the smallest of number is %d”,s);
getch();
return 0;
}
OUTPUT
enter the number of elements
5
a[0] =9
a[1] =8
a[2] =25
a[3] =3
a[4] =6
the largest of number is 25
the smallest of number is 6
WRITE A PROGRAM TO FIND MAXIMUM AUR MINIMUM USING DIVIDE & CONQUER APPROACH
SOURCE CODE
#include<stdio.h>
#include<conio.h>
int a[5],max,min;
void maxmin(int i, int j)
{
int max1,min1,mid;
if(i==j)
max=min=a[j];
else if(i==j-1)
{
if(a[i]<a[j])
{
min=a[i];
max=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;
}
}
int main()
{
int f,l,i,j;
printf(“Enter the elements of arrayn”);
for(i=0;i<5;i++)
{
printf(“Enter a[%d]”,i);
scanf(“%d”,&a[i]);
}
max=min=a[0];
maxmin(0,9);
printf(“The maximum and minimum no is:%d %d”,max,min);
}
OUTPUT
Enter the elements of array
Enter a[0]=36
Enter a[1]=89
Enter a[2]=8
Enter a[3]=7
Enter a[4]=25
The maximum and minimum no is: 89 7
WRITE A PROGRAM TO SOLVE KNAPSACK PROBLEM USING GREEDY ALGORITHM
SOURCE CODE
#include<stdio.h>
#include<conio.h>
int main()
{
int i,j,n,t,temp;
float p[30],w[30],r[30],x[30],u;
printf(“n enter the number of items”);
scanf(“%d”,&n);
printf(“n enter the number of profits”);
for(i=0;i<n;i++)
{
scanf(“%f”,&p[i]);
}
printf(“n enter the weight”);
for(i=0;i<n;i++)
{
scanf(“%f”,&w[i]);
}
printf(“n enter the capacity”);
scanf(“%f”,&u);
printf(“n the calculated pi/wi ratio”);
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])
{
t=r[i];
r[i]=r[j];
r[j]=t;
t=p[i];
p[i]=p[j];
p[j]=t;
t=w[i];
w[i]=w[j];
w[j]=t;
}
}
}
printf(“the sorted ratio array is “);
for(i=0;i<n;i++)
{
printf(” %dt%3.2fn”,i,r[i]);
}
printf(“the sorted profit array is “);
for(i=0;i<n;i++)
{
printf(” %dt%3.2fn”,i,p[i]);
}
printf(“the sorted weight array is “);
for(i=0;i<n;i++)
{
printf(” %dt%3.2fn”,i,w[i]);
}
for(i=0;i<n;i++)
{
x[i]=0.0;
}
for(i=0;i<n;i++)
{
if (u>w[i])
{
x[i]=1.0;
u=u-w[i];
// printf(“%f”,u);
}
else
{
break;
}
}
x[i]=u/w[i];
printf(“the knapsack array “);
for(i=0;i<n;i++)
{
printf(” %dt%3.2fn”,i,x[i]);
}
getch();
return 0;}
OUTPUT
enter the number of items6
enter the number of profits200
50
100
80
48
64
enter the weight
5
10
10
10
24
4
enter the capacity 35
the calculated pi/wi ratio the sorted ratio array is
0 40.00
1 16.00
2 10.00
3 8.00
4 5.00
5 2.00
the sorted profit array is
0 200.00
1 64.00
2 100.00
3 80.00
4 50.00
5 48.00
the sorted weight array is
0 5.00
1 4.00
2 10.00
3 10.00
4 10.00
5 24.00
the knapsack array
0 1.00
1 1.00
2 1.00
3 1.00
4 0.60
5 0.00

Leave a Comment

Your email address will not be published. Required fields are marked *

To Resolve this issue at just 5$ from ServerExpert

https://serverexpert.io/

For Hosting please visit Hostingwebsite.io

You have Successfully Subscribed!

Open chat