MSC306P: ADVANCED ALGORITHM LAB MANUAL
1. Write a Program to 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>
#include<math.h>
#define l 5
int binary(int,int[],int,int,int);
int Linear(int,int[],int);
void sort(int[],int);
void display(int[],float[],int[]);
void main()
{
int a[20000],num[l],pos,res[l],op,key,n,i,s=0;
float time[l];
int ch=1;
clock_t start,end;
clrscr();
while(ch)
{
printf("[Link]\[Link]\[Link]\n");
printf("Enter your choice\n");
scanf("%d",&op);
P a g e 1 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
switch(op)
{
case 1:s=0;
while(l>s)
{
printf("Enter the number of elements\
n");
scanf("%d",&n);
num[s]=n;
for(i=0;i<n;i++)
a[i]=rand()%500;
sort(a,n);
printf("The sorted elements are\n");
for(i=0;i<n;i++)
printf("%4d\t",a[i]);
printf("Enter the search key\n");
scanf("%d",&key);
start=clock();
pos=binary(n,a,key,0,n-1);
end=clock();
time[s]=(float)(end-start)/CLK_TCK;
res[s]=pos;
s++;
}
display(num,time,res);
break;
P a g e 2 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
case 2:s=0;
while(l>s)
{
printf("Enter the number of elements\
n");
scanf("%d",&n);
num[s]=n;
for(i=0;i<n;i++)
a[i]=rand()%500;
sort(a,n);
printf("The sorted elements are\n");
for(i=0;i<n;i++)
printf("%4d\t",a[i]);
printf("Enter the search key\n");
scanf("%d",&key);
start=clock();
pos=Linear(n,a,key);
end=clock();
time[s]=(float)(end-start)/CLK_TCK;
res[s]=pos;
s++;
}
display(num,time,res);
break;
case 3:exit(0);
P a g e 3 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
break;
}
getch();
}
}
int binary(int n,int a[],int key,int low,int high)
{
int mid;
delay(30);
if(low>high)
return -1;
mid=(low+high)/2;
if(key==a[mid])
return mid+1;
else if(key<a[mid])
return binary(n,a,key,low,mid-1);
else
return binary(n,a,key,mid+1,high);
}
int Linear(int n,int a[],int key)
{
delay(10);
if(n<0)
return -1;
if(key == a[n])
P a g e 4 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
return n+1;
else
return Linear(n-1,a,key);
}
void sort(int a[],int n)
{
int i,temp,j;
for(i=0;i<=n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
}
void display(int num[],float time[],int res[])
{
int i;
printf("Input size \t time \t Position \n");
for(i=0;i<l;i++)
P a g e 5 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
{
if(res[i]==0)
printf("%d %f not found\n",num[i],time[i]);
else
printf("%d \t %f \t %d\
n",num[i],time[i],res[i]);
}
}
P a g e 6 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
2. Write a Program to Sort a given set of elements using the
Quicksort 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. The elements can be read from a
file or can be generated using the random number generator.
#include<stdio.h>
#include<conio.h>
#include<time.h>
#define l 5
int partition(int[],int,int);
void quicksort(int[],int,int);
void main()
{
int n,i,a[10000],num[l],s=0;
float time[l];
clock_t start,end;
clrscr();
while(l>s)
{
printf("Enter the number of array elements\n");
scanf("%d",&n);
num[s]=n;
for(i=0;i<n;i++)
a[i]=rand()%500;
P a g e 7 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
for(i=0;i<n;i++)
{
printf("%4d",a[i]);
}
start=clock();
quicksort(a,0,n-1);
end=clock();
printf("The sorted array is \n");
for(i=0;i<n;i++)
printf("%4d",a[i]);
time[s++]=((float)(end-start)/CLK_TCK);
}
printf("\n time \t elements \n");
for(s=0;s<l;s++)
printf("%f \t %d \t \n",time[s],num[s]);
getch();
}
int partition(int a[],int low,int high)
{
int i,j,temp,key;
key=a[low];
i=low+1;
j=high;
while(1)
{
while(i<high && key>=a[i])
P a g e 8 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
i++;
while(key<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;
}
}
}
void quicksort(int a[],int low,int high)
{
int j;
delay(2);
if(low<high)
{
j=partition(a,low,high);
quicksort(a,low,j-1);
quicksort(a,j+1,high);
P a g e 9 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
}
}
3. Write a Program to Sort a given set of elements using heap
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<dos.h>
#include<conio.h>
#include<time.h>
#define MAX 1000
#define T 3
void heapify(int a[],int n)
{
int i,j,k,item;
for(k=1;k<n;k++)
{
delay(10);
item=a[k];
i=k;
j=(i-1)/2;
while(i>0 && item>a[j])
{
delay(10);
a[i]=a[j];
i=j;
P a g e 10 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
j=(i-1)/2;
}
a[i]=item;
}
}
void adjust(int a[],int n)
{
int i,j,item;
j=0;
item=a[j];
i=2*j+1;
while(i<n)
{
delay(10);
if(i+1<n)
if(a[i]<a[i+1])
i++;
if(item<a[i])
{
a[j]=a[i];
j=i;
i=2*j+1;
}
else
break;
}
P a g e 11 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
a[j]=item;
}
void heap_sort(int a[],int n)
{
int i, temp;
heapify(a,n);
for(i=n-1;i>0;i--)
{
delay(10);
temp=a[0];
a[0]=a[i];
a[i]=temp;
adjust(a,i);
}
}
void main()
{
clock_t start, end;
int i,n,a[MAX],num[10],s=0;
float tim[10];
clrscr();
while(s<T)
{
printf("enter the no of elements\n");
scanf("%d",&n);
num[s]=n;
P a g e 12 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
printf("please wait,%d random numbers are
generating\n",n);
for(i=0;i<n;i++)
a[i]=rand()%500;
for(i=0;i<n;i++)
printf("%d \t",a[i]);
start=clock();
heap_sort(a,n);
end=clock();
printf("\nsorted array is\n");
for(i=0;i<n;i++)
printf("%d \t",a[i]);
printf("\n");
tim[s++]=(float)(end-start)/CLK_TCK;
}
clrscr();
printf("\t The time taken was:\n\n");
printf("Time Elements\n");
for(s=0;s<T;s++)
printf(" %f %d \n",tim[s],num[s]);
getch();
}
P a g e 13 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
[Link] a Program to Implement 0/1 Knapsack problem using
Dynamic Programming.
#include<stdio.h>
#include<conio.h>
int v[10][10],p[10],w[10],m,n,i,j;
void optimal_solution()
{
int i,j,x[10];
printf("\nThe optimal solution id %d\n\n",v[n][m]);
for(i=0;i<n-1;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;
if(v[i][j]==v[i-1][j])
P a g e 14 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
x[i]=0;
}
printf("The objects that are selected are shown below\
n");
for(i=1;i<=n;i++)
{
printf("x[%d]",i);
}
printf(" = ");
for(i=1;i<=n;i++)
{
printf("\t%d",x[i]);
}
}
int max(int a,int b)
{
return (a>b)?a:b;
}
void knapsack()
{
for(i=0;i<=n;i++)
{
for(j=0;i<=m;j++)
{
if(i==0||j==0)
P a g e 15 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
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]);
}
}
}
void main()
{
clrscr();
printf("Enter the number of objects\n");
scanf("%d",&n);
printf("Enter the weight of objects\n");
for(i=1;i<=n;i++)
scanf("%d",&w[i]);
printf("Enter the profits of object\n");
for(i=1;i<=n;i++)
scanf("%d",&p[i]);
printf("Enter the capacity of the knapsack\n");
scanf("%d",&m);
knapsack();
printf("The output is...\n");
for(i=0;i<=n;i++)
{
for(j=0;j<=m;j++)
printf("%d\t",v[i][j]);
P a g e 16 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
printf("\n");
}
optimal_solution();
getch();
}
5. Write a Program to 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 n,i,j,a[10][10],s[10],d[10],v,k,min,u;
clrscr();
printf("enter the numbers of vertices \n");
scanf("%d",&n);
printf("enter 999 if no edge between vertex \n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
printf("enter the starting vertices \n");
scanf("%d", &v);
for(i=1;i<=n;i++)
{
s[i]=0; d[i]=a[v][i];
}
d[v]=0;
P a g e 17 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
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];
}
}
if("the shortest displace from %d\n",v);
for(i=2;i<=n;i++)
printf("%d......>%d=%d\n",v,i,d[i]);
getch();
}
P a g e 18 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
6. Write a Program to obtain the Topological ordering of
vertices in a given digraph. Compute the transitive closure of
a given directed graph using Warshall's algorithm.
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
int n,a[10][10],indegree[10],i,j,k,p[10][10];
void find_indegree()
{
int i,j;
for(j=0;j<n;j++)
{
int s um=0;
for(i=0;i<n;i++)
{
sum+=a[i][j];
}
indegree[j]=sum;
}
}
void topological_sort()
{
P a g e 19 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
int i=0;
int u,v,t[10],s[10],k,top=-1;
find_indegree();
k=0;
for(i =0;i<n;i++)
{
if(indegree[i]==0)
{
s[++top]=i;
}
}
while(top!=-1)
{
u=s[top--];
t[k++]=u;
for(v=0;v<n;v++)
{
if(a[u][v]==1)
{
indegree[v]--;
if(indegree[v]==0)
{
s[++top]=v;
}
}
}
}
P a g e 20 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
printf("the topological sequence is \n");
for(i=0;i<n;i++)
printf("%d\t",t[i]);
}
void path_matrix()
{
int i,j,k;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
p[i][j]=a[i][j];
}
}
for(k=0;k<n;k++)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(p[i][k]==1 && p[k][j]==1)
p[i][j]=1;
}
}
}
printf("\n the path matrix(warshall's algorithm)is show
below \n");
P a g e 21 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
printf("%d\t",p[i][j]);
}
printf("\n");
}
}
void main()
{
int ch;
clrscr();
printf("enter the number of vertices\n");
scanf("%d",&n);
printf("enter the adjacency matrix \n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&a[i][j]);
}
}
while(1)
{
printf("\n [Link] sorting \n");
P a g e 22 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
printf("[Link]'s algorithm \n");
printf("[Link] \n");
printf("\n enter your choice");
scanf("%d",&ch);
switch(ch)
{
case 1:
topological_sort();
break;
case 2:
path_matrix();
break;
case 3:
exit(0);
}
}
getch();
}
P a g e 23 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
7. Write a Program to Find a subset of a given set S =
{s1,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 sumOfSub(int,int,int);
static int m=0;
int w[100];
int x[100];
void main()
{
int i=0,sum=0,n=0;
clrscr();
printf("Enter size of array: ");
scanf("%d",&n);
printf("Enter %d elements: ",n);
for(i=1;i<=n;i++)
{
scanf("%d",&w[i]);
sum+=w[i];
P a g e 24 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
x[i]=0;
}
printf("Enter the sum to be obtained: ");
scanf("%d",&m);
if(sum<m)
{
printf("Not possible to obtain any subset!!!");
exit(1);
}
printf("Possible subsets are: \n(0 indicates exclusion
and 1 indicates inclusion)\n");
sumOfSub(0,1,sum);
getch();
}
void sumOfSub(int s,int k,int r)
{
int i=0;
x[k]=1;
if(s+w[k]==m)
{
printf("\n");
printf("{");
for(i=1;i<=k;i++)
printf(" %d ",x[i]);
printf("}");
}
P a g e 25 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
else if((s+w[k]+w[k+1])<=m)
{
sumOfSub(s+w[k],k+1,r-w[k]);
}
if((s+r-w[k])>=m && (s+w[k+1])<=m)
{
x[k]=0;
sumOfSub(s,k+1,r-w[k]);
}
}
P a g e 26 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
8. Write a Program to solve the string matching problem using
Boyer-Moore approach.
#include<stdio.h>
#include<limits.h>
#include<string.h>
#define NO_OF_CHARS 256
int max (int a, int b){
return (a>b)?a:b;
}
void badCharHeuristic(char *str,int size,int
badchar[NO_OF_CHARS])
{
int i;
for(i=0;i<NO_OF_CHARS;i++)
badchar[i]=-1;
for(i=0;i<size;i++)
badchar[(int)str[i]]=i;
}
void search(char *txt,char *pat)
{
int m=strlen(pat);
int n=strlen(txt);
int badchar[NO_OF_CHARS];
int s=0;
badCharHeuristic(pat,m,badchar);
while(s<=(n-m))
P a g e 27 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
{
int j=m-1;
while(j>=0 && pat[j]==txt[s+j])
j--;
if(j<0)
{
printf("\nPattern occurs at shift = %d",s);
s+=(s+m<n)?m-badchar[txt[s+m]]:1;
}
else
s+=max(1,j-badchar[txt[s+j]]);
}
}
void main()
{
char txt[100],pat[100];
clrscr();
printf("Enter the source text\n");
gets(txt);
printf("Enter the pattern search\n");
gets(pat);
search(txt,pat);
getch();
P a g e 28 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
9. Write a Program to solve the string matching problem using
naïve approach and the KMP algorithm and compare their
Performances.
#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<stdlib.h>
void naive(char txt[100],char pat[100])
{
int n,m,i,j,count=0,shift=0;
n=strlen(txt);
m=strlen(pat);
for(i=0;i<=n-m;i++)
{
shift++;
for(j=0;j<m;j++)
{
if(txt[i+j]==pat[j])
count++;
}
if(count==m)
printf("pattern occurs with shift=%d\
n",shift);
count=0;
}
}
P a g e 29 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
int *compute_prefix(char *pat,int psize)
{
int k=-1;
int i=1;
int *pi=malloc(sizeof(int)*psize);
if(!pi)
return NULL;
pi[0]=k;
for(i=1;i<psize;i++)
{
while(k>-1 && pat[k+1]!=pat[i])
k=pi[k];
if(pat[i]==pat[k+1])
k++;
pi[i]=k;
}
return pi;
}
int kmp(char *txt,int tsize,char *pat,int psize)
{
int i;
int *pi=compute_prefix(pat,psize);
int k=-1;
if(!pi)
return -1;
P a g e 30 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
for(i=0;i<tsize;i++)
{
while(k>-1 && pat[k+1]!=txt[i])
k=pi[k];
if(txt[i]==pat[k+1])
k++;
if(k==psize-1)
{
free(pi);
return i-k;
}
}
free(pi);
return -1;
}
void main()
{
char txt[100],pat[100];
int ch,i;
clrscr();
printf("Enter the string\n");
gets(txt);
printf("Enter the pattern to match\n");
gets(pat);
while(1)
{
P a g e 31 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
printf("\[Link]\[Link]\[Link]\n");
scanf("%d",&ch);
switch(ch)
{
case 1: naive(txt,pat);
break;
case 2: i=kmp(txt,strlen(txt),pat,strlen(pat));
if(i>=0)
printf("Pattern found with shift=%d\
n",i);
else
printf("Pattren does not exist in the given
string\n");
break;
default:exit(0);
}
}
}
P a g e 32 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
10. Write a Program to implement a parallelized Merge Sort
algorithm to sort a given set of elements 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. The
elements can be read from a file or can be generated using the
random number generator (use OpenMP)
#include <stdio.h>
#include <conio.h>
//#include <omp.h>
#include<stdlib.h>
#include<time.h>
#define MAX 10000
int a[MAX],c[MAX];
int mergesort(int *,int , int);
int merge(int *, int, int, int);
void display(int n)
{
int i ;
printf("Array elements are \n");
for(i=0; i<n; i++)
{
printf("%d\t", a[i]);
}
}
P a g e 33 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
void load (int n)
{
int i,v;
for(i=0; i<n; i++)
{
v = rand()%10000;
a[i] = v;
}
}
int main()
{
int n,i;
double start,end;
clrscr();
printf("Enter the array size:\n");
scanf("%d",&n);
load(n);
display(n);
start=clock();
mergesort(a,0,n-1);
end=clock();
printf("\nAfter Sorting:\n");
display(n);
printf("\nTime taken for merge sort
%f",(end-start)/CLOCKS_PER_SEC);
printf("\n");
getch();
P a g e 34 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
return(0);
}
int mergesort(int a[], int low, int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
# pragma omp parallel sections num_threads(2)
{
#pragma omp section
{
mergesort(a,low,mid);
}
#pragma omp section
{
mergesort(a,mid+1,high);
}
}
merge(a,low,mid,high);
}
return;
}
merge(int a[], int low, int mid, int high)
P a g e 35 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
{
int i,j,k;
i=low;
j=mid+1;
k=low;
delay(20);
while((i<=mid)&&(j<=high))
{
if(a[i]<a[j])
{
c[k]=a[i];
k=k+1;
i++;
}
else
{
c[k]=a[j];
k=k+1;
j=j+1;
}
}
while(i<=mid)
{
c[k]=a[i];
k=k+1;
i=i+1;
}
P a g e 36 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
while(j<=high)
{
c[k]=a[j];
k=k+1;
j=j+1;
}
for(i=low; i<=k-1; i++)
a[i]=c[i];
return(0);
}
P a g e 37 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
12. Write a program to implement a Monte Carlo algorithm to
test the prime of a given integer and determine its
performance
#include<stdio.h>
#include<conio.h>
#include<time.h>
#include<stdlib.h>
int power(int x,int y,int p)
{
int res=1;
x=x%p;
while(y>0)
{
if(y&1)
res=(res*x)%p;
y=y>>1; //y=y/2;
x=(x*x)%p;
}
return res;
}
int miller(int d,int n)
{
int a=2+rand()%(n-4);
P a g e 38 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
int x;
x=power(a,d,n);
if(x==1||x==n-1)
return 1;
while(d!=n-1)
{
x=(x*x)%n;
d*=2; //d=d*2
if(x==1)
return 0;
if(x==n-1)
return 1;
}
return 0;
}
int isPrime(int n,int k)
{
int d,i;
if(n<=1 || n==4)
return 0;
if(n<=3)
return 1;
d=n-1;
while(d%2==0)
d/=2;
for(i=0;i<k;i++)
P a g e 39 | 40
MSC306P: ADVANCED ALGORITHM LAB MANUAL
if(!miller(d,n))
return 0;
return 1;
}
int main()
{
double st,et;
double ts;
int iteration=5;
long long num;
clrscr();
st=clock();
printf("Enter integer to test primality:\n");
scanf("%lld",&num);
if(isPrime(num,iteration))
printf("\n%lld is prime\n",num);
else
printf("\n%lld is not prime",num);
et=clock();
ts=(et-st)/CLK_TCK;
printf("\nThe time taken is %lf\n",ts);
getch();
return 0;
}
P a g e 40 | 40