ADVANCED DATA STRUCTURES AND

ALGORITHMS LAB PROGRAMS

-(For internal on 16/10/2024)

1.Binary Search :-
#include<stdio.h>
void Bsearch(int A[],int s,int e,int ele);
int main()
{
int i,s,e,n;
printf("Enter the size of array : ");
scanf("%d",&n);
int A[n];
printf("Enter the array : ");
for(i=0;i<n;i++)
{scanf("%d",&A[i]);}
printf("Enter the element to search : ");
int ele;
scanf("%d",&ele);
s=0,e=n-1;
Bsearch(A,s,e,ele);
return 0;
}
void Bsearch(int A[],int s,int e,int ele)
{
if(s==e)
{
if(A[s]==ele)
{
 printf("Element found at index %d.\n",e);
}
else
{
printf("Element not found.\n");
}
}
int mid = (s+e)/2;
if(ele<A[mid])
{
Bsearch(A,s,mid,ele);
}
else
{
Bsearch(A,mid+1,e,ele);
}
}

2.Merge Sort :-
#include<stdio.h>
int n;
void Merge(int a[],int S,int M,int E)
{
int b[n];
int i=S,j=M+1,k=S,x;

while(i<=M && j<=E)

{
if(a[i]<a[j]){b[k]=a[i];
i++;
 }
else
{
b[k]=a[j];
j++;
}
k++;
}
if(i>M)
{
for(x=j;x<=E;x++)
{
b[k]=a[x];
k++;
}
}
else{
for(x=i;x<=M;x++)
{
b[k]=a[x];
k++;
}
}
for(x=S;x<=E;x++){a[x]=b[x];}
}
void MergeSort(int a[],int S,int E){
if(S<E){ int M = (S+E)/2;
MergeSort(a,S,M);
MergeSort(a,M+1,E);
Merge(a,S,M,E);
}}

int main(){
int i;
printf("Enter the size of array : ");
scanf("%d",&n);
int a[n];
printf("Enter the array elements : ");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
printf("Original array: ");
for(i=0;i<n;i++){printf("%d ",a[i]);}
MergeSort(a,0,n-1);
printf("\nSorted array: ");
for(i=0;i<n;i++){printf("%d ",a[i]);}
}

3.Quick Sort :-
#include<stdio.h>
int n;
int swap(int *x,int *y)
{ int temp=*x;
*x=*y;
*y=temp;}
int partition(int a[],int S,int E)
{
int p=a[S];
 int i=S,j=E;
while(i<j)
{while(a[i]<=p && i<=E){i++;}

while(a[j]>p && j>=S){j--;}

if(i<j){swap(&a[i],&a[j]);}
}
swap(&a[S],&a[j]);
return j;
}
void QuickSort(int a[],int S,int E)
{
if(S<E){
int j=partition(a,S,E);
QuickSort(a,S,j-1);
QuickSort(a,j+1,E);
}
}
int main(){
int i;
printf("Enter the size of array : ");
scanf("%d",&n);
int a[n];
printf("Enter the array elements : ");
for(i=0;i<n;i++)
{scanf("%d",&a[i]);}
printf("Original array: ");
for(i=0;i<n;i++){printf("%d ",a[i]);}
QuickSort(a,0,n-1);
printf("\nSorted array: ");
 for(i=0;i<n;i++){printf("%d ",a[i]);}}

4.Min-max :-
#include<stdio.h>
int min,max;
void minmax(int a[],int S,int E)
{
if(S==E)
{
min=max=a[S];
}
else if(S==E-1)
{
min=a[S]<a[E]?a[S]:a[E];
max=a[S]>a[E]?a[S]:a[E];
}
else
{
int M=(S+E)/2;
minmax(a,S,M);
int min1=min;
int max1=max;
minmax(a,M+1,E);
if(min1<min)
{
min=min1;
}
if(max<max1)
{
max=max1;
}
 }
}
void main()
{
int n,i;
printf("Enter the size of array : ");
scanf("%d",&n);
int a[n];
printf("Enter the array elements : ");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
minmax(a,0,n-1);
printf("Minimum in the array is %d.\nMaximum in the array is %d.\n",min,max);
}

5.Fractional Knapsack problem :-

#include<stdio.h>
struct objects{
int weight;
float value;
};
void fractionalKnapsack(struct objects items[],int n,int capacity);
void main()
{
int i;
printf("\t\t\t\t\t\t\t\tKnapsack Problem \n");
printf("Enter the bag capacity : ");
int capacity;
 scanf("%d",&capacity);
printf("\nEnter the number of objects : ");
int n;
scanf("%d",&n);
struct objects items[n];
for(i=0;i<n;i++)
{
printf("\nEnter the weight of object %d : ",i+1);
scanf("%d",&items[i].weight);
printf("Enter the value of the object : ");
scanf("%f",&items[i].value);
}
fractionalKnapsack(items,n,capacity);
}

void fractionalKnapsack(struct objects items[],int n,int capacity)

{
int i;
float totalValue=0.0;
int used[n];
float weights[n];
for(i=0;i<n;i++) {
used[i]=0;
weights[i]=0.0;}
int remainingCapacity=capacity;
while(remainingCapacity>0)
{
int bestIndex=-1;
float bestRatio=0.0;
for(i=0;i<n;i++)
 {
if(used[i]==0)
{
float ratio=items[i].value/items[i].weight;
if(ratio>bestRatio)
{
bestRatio=ratio;
bestIndex=i;
}
}
}
if(bestIndex==-1){break;}
used[bestIndex]=1;
if(items[bestIndex].weight<=remainingCapacity)
{
totalValue+=items[bestIndex].value;
remainingCapacity-=items[bestIndex].weight;
weights[bestIndex]=items[bestIndex].weight;
}
else
{

totalValue+=items[bestIndex].value*((float)remainingCapacity/items[bestIndex].weight);
weights[bestIndex]=remainingCapacity;
remainingCapacity=0;
}
}
printf("The selected weights are :\n");
for(i=0;i<n;i++)
{
printf("obj %d :- %.2f ",i+1,weights[i]);
 }
printf("\nThe maximum profit is %.2f\n",totalValue);
}

6.All Pairs Shortest Path :-

#include<stdio.h>
int n,i,j,k;
void APSP(int cost[n][n],int n);
int min(int a ,int b);
int main()
{
printf("Enter the size of Graph : ");
scanf("%d",&n);
int cost[n][n];
printf("Enter the graph weights : \n");
for(i=0;i<n;i++){
for(j=0;j<n;j++){
scanf("%d",&cost[i][j]);
}
}
APSP(cost,n);
}
void APSP(int cost[n][n],int n)
{
int A[n][n];
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
A[i][j]=cost[i][j];
 }
}
for(k=0;k<n;k++)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
A[i][j]=min(A[i][j],A[i][k]+A[k][j]);
}
}
}
printf("The All pairs shortest path of the given graph is :\n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
printf("%d ",A[i][j]);
}
printf("\n");
}
}
int min(int a,int b)
{
if(a<b)
{return a;}
else
{return b;}
}
7.Prim’s Algorithm :-
#include<stdio.h>
#include<stdlib.h>

void prims(int n,int cost[n][n])

{
int st[n-1][2];
int i,j,u,v,min,min_cost=0,visited[n],ne=1;
for(i=0;i<n;i++)
{
visited[i]=0;
}
int z=0;
visited[0]=1;
while(ne<n)
{
min=999;
for(i=0;i<n;i++)
{
if(visited[i]){
for(j=0;j<n;j++)
{
if(!visited[j]&&cost[i][j]<min)
{
min=cost[i][j];
u=i,v=j;
}
}
 }
}
if(visited[u]==0||visited[v]==0)
{
st[z][0]=u+1;
st[z][1]=v+1;
z++;
ne++;
min_cost+=min;
visited[v]=1;
}
cost[u][v]=cost[v][u]=999;
}
printf("\nThe edges considered for MST are :\n");
for(i=0;i<n-1;i++)
{
printf("%d--%d\n",st[i][0],st[i][1]);
}
printf("\nCost of constructing MST is %d ",min_cost);
}
int main()
{
int i,j,n;
printf("Enter the number of vertices : ");
scanf("%d",&n);
int cost[n][n];
printf("Enter Graph wieghts:\n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
 {
scanf("%d",&cost[i][j]);
if(cost[i][j]==0){ cost[i][j]=999;}
}
}
int st[n-1][2];
prims(n,cost);
return 0;
}

NOTE :-
Remaining programs :-
1.Kruskal’s Algorithm
2.Strassian’s Matrix multiplication.