Technocrat

  • Home
Showing posts with label Algorithm. Show all posts
Showing posts with label Algorithm. Show all posts

Thursday, November 27, 2014

Binary Search in C using Recursion

 Sumit Kar     November 27, 2014     Algorithm, C - Programming, Data Structure     No comments   


#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);
}


Read More
  • Share This:  
  •  Facebook
  •  Twitter
  •  Google+
  •  Stumble
  •  Digg
  •  WhatsApp

Wednesday, November 12, 2014

Solve All-Pairs Shortest Path Problem using Floyd–Warshall Algorithm

 Sumit Kar     November 12, 2014     Algorithm, C - Programming     No comments   



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











Read More
  • Share This:  
  •  Facebook
  •  Twitter
  •  Google+
  •  Stumble
  •  Digg
  •  WhatsApp

Insertion Sort

 Sumit Kar     November 12, 2014     Algorithm, C - Programming     No comments   



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.


Read More
  • Share This:  
  •  Facebook
  •  Twitter
  •  Google+
  •  Stumble
  •  Digg
  •  WhatsApp

Prim's Algorithm

 Sumit Kar     November 12, 2014     Algorithm, C - Programming     No comments   

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:
 




Read More
  • Share This:  
  •  Facebook
  •  Twitter
  •  Google+
  •  Stumble
  •  Digg
  •  WhatsApp

Tuesday, September 9, 2014

C Program to Implement Heap Sort

 Sumit Kar     September 09, 2014     Algorithm, C - Programming     No comments   



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.



Read More
  • Share This:  
  •  Facebook
  •  Twitter
  •  Google+
  •  Stumble
  •  Digg
  •  WhatsApp

Monday, September 8, 2014

Write a C Program to find the number of data in a linked list

 Sumit Kar     September 08, 2014     Algorithm, C - Programming, Data Structure     No comments   



Sumit Kar, Sorting, C, Timus Rak, C Program



#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.
*/


Read More
  • Share This:  
  •  Facebook
  •  Twitter
  •  Google+
  •  Stumble
  •  Digg
  •  WhatsApp

Saturday, September 6, 2014

Write a C Program to sort a set of number using Selection Sort

 Sumit Kar     September 06, 2014     Algorithm, C - Programming     No comments   



Selection Sort, Sumit Kar, Timus Rak










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.


Read More
  • Share This:  
  •  Facebook
  •  Twitter
  •  Google+
  •  Stumble
  •  Digg
  •  WhatsApp

Write a C Program for Binary Search

 Sumit Kar     September 06, 2014     Algorithm, C - Programming     No comments   



Binary Search, Sumit Kar, Timus rak


#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");


}


Read More
  • Share This:  
  •  Facebook
  •  Twitter
  •  Google+
  •  Stumble
  •  Digg
  •  WhatsApp

Write a C Program to Implement Dijkstra's algorithm

 Sumit Kar     September 06, 2014     Algorithm, C - Programming     No comments   












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








Read More
  • Share This:  
  •  Facebook
  •  Twitter
  •  Google+
  •  Stumble
  •  Digg
  •  WhatsApp
Older Posts Home

Pages

  • Home

Trending Now

  • Write a Program to Add two 3x3 Matrix using C
    #include<stdio.h> void main () { int a [ 3 ][ 3 ], b [ 3 ][ 3 ], s [ 3 ][ 3 ], i , j ; printf ( "Enter the values of ...
  • C program for Unit Conversion
    /* Convert Celsius to Fahrenheit */ #include<stdio.h> void main() {     float c,f;     printf("Enter the temperature in Celcius: ...
  • Addition of two numbers on Server sent from Client [TCP] using C
    /* tcpClient.c */ #include <sys/types.h> #include <sys/socket.h> #include <netinet/in.h> #include <arpa/inet.h> #inc...
  • Write a Program to Print the Truth Table of Basic Gates using C
  • Write a Program to Add two 5x5 Matrix using C
    #include<stdio.h> void main() {   int a[5][5],b[5][5],c[5][5];   int i,j;   for(i=0;i<5;i++)   {     printf("\nEnter elements ...
  • Using the concept of Inheritance write a C++ Program to calculate the area and perimeter of rectangle
    /* C++ Program to calculate the area and perimeter of rectangles using concept of inheritance. */ #include using namespace std; class Re...
  • Concatenation of two strings sent from Client on the Server - [ TCP ] using C
    /* tcpClient.c */ #include <sys/types.h> #include <sys/socket.h> #include <netinet/in.h> #include <arpa/inet.h> #inc...
  • 8085 Programming: Exchange the contents of memory locations
    Exchange the contents of memory locations 2000H and 4000H. Program 1: LDA 2000H : Get the contents of memory location 2000H into accumulator...
  • Calculate Depreciation using C
    #include<conio.h> #include<stdio.h> void main () { float sv , pv , dep ; int yos ; clrscr (); printf ( "Enter the pu...
  • 8085 Programming: 1's COMPLEMENT OF A 16-BIT NUMBER
    The 16bit number is stored in C050,C051 The answer is stored in C052,C053   LXI H,C050   MOV A,M   CMA   STA C052   INX H   MOV ...

Blog Archive

  • ▼  2020 (1)
    • ▼  May (1)
      • Automating your deployments using Ansible
  • ►  2015 (92)
    • ►  October (4)
    • ►  September (3)
    • ►  August (3)
    • ►  July (9)
    • ►  June (9)
    • ►  May (20)
    • ►  April (7)
    • ►  March (22)
    • ►  February (7)
    • ►  January (8)
  • ►  2014 (158)
    • ►  November (70)
    • ►  October (6)
    • ►  September (82)
Powered by Blogger.

Categories

C - Programming Java Programming Basic Technology 8085 Assembly Programming For Loop Numerical Methods WhatsApp Algorithm Shell Programming Programming Networking Windows Android C++ Programming CPP If Else Tricky Internet Microsoft Pattern Photography Socket Program News While Loop Array DBMS DS Macro Recursion User Defined Function Conditional Operator Data Structure Durga Puja Earthquake Google Mela Nokia SQL Share Yahoo Airtel Bio Command Prompt Confused Facebook Finance Firefox Ganges Graph HokKolorob Input Kolkata MCQ Math Matrix NetNeutrality Oracle Religion Search Sumit Kar Survey Switch Case Viral Virus Visual Studio do-while featured featured_slider

Popular Programs

  • Write a Program to Add two 3x3 Matrix using C
    #include<stdio.h> void main () { int a [ 3 ][ 3 ], b [ 3 ][ 3 ], s [ 3 ][ 3 ], i , j ; printf ( "Enter the values of ...
  • C program for Unit Conversion
    /* Convert Celsius to Fahrenheit */ #include<stdio.h> void main() {     float c,f;     printf("Enter the temperature in Celcius: ...
  • Addition of two numbers on Server sent from Client [TCP] using C
    /* tcpClient.c */ #include <sys/types.h> #include <sys/socket.h> #include <netinet/in.h> #include <arpa/inet.h> #inc...
  • Write a Program to Print the Truth Table of Basic Gates using C
  • Write a Program to Add two 5x5 Matrix using C
    #include<stdio.h> void main() {   int a[5][5],b[5][5],c[5][5];   int i,j;   for(i=0;i<5;i++)   {     printf("\nEnter elements ...
  • Using the concept of Inheritance write a C++ Program to calculate the area and perimeter of rectangle
    /* C++ Program to calculate the area and perimeter of rectangles using concept of inheritance. */ #include using namespace std; class Re...
  • Concatenation of two strings sent from Client on the Server - [ TCP ] using C
    /* tcpClient.c */ #include <sys/types.h> #include <sys/socket.h> #include <netinet/in.h> #include <arpa/inet.h> #inc...
  • 8085 Programming: Exchange the contents of memory locations
    Exchange the contents of memory locations 2000H and 4000H. Program 1: LDA 2000H : Get the contents of memory location 2000H into accumulator...
  • Calculate Depreciation using C
    #include<conio.h> #include<stdio.h> void main () { float sv , pv , dep ; int yos ; clrscr (); printf ( "Enter the pu...
  • 8085 Programming: 1's COMPLEMENT OF A 16-BIT NUMBER
    The 16bit number is stored in C050,C051 The answer is stored in C052,C053   LXI H,C050   MOV A,M   CMA   STA C052   INX H   MOV ...

Daily Hits

Copyright © Sumit Kar