1.

Search for a key st=clock();

element using linear printf(" Start time is %f",
search method with the (float)st);
help .......Plot a graph of for(i=0;i<n;i++)
time taken versus n. {
if(a[i]==element)
#include<stdio.h> {
#include<conio.h> printf("search is
#include<time.h> successful\n");
int main() printf("Element %d found
{ at location %d",element,i);
int found=1;
a[10000],i,found=0,eleme break;
nt,n; }
clock_t st,et; }
float ts; if(!found)
printf("Enter array {printf("Element %d not
size\n"); found\n",element);
scanf("%d",&n); }
printf("Random array et=clock();
elements are\n"); printf(" end time is %f",
for(i=0;i<n;i++) (float)et);
{ ts=(float)(et-
a[i]=rand(); st)/CLOCKS_PER_SEC;
printf("%d\t", a[i]); printf("The time taken is
} %f", ts);
printf("\nEnter element to getch();
be searched"); return 0;
scanf("%d",&element); }
2. Implement binary printf("Enter %d elements
search algorithm using in ascending order\n",n);
recursive and non- for(i=0;i<n;i++)
recursive approach. scanf("%d",&a[i]);
Analyze its time printf("Enter key element
complexity. to be searched : ");
scanf("%d",&key);
#include<stdio.h> low=0;
#include<stdlib.h> high=n-1;
void Rbinsearch(int printf("*******************
[],int,int,int); ***************************
void Ibinsearch(int [], ******\n");
int,int,int); printf("\[Link] search
int a[100],i, using recursion \n2.
n,low,high,key,mid,found= Binary search without
0; recursion
void main() (Iteration) [Link]\n");
{ printf("Enter your
int choice; choice\n");
printf(" Recursive and scanf("%d",&choice);
Non Recursive switch(choice)
implementation of Binary {
Search Algorithm\n"); case
printf("\n***************** 1:Rbinsearch(a,low,high,ke
*************************** y);
*\n"); break;
printf("Enter input case
size\n"); 2:Ibinsearch(a,low,high,ke
scanf("%d",&n); y);
break; }
case 3:return; if(!found)
default:printf("Invalid printf("Element %d not
Choice\n"); found\n", key);
} }
} void Ibinsearch( int a[], int
void Rbinsearch( int a[], int low, int high, int key)
low, int high, int key){ {
while(low<=high) while(low<=high)
{ {
mid=(low+high)/2 ; mid=(low+high)/2 ;
if(key<a[mid]) if(a[mid]==key)
{ {
return Rbinsearch(a,low,mid- printf(" Search is
1,key); successful\n");
} printf("key element %d
else if(key>a[mid]) found at location
{ %d",key,mid);
return found=1;
Rbinsearch(a,mid+1,high,key); break;
} }
else else if(key<a[mid])
{ high=mid-1;
printf(" Search is else
successful\n"); low=mid+1;
printf("key element %d }
found at location if(!found)
%d",key,mid); printf("Element %d not
found=1; found\n", key);
break; }
}
4. Write a C program to
implement merge sort {
algorithm using divide and int mid;
conquer approach. Analyze if(low<high)
its time complexity. {
mid=(low+high)/2;
mergesort(a,low,mid);
#include<stdio.h>
mergesort(a,mid+1,high);
#include<conio.h>
merge(a,low,mid,high);
void mergesort(int
}
a[],int,int);
}
void merge(int a[],int,int,int); void merge(int a[],int low,int
int main() mid,int high)
{ {
int a[100],n,i; int c[100],i,j,k;
printf(" Enter array size\n"); i=low;
scanf("%d",&n); j=mid+1;
printf("Enter array k=low;
elements\n"); while(i<=mid && j<=high)
for(i=0;i<n;i++) {
scanf("%d",&a[i]); if(a[i]<=a[j])c[k++]=a[i++];
mergesort(a,0,n-1); else
printf("sorted elements c[k++]=a[j++];
are\n"); }
while(i<=mid)
for(i=0;i<n;i++)
c[k++]=a[i++];
printf("%d\t",a[i]);
while(j<=high)
return 0;
c[k++]=a[j++];
}
for(i=low;i<=high;i++)
void mergesort(int a[],int
a[i]=c[i];
low,int high) }
3. Write a C program to j=j-1;
implement quick sort if(i<j)
algorithm using divide and Exch(&a[i], &a[j]);
conquer }
approach. Analyze its time Exch(&a[j], &a[pivot]);
complexity. QuickSort(a, low, j);
QuickSort(a, j+1, high);
# include <stdio.h> }
# include <conio.h> void main()
void Exch(int *p, int *q) {
{ int n, a[1000],i;
int temp = *p; printf("\n Enter the array
*p = *q; size\n");
*q = temp; scanf("%d", &n);
} printf("Enter array
void QuickSort(int a[], int elements\n");
low, int high) for(i=0;i<=n-1;i++)
{ scanf("%d",&a[i]);
int i, j,pivot, k; QuickSort(a, 0, n);
if(low>=high) printf("\nSorted Numbers
return; are: \n ");
pivot=low; for(i=1; i<=n; i++)
i=low; printf("%d\t", a[i]);
j=high; getch();}
while(i<=j)
{
while ( a[i] <= a[pivot] )
i=i+1;
while ( a[j] > a[pivot] )
5. Write a C program to find for(j=1;j<=n;j++)
Minimum Cost Spanning tree if(cost[i][j]<min)
of a given undirected graph if(visited[i]!=0)
using Prim’s algorithm. {
min=cost[i][j];
#include<stdio.h> u=i;
#include<conio.h> v=j;
int u,v,n,i,j,ne=1,visited[10]= }
{0},min,mincost=0,cost[10] if(visited[u]==0 ||
[10]; visited[v]==0)
void main() {
{ printf("\n Edge %d:(%d %d)
printf("\n Enter the number cost:%d",ne++,u,v,min);
of nodes:"); mincost+=min;
scanf("%d",&n); visited[v]=1;
printf("\n Enter the }
adjacency matrix:\n"); cost[u][v]=cost[v][u]=999;
for(i=1;i<=n;i++) }
for(j=1;j<=n;j++) printf("\n Minimun
{ cost=%d",mincost);
scanf("%d",&cost[i][j]); getch();
if(cost[i][j]==0) }
cost[i][j]=999;
}
visited[1]=1;
printf("\n");
while(ne<n)
{
for(i=1,min=999;i<=n;i++)
6. Write a C program to sort }
the numbers in ascending void heapsort(int a[],int n)
order using heap sort. {
int i;
#include<stdio.h> for(i=n/2-1;i>=0;i--)
void swap( int *a, int *b) heapify(a,n,i);
{ for(i=n-1;i>=0;i--)
int temp=*a; {
*a=*b; swap(&a[0],&a[i]);
*b=temp; heapify(a,i,0);
} }
void heapify( int a[],int n, int }
i) void main()
{ {
int largest=i; int a[100],n,i;
int left=2*i+1; printf(" Enter array size\n");
int right=2*i+2; scanf("%d", &n);
if( left < n && a[left] > printf("Enter array
a[largest]) elements\n");
largest=left; for(i=0;i<n;i++)
if(right < n && a[right] > scanf("%d", &a[i]);
a[largest]) heapsort(a, n);
largest=right; printf("sorted elements
if( largest!=i) are\n");
{ for(i=0;i<n;i++)
swap(&a[i],&a[largest]); printf("%d\t", a[i]);
heapify(a,n,largest); }
}
7. Write a C program to for(i=0;i<n;i++)
compute the transitive for(j=0;j<n;j++)
closure of a given directed scanf("%d",&a[i][j]);
graph using path();
Warshall's algorithm. printf("\nThe path matrix is
showm below\n");
# include <stdio.h> for(i=0;i<n;i++)
int n,a[10][10],p[10][10]; {
void path() for(j=0;j<n;j++)
{ printf("%d ",p[i][j]);
int i,j,k; printf("\n");
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;
}
void main()
{
int i,j;
printf("Enter the number of
nodes:");
scanf("%d",&n);
printf("\nEnter the
adjacency matrix:\n");