#include<stdio.h>
void bins(int lb,int ub,int item,int a[]);
void main()
{
int i,n,item,a[20];
printf("Enter the size of an array: ");
scanf("%d",&n);
printf("Enter the elements of the array: " );
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
printf("Enter the number to be search: ");
scanf("%d",&item);
bins(0,n-1,item,a);
}
void bins(int lb,int ub,int item,int a[])
{
int mid,flag=0;
if(lb<=ub)
{
mid=(lb+ub)/2;
if(item==a[mid])
{
flag=flag+1;
}
else if(item<a[mid])
{
return bins(lb,mid-1,item,a);
}
else
return bins(mid+1,ub,item,a);
}
if(flag==0)
printf("Number is not found.");
else
printf("Number is found at %d", mid+1);
}
Showing posts with label Algorithm. Show all posts
Showing posts with label Algorithm. Show all posts
Thursday, November 27, 2014
Wednesday, November 12, 2014
Solve All-Pairs Shortest Path Problem using Floyd–Warshall Algorithm
Program:
#include<stdio.h>
#include<conio.h>
#define inf 999
void main()
{
int i,j,k,n,w[20][20];
clrscr();
printf("\n Enter the no. of vertices : ");
scanf("%d",&n);
printf("\n Enter the weights : ");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
printf("w[%d][%d]= ",i,j);
scanf("%d",&w[i][j]);
if(i!=j && (w[i][j]==0))
w[i][j]=inf;
}
for(i=1;i<=n;i++)
{
printf("\n");
for(j=1;j<=n;j++)
printf("%d\t",w[i][j]);
}
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(w[i][k]+w[k][j]<w[i][j])
w[i][j]=w[i][k]+w[k][j];
}
}
}
printf("\n The resultant Matrix : \n");
for(i=1;i<=n;i++)
{
printf("\n");
for(j=1;j<=n;j++)
printf("%d\t",w[i][j]);
}
getch();
}
Output:
Enter the no. of vertices : 5
Enter the weights : w[1][1]= 0
w[1][2]= 3
w[1][3]= 8
w[1][4]= 0
w[1][5]= 4
w[2][1]= 0
w[2][2]= 0
w[2][3]= 0
w[2][4]= 1
w[2][5]= 7
w[3][1]= 0
w[3][2]= 4
w[3][3]= 0
w[3][4]= 0
w[3][5]= 0
w[4][1]= 2
w[4][2]= 0
w[4][3]= 5
w[4][4]= 0
w[4][5]= 0
w[5][1]= 0
w[5][2]= 0
w[5][3]= 0
w[5][4]= 6
w[5][5]= 0
0 3 8 999 4
999 0 999 1 7
999 4 0 999 999
2 999 5 0 999
999 999 999 6 0
The resultant Matrix :
0 3 8 4 4
3 0 6 1 7
7 4 0 5 11
2 5 5 0 6
8 11 11 6 0
Insertion Sort
Write a C program to
implement Insertion Sort Algorithm
Algorithm:
for (c
= 1 to n - 1)
{
d
<= c;
while ( d > 0 AND array[d] < array[d-1])
{
t <= array[d];
array[d] <= array[d-1];
array[d-1] <= t;
d
<= d-1;
}
}
Program:
#include <stdio.h>
void main()
{
int
n, array[20], c, d, t;
printf("Enter the number of Elements:");
scanf("%d", &n);
printf("Enter %d integers:\n", n);
for
(c = 0; c < n; c++)
{
scanf("%d", &array[c]);
}
for
(c = 1 ; c <= n - 1; c++)
{
d =
c;
while ( d > 0 && array[d] < array[d-1])
{
t = array[d];
array[d] = array[d-1];
array[d-1] = t;
d--;
}
}
printf("Sorted list in ascending order:\n");
for
(c = 0; c <= n - 1; c++)
{
printf("%d ",
array[c]);
}
}
Output:
Enter the number of Elements:5
Enter 5 integers:
Enter the elements:
8 6 5 1 65
Sorted list in ascending order: 1 5 6 8 65
Conclusion:
Insertion sort is a simple sorting algorithm that
builds the final sorted array (or list) one item at a time. It is much less
efficient on large lists than more advanced algorithms such as quicksort,
heapsort, or merge sort.
Prim's Algorithm
Write a C Program to Implement Prim’s Algorithm and find the Minimum Spanning Tree (MST) for the following Graph.
Algorithm:
visit[1] <- 1;
while( p < n )
{
min=999;
for( i<- 1 to n )
{
for( j <- 1 to n )
{
if(cost[i][j] < min)
{
if( visit[i]!= 0 )
{
Min <- cost[i][j];
a <- u <- i;
b <- v <- j;
}
}
}
}
if( visit[u] = 0 OR visit[v] = 0 )
{
Print Edge of MST;
mincost <- mincost+min;
visit[b] <- 1;
}
cost[a][b] <- cost[b][a] <- inf;
}
Print Total Minimum Cost;
Program:
#include<stdio.h>
#include<conio.h>
#define inf 999
int cost[10][10],visit[10]={0};
int n,p=1,i,u,v,j,min,a,b,mincost;
void main()
{
clrscr();
printf("Enter node value: ");
scanf("%d",&n);
printf("Enter the adjacency matrix: \n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&cost[i][j]);
if( cost[i][j]==0 && i!=j )
cost[i][j]=inf;
}
}
printf("Entered Matrix: ");
for(i=1;i<=n;i++)
{
printf("\n");
for(j=1;j<=n;j++)
{
printf("%d\t",cost[i][j]);
}
}
visit[1]=1;
while(p<n)
{
for(i=1,min=999;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(cost[i][j]<min)
{
if (visit[i]!=0)
{
min=cost[i][j];
a=u=i;
b=v=j;
}
}
}
}
if(visit[u]==0 || visit[v]==0)
{
printf("\nEdge %d:(%d-%d) Cost=%d\n",p++,a,b,min);
mincost=mincost+min;
visit[b]=1;
}
cost[a][b]=cost[b][a]=inf;
}
printf("\n Minimum cost=%d",mincost);
getch();
}
Output:
Tuesday, September 9, 2014
C Program to Implement Heap Sort
Algorithm:
hs( a[], n)
{
heap(a,n);
for (i = n to 1)
{
temp<-a[1];
a[1]<-a[i];
a[i]<-temp;
downheap(a,1,i-1);
}
}
heap(a[],n)
{
index <- n/2;
for(i= index to 1)
downheap(a,i,n);
}
downheap(heap[], root, leaf)
{
lc<-2*root;
rc<-lc+1;
if(lc<=leaf)
{
max<-heap[lc];
index<-lc;
if(rc<=leaf)
{
if(heap[rc]>max)
{
max<-heap[rc];
index<-rc;
}
}
if(heap[root] < heap[index])
{
temp <- heap[root];
heap[root] <- heap[index];
heap[index] <- temp;
downheap(heap,index,leaf);
}
}
}
Program
#include<stdio.h>
#include<conio.h>
void heap(int *, int);
void downheap(int*,int,int);
void hs(int *,int);
void main()
{
int a[20],i,n;
clrscr();
printf("Enter the number of Elements:");
scanf("%d",&n);
printf("Enter the elements:\n");
for(i=1;i<=n;i++)
{
printf("Enter element [%d]:",i);
scanf("%d",&a[i]);
}
hs(a,n);
printf("The Sorted Elements are:");
for(i=1;i<=n;i++)
{
printf("%d ",a[i]);
}
getch();
}
void hs(int a[],int n)
{
int i,temp;
heap(a,n);
for (i=n;i>1;i--)
{
temp=a[1];
a[1]=a[i];
a[i]=temp;
downheap(a,1,i-1);
}
}
void downheap(int heap[],int root,int leaf)
{
int index,lc,rc,max,temp;
lc=2*root;
rc=lc+1;
if(lc<=leaf)
{
max=heap[lc];
index=lc;
if(rc<=leaf)
{
if(heap[rc]>max)
{
max=heap[rc];
index=rc;
}
}
if(heap[root]<heap[index])
{
temp=heap[root];
heap[root]=heap[index];
heap[index]=temp;
downheap(heap,index,leaf);
}
}
}
void heap(int a[],int n)
{
int i,index;
index=n/2;
for(i=index;i>=1;i--)
downheap(a,i,n);
}
Output:
Enter the
number of Elements:5
Enter the
elements:
Enter
element [1]:5
Enter
element [2]:8
Enter
element [3]:1
Enter
element [4]:6
Enter
element [5]:65
The
Sorted Elements are:1 5 6 8 65
Conclusion:
The
elements are arranged in a Max Heap. The root element is popped out and the
leaf node is placed in the blank position.
The
program has run correctly.
Monday, September 8, 2014
Write a C Program to find the number of data in a linked list
#include <stdio.h>
#define newnode (struct node*)malloc(sizeof(struct node))
typedef struct node
{
int data;
struct node *next;
} node;
node *create_list();
void main()
{
node *f;
int len;
f = NULL;
f = create_list();
len = find_len(f);
printf("\n length = %d",len);
} // main
node *create_list()
{
node *f,*c,*p;
int tdata;
f = NULL;
printf("\n Enter data ( use 0 to exit ) : ");
scanf("%d",&tdata);
while( tdata != 0 )
{
c = newnode;
if( c == NULL)
{
printf("\n Insuf. mem. ");
exit(0);
}
c->data = tdata;
c->next = NULL;
if( f== NULL)
f = c;
else
p->next = c;
p = c;
printf("\n Enter data ( use 0 to exit ) : ");
scanf("%d",&tdata);
} //while
return(f);
} // create list
int find_len(node *f)
{
int len=0;
node *t;
if( f == NULL)
return(0);
t = f;
while( t != NULL )
{
len++;
t = t->next;
}
return(len);
}
/*
Summary: Linked list is an ordered set of data elements, each containing a link to its successor. This program is to create a linked list. After creating the linked list ,the length of linked list is calculated.
*/
Saturday, September 6, 2014
Write a C Program to sort a set of number using Selection Sort
Algorithm:
ssort(array[],n)
{
for ( i = 0 to n-1 )
{
position <- i;
for ( j = i + 1 to n )
{
if ( array[position] > array[j] )
position <- j;
}
if ( position != i )
{
temp <- array[i];
array[i] <- array[position];
array[position] <- temp;
}
}
}
Program:
/* Using User Defined Method */
#include <stdio.h>
void printar(int array[], int n)
{
int i;
for ( i = 0 ; i < n ; i++ )
printf("%d ", array[i]);
printf("\n\n");
}
void ssort(int array[], int n)
{
int i,j,position,temp;
for ( i = 0 ; i < ( n - 1 ) ; i++ )
{
position = i;
for ( j = i + 1 ; j < n ; j++ )
{
if ( array[position] > array[j] )
position = j;
}
if ( position != i )
{
temp = array[i];
array[i] = array[position];
array[position] = temp;
printar(array,n);
}
}
}
void main()
{
int array[100], i,n;
printf("\nEnter number of elements: ");
scanf("%d", &n);
printf("\nEnter %d integers: ", n);
for ( i = 0 ; i < n ; i++ )
scanf("%d", &array[i]);
printf("\nProcessing... \n\n");
ssort(array,n);
printf("\n\nSorted list in ascending order: ");
printar(array,n);
}
/* Without Using User Defined Method */
#include<stdio.h>
void main()
{
int a[10],i,j,k,t;
printf("Enter 10 values:\n");
for(i=0;i<10;i++)
scanf("%d",&a[i]);
for(i=0;i<10;i++)
{
k=i;
for(j=i;j<10;j++)
{
if(a[k]>a[j])
k=j;
}
if(k!=i)
{
t=a[k];
a[k]=a[i];
a[i]=t;
}
}
printf("Sorted Array is:\n");
for(i=0;i<10;i++)
printf("%d\n",a[i]);
}
Output:
Conclusion:
The given elements are sorted. The smallest element gets its position at the beginning of given array and the sorting process is continued recursively from the next location as the starting of the array. The program has run correctly.
Write a C Program for Binary Search
#include<stdio.h>
void main()
{
int arr[10],i,max,min,mid,val,index;
printf("Please enter 10 values in ascending order:\n");
for(i=0;i<10;i++)
scanf("%d",&arr[i]);
printf("\nEnter a value to be searched: ");
scanf("%d",&val);
max=9;
min=0;
index=-1;
while(min<=max)
{
mid=(max+min)/2;
if(val==arr[mid])
{
index=mid;
break;
}
if(arr[mid]>val)
max=mid-1;
else
min=mid+1;
}
if(index>=0)
printf("Value found in Array at %d location",index+1);
else
printf("Value not found in Array");
}
Write a C Program to Implement Dijkstra's algorithm
Algorithm:
dj(int n,int v,int cost[][],int dist[])
{
for( i <- 1 to n )
flag[i]<-0;
dist[i]<-cost[v][i];
count<-2;
while(count<=n)
{
min<-99;
for( w <- 1 to n )
if(dist[w]<min && !a[w])
min <- dist[w];
u<-w;
a[u] <- 1;
count <- count+1;
for( w <- 1 to n )
if((dist[u]+cost[u][w])<dist[w] && !a[w])
dist[w] <- dist[u]+cost[u][w];
}
}
Program:
#include<stdio.h>
#include<conio.h>
#define inf 999
void dj(int n,int v,int cost[10][10],int dist[])
{
int i,u,count,w,a[10],min;
for(i=1;i<=n;i++)
a[i]=0,dist[i]=cost[v][i];
count=2;
while(count<=n)
{
min=99;
for(w=1;w<=n;w++)
if(dist[w]<min && !a[w])
min=dist[w],u=w;
a[u]=1;
count++;
for(w=1;w<=n;w++)
if((dist[u]+cost[u][w])<dist[w] && !a[w])
dist[w]=dist[u]+cost[u][w];
}
}
int main()
{
int n,v,i,j,cost[10][10],dist[10],infi=224;
clrscr();
printf("\n Enter the no.of nodes: ");
scanf("%d",&n);
printf("\n Enter the cost matrix:\n\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&cost[i][j]);
if(cost[i][j]==0 && i!=j )
cost[i][j]=inf;
}
printf("\n");
}
printf("The Matrix for the given graph is:\n\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(cost[i][j]!=inf)
printf("%d\t",cost[i][j]);
else
printf("%c\t",infi);
}
printf("\n");
}
printf("\n Enter the source: ");
scanf("%d",&v);
dj(n,v,cost,dist);
printf("\n Shortest path:\n");
for(i=1;i<=n;i++)
{
if(i!=v)
printf("%c->%c Cost=%d\n",64+v,64+i,dist[i]);
}
getch();
return 0;
}
Output:
Enter the no.of nodes: 9
Enter the cost matrix:
0 5 2 0 0 0 0 0 0
5 0 0 3 0 3 0 0 0
2 0 0 6 5 8 0 0 0
0 3 6 0 0 0 1 4 0
0 0 5 0 0 0 6 2 0
0 3 8 0 0 0 6 2 0
0 0 0 1 6 6 0 0 7
0 0 0 4 2 2 0 0 3
0 0 0 0 0 0 7 3 0
The Matrix for the given graph is:
0 5 2 α α α α α α
5 0 α 3 α 3 α α α
2 α 0 6 5 8 α α α
α 3 6 0 α α 1 4 α
α α 5 α 0 α 6 2 α
α 3 8 α α 0 6 2 α
α α α 1 6 6 0 α 7
α α α 4 2 2 α 0 3
α α α α α α 7 3 0
Enter the source: 1
Shortest path:
A->B Cost=5
A->C Cost=2
A->D Cost=8
A->E Cost=7
A->F Cost=8
A->G Cost=9
A->H Cost=9
A->I Cost=12
