Design and Analysis of Algorithms Lab Manual

1. Write a program to sort a list of N elements using selection sort technique

#include <stdio.h>
void selectionsort(int array[ ],int size)
{
int i,j,imin;
for(i=0;i<size-1;i++)
{
imin=i;
for(j=i+1;j<size;j++)
if(array[j]<array[imin];
imin=j;
int temp;
temp=array[i];
array[i]=array[imin]
array[imin]=temp;
}
}
int main()
{
int n;
n=5;
int arr[5]={12,19,55,2,16};
printf("Array before Sorting: ");
for(int i=0;i<n;i++)
printf("%d”,arr[i]);
printf("\n");
selectionSort(arr,n);
printf("Array after Sorting: ");
for(int i=0;i<n;i++)
printf("%d ",arr[i]);
printf("\n");
 Design and Analysis of Algorithms Lab Manual

2. Write a program to perform Travelling Salesman Problem

#include<stdio.h>
int tsp g[10][10]={
{12,30,33,10,45},
{56,22,9,15,18},
{29,13,8,3,12},
{33,28,16,10,3},
{,4,30,24,20}
};
int visited[10],n,cost=0;
void travellingsalesman(int c)
{
int k,adj_vertex=999;
int min=999;
visited[c]=1;
printf(“%d”,c+1);
for(k=0;k<n;k++) {
if((tsp_g[c][k]!=0)&&(visited[k]==0)) {
if(tsp_g[c][k]<min) {
min=tsp_g[c][k];
}
adj_vertex=k;
}}
if(min!=999)
{
cost=cost+min;
}
if(adj_vertex==999)
{
adj_vertex=0;
printf(“%d”,adj_vertex+1);
cost=cost+tsp_g[c][adj_vertex];
return;
}
travellingsalesman(adj_vertex);
}
int main() {
int i,j;
n=5;
for(i=0;i<n;i++) {
visited[i]=0; }
printf(“shortest path:”);
travellingssalesman(0);
printf(“\n Minimum cost:”);
printf(“%d\n”,cost);
return 0;
}
 Design and Analysis of Algorithms Lab Manual

3. Write program to implement Dynamic Programming algorithm for

the 0/1 Knapsack problem.
#include<stdio.h>
#include<string.h>
int findmax(int n1,int n2)
{
if(n1>n2)
{
return n1;
}
else
{
return n2;
}
}
int knapsack(int W,int wt[],int val[],int n)
{
int K[n+1][W+1];
for(int i=0;i<=n;i++)
{
for(int w=0;w<=W;w++)
{
if(i==0||w==0)
{
K[i][w]=0;
}
elseif(wt[i-1]<=w)
{
K[i][w]=findmax(val[i-1]+K[i-1][w-wt[i-1]],K[i-1][w]);
}
else
{
K[i][w]=K[i-1][w];
} }
}
return K[n][W];
}
int main()
{
int val[5] ={70,20,50};
int wt[5] ={11,12,13};
int W={30};
int Ten=sizeofval/sizeofval[0];
printf(“maximum profit achieved with this knapsack:%d”,knapsack(W,wt,val,len));
}
 Design and Analysis of Algorithms Lab Manual

4. Write a 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 n,i,s,ch,j;
char c,dummy;
clrscr();
printf("ENTER THE NUMBER 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("THE ADJACENCY MATRIX IS\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("\nMENU");
printf("\n1.B.F.S");
printf("\n2.D.F.S");
printf("\nENTER YOUR CHOICE");
scanf("%d",&ch);
printf("ENTER THE SOURCE VERTEX :");
scanf("%d",&s);
switch(ch)
{
case 1:bfs(s,n);
break;
case 2:
dfs(s,n);
 Design and Analysis of Algorithms Lab Manual
break;
}
printf("DO U WANT TO CONTINUE(Y/N) ? ");
scanf("%c",&dummy);
scanf("%c",&c);
}while((c=='y')||(c=='Y'));
}
//**************BFS(breadth-first search) code**************//
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
 Design and Analysis of Algorithms Lab Manual
{
k=q[front++];
return(k);
}
}
//***************DFS(depth-first search) code******************//
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("Stack overflow ");
else
stack[++top]=item;
}
int pop()
{
int k;
if(top==-1)
return(0);
else
{
k=stack[top--];
return(k);
}
}
 Design and Analysis of Algorithms Lab Manual

5. Write a Program to find the minimum and maximum value in an array using
divide and conquer

#include<stdio.h>
#include<conio.h>
void maxmin(int a[], int i, int j,int *max, int *min)
{
int mid, min1, max1;
if(i==j)
*max=*min=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(a,i,mid,max,min);
maxmin(a,mid+1,j,&max1,&min1);
if(max1>*max)
*max=max1;
if(min1<*min)
*min=min1;
}
}
void main()
{
int a[10],n,max,min,i;
clrscr();
printf("Enter total number of elements \n");
scanf("%d",&n);
printf("Enter Elements \n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
maxmin(a,0,n-1,&max,&min);
printf("max=%d\n min=%d\n",max,min);
getch();
}
 Design and Analysis of Algorithms Lab Manual

6. Write a program to implement Divide and conquer strategy. Eg: Quick Sort
algorithm for sorting list of integers in ascending order.

#include <stdio.h>
#define MAX 7
int intArray[MAX]={4,6,3,2,1,9,7};
void printline(int count)
{
int i;
for(i=0;i<count-1;i++)
{
printf(
"=");
}
printf("=\n");
}
void display()
{
int i;
printf("[");
printf(“%d”,i<MAX;i++)
{
printf("%d ",intArray[i]);
}
printf("]\n");
}

void swap(int num1,int num2)

{
int temp=intArray[num1];
intArray[num1]=intArray[num2];
intArray[num2]=temp;
}

int partition(int left,int right,int pivot)

{
int leftpointer=left-1;
while(true)
{
while(intArray[++leftpointer]<pivot){
}
while(rightpointer>0&&intArray[--rightpointer]>pivot){
}
if(leftpointer>=rightpointer){
break;
}
else{
printf(" item swapped :%d,%d\n",intArray[leftpointer],intArray[rightpointer]);
swap(leftpointer,rightpointer);
}
}
printf(" pivot swapped :%d,%d\n",intArray[leftpointer],intArray[right]);
 Design and Analysis of Algorithms Lab Manual
swap(leftpointer,right);
printf("Updated Array: ");
display();
return leftpointer;
}

void quickSort(int left,int right){

if(right-left<=0)
{
return;
}else{
int pivot= intArray[right];
int partitionPoint=partition(left,right,pivot);
quickSort(left,partition-1);
quickSort(partitionPoint+1,right);
}

}
int main()
{
printf("Input Array: ");
display();
printline(50);
quickSort(0,MAX-1);
printf("Output Array: ");
display();
printline(50);
}
 Design and Analysis of Algorithms Lab Manual

7. Write a program to implement Merge sort algorithm for sorting a list of integers
in ascending order

#include <stdio.h>
#define max 10
int a[11]={10,14,19,26,27,31,33,35,42,44,0};
int b[10];
void merging(intlow,int mid,int high)
{
int l1,l2,i;
for(l1=low,l2=mid+1,i=low;l1<=mid&&l2<=high;i++)
{
if(a[l1]<=a[l2])
b[i]=a[l1++];
else
b[i]=a[l2++];
}
while(l1<=mid)
b[i++]=a[l1++];
while(l2<=high)
b[i++]=a[l2++];
for(i=low;i<=high;i++)
a[i]=b[i];
}
void sort(int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
sort(low,high);
sort(mid+1,high);
merging(low,mid,high)
}else{
return;
}
}
int main()
{
int i;
printf("Array before sorting\n");
for(i=0;i<=max;i++)
printf("%d “.a[i]);
sort(0,max);
printf("\nArray after sorting\n");
for(i=0;i<=max;i++)
printf("%d ",a[i]);
}
 Design and Analysis of Algorithms Lab Manual

10. Write a Program to perform Knapsack Problem using Greedy Solution

#include<stdio.h>
int n = 5;
int p[10] = {3, 3, 2, 5, 1};
int w[10] = {10, 15, 10, 12, 8};
int W = 10;
void main()
{
int cur_w;
float tot_v;
int i, maxi;
int used[10];
printf("Bag Capacity = %d",W);
printf("\n Objects Available \n");
for(i=0;i< n; ++i)
printf(“%d\n”,p[i]);
printf("\n Weights Available \n");
for(i=0;i< n; ++i)
printf("%d\n",w[i]);
for (i = 0; i < n; ++i)
used[i] = 0;
cur_w = W;
while (cur_w > 0) {
maxi = -1;
for (i = 0; i < n; ++i)
if ((used[i] == 0) && ((maxi == -1) || ((float)w[i]/p[i] > (float)w[maxi]/p[maxi])))
maxi = i;
used[maxi] = 1;
cur_w -= p[maxi];
tot_v += w[maxi];
if (cur_w >= 0)
printf("Added object %d (%d, %d) completely in the bag. Space left: %d.\n", maxi + 1, w[maxi],
p[maxi], cur_w);
else {
printf("Added %d%% (%d, %d) of object %d in the bag.\n", (int)((1 + (float)cur_w/p[maxi]) * 100),
w[maxi], p[maxi], maxi + 1);
tot_v -= w[maxi];
tot_v += (1 + (float)cur_w/p[maxi]) * w[maxi]; } }
printf("Filled the bag with objects worth %.2f.\n", tot_v);
getch(); }
 Design and Analysis of Algorithms Lab Manual

13. Write a program to implement greedy algorithms for job sequencing with
deadlines

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct Jobs{
char id;// Jobs Id
int dead;// Deadline of Jobs
int profit;// Profit if Jobs is over before or on deadline
}Jobs;
int compare(const void*a,const void*b){
Jobs*temp1=(Jobs*)a;
Jobs*temp2=(Jobs*)b;
return(temp2->profit-temp1->profit);
}
int min(int num1,int num2)
{
return(num1>num2)?num2:num1;
}
int main( )
Jobs arr[]={
{'a',2,100},
{'b',2,20},
{'c',1,40},
{'d',3,35},
{'e',1,25}
};
int n=sizeof(arr)/sizeof(arr[0]);
printf("Following is maximum profit sequence of Jobs: \n");
qsort(arr,n,sizeof(Jobs),compare);
int result[n];// To store result sequence of Jobs
bool slot[n];To keep track of free time slots
// Initialize all slots to be free
for(int i=0;i<n;i++)
slot[i]=false;
for(int i=0;i<n;i++)
{
for(int j=min(n,arr[i].dead)-1;j>=0;j--){
If(slot[j]= =false)
{
result[j]=i;
slot[j]=true;
break;
}}
}
// Print the result
for(int i=0;<n;i++)
if(slot[i])
printf("%c ",arr[result[i]].id);
return 0;
}
 Design and Analysis of Algorithms Lab Manual

14. Write a program to implement Dynamic Programming algorithm for the

optimal Binary Search Tree Problem

#include<stdio.h>
#include<conio.h>
#include<limits.h>
int sum(int frq[] , int i, int j);
int optimalsearchtree(int key[], int frq[], int n);
int optcost(int frq[],int i,int j)
{
int min, r, cost, fsum,m,n,max;
if(j<i)
return 0;
if(j==i)
return frq[i];
fsum=sum(frq,i,j);
min=max;
for(r=1;r<=j;++r)
{
cost=optcost(frq,i,r-1)+optcost(frq,r+1,j);
if(cost<min)
min=cost;
}
return min+fsum;
}
int optimalsearchtree(int key[], int frq[], int n)
{
return optcost(frq,0,n-1);
}
int sum(int frq[], int i, int j)
{
int s=0,k;
for(k=i;k<=j;k++)
s=s+frq[k];
return s;
}
void main()
{
int n;
int key[]={34, 8};
int frq[]={10,12};
clrscr();
n=sizeof(key)/sizeof(key[0]);
printf("cost of optimal bst is %d",optimalsearchtree(key,frq,n));
getch();
}
 Design and Analysis of Algorithms Lab Manual

15. Write a Program that Implements Prim's algorithm to generate minimum cost
Spanning tree

#include<stdio.h>
#include<conio.h>
int prim(int t[10][2], int min);
int cost[10][10],i,j,n,ch,s,k,l,t[10][2],mincost=9999,nr[10];
int min=0;
void main()
{
clrscr();
printf("enter the no of vertices");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if((i<j)||(j<i))
{
printf("\n is there is any connection between %d & %d( enter 1 for yes,0 for no) \n",i,j);
scanf("%d",&ch);
if(ch==1)
{
printf("Enter the cost from %d & %d \n",i,j);
scanf("%d",&cost[i][j]);
}
else
{
cost[i][j]=9999;
cost[j][i]=cost[i][j];
}
}
if(i==j)
cost[i][j]=9999;
}
}
printf("The cost of adjecency Matrix is \n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%d\t",cost[i][j]);
}
printf("\n");
}
s=prim(t,min);
printf("min Spanning tree is \n");
for(i=1;i<=n-1;i++)
{
printf("\t %d \t %d \t ",t[i][1],t[i][2]);
printf("\n");
 Design and Analysis of Algorithms Lab Manual
}
printf("Min cost is =%d",s);
getch();
}
int prim(int t[10][2], int min)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(cost[i][j]<mincost)
{
mincost=cost[i][j];
k=i;
l=j;
}
}
}
min=cost[k][l];
t[1][1]=k;
t[1][2]=l;
for(i=1;i<=n;i++)
{
if(cost[i][l]<=cost[i][k])
nr[i]=l;
else
nr[i]=k;
}
nr[k]=nr[l]=0;
for(i=2;i<n-1;i++)
{
mincost=9999;
for(j=1;j<=n;j++)
{
if((nr[j]!=0)&&(mincost>=cost[j][nr[j]]))
{
mincost=cost[j][nr[j]];
k=j;
}
}
j=k;
t[i][1]=j;
t[i][2]=nr[j];
min=min+cost[j][nr[j]];
nr[j]=0;
for(k=1;k<=n;k++)
{
if((nr[k]!=0)&&((cost[k][nr[k]]>cost[k][j])))
{
nr[k]=j;
}}
}
return min;
 Design and Analysis of Algorithms Lab Manual
}

16. Write a program that implements Kruskal’s Algorithm to generate minimum

cost spanning tree

#include <stdio.h>
#include <stdlib.h>
const int inf=999999;
intk,a,b,u,v,n,ne=1;
int mincost=0;
int cost[3][3]={{0,10,20},{12,0,15},{16,18,0}};
int p[9]={0};
int applyfind(int i)
{
while(p[i]!=0)
i=p[i];
return i;
}

int applyunion(int i,int j)

{
if(i!=j)
{
p[j]=i;
return 1;
}
return 0;
}
int main()
{
n=3;
int i,j;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(cost[i][j]==0)
{
cost[i][j]=inf;
}
}
printf(“Minimum cost spanning tree:\n”);
while(ne<n)
{
int min_val=inf;
for(i=0;i<n;i++){
for(j=0;j<n;j++)
{
if(cost[i][j]<min_val)
{
min_vcal=cost[i][j];
 Design and Analysis of Algorithms Lab Manual
a=u=i;
b=v=j;
}
}

}
u=applyfind(u);
v=applyfind(v);
if(applyunion(u,v)!=0)
{
printf("%d -> %d\n",a,b);
mincost+=min_val;
}
cost[a][b]=cost[b][a]=999;
ne++;
}
printf("Minimum cost = %d",mincost);
return 0;
}