Programming: C Program to Represent Graph Using Adjacency Matrix

C Code Graph Programming

Programming: C Program to Represent Graph Using Adjacency Matrix

This C program generates graph using Adjacency Matrix Method.

A graph G,consists of two sets V and E. V is a finite non-empty set of vertices.E is a set of pairs of vertices,these pairs are called as edges V(G) and E(G) will represent the sets of vertices and edges of graph G.

Undirected graph – It is a graph with V vertices and E edges where E edges are undirected. In undirected graph, each edge which is present between the vertices Vi and Vj,is represented by using a pair of round vertices (Vi,Vj).

Directed graph – It is a graph with V vertices and E edges where E edges are directed.In directed graph,if Vi and Vj nodes having an edge.than it is represented by a pair of triangular brackets Vi,Vj.

Here is the source code of the C program to create a graph using adjacency matrix. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

//... A Program to represent a Graph by using an Adjacency Matrix method
#include 
#include 
int dir_graph();
int undir_graph();
int read_graph(int adj_mat[50][50], int n );

void main()
{
   int option;
   do
   {     
        printf("\n A Program to represent a Graph by using an ");
  printf("Adjacency Matrix method \n ");
  printf("\n 1. Directed Graph ");
  printf("\n 2. Un-Directed Graph ");
  printf("\n 3. Exit ");
  printf("\n\n Select a proper option : ");
  scanf("%d", &option);
  switch(option)
  {
    case 1 : dir_graph();
       break;
    case 2 : undir_graph();
       break;
    case 3 : exit(0);
  } // switch
    }while(1);
}
 
int dir_graph()
{
    int adj_mat[50][50];
    int n;
    int in_deg, out_deg, i, j;
    printf("\n How Many Vertices ? : ");
    scanf("%d", &n);
    read_graph(adj_mat, n);
    printf("\n Vertex \t In_Degree \t Out_Degree \t Total_Degree ");
    for (i = 1; i <= n ; i++ )
    {
        in_deg = out_deg = 0;
 for ( j = 1 ; j <= n ; j++ )
 {
            if ( adj_mat[j][i] == 1 )
                in_deg++;
 } 
        for ( j = 1 ; j <= n ; j++ )
            if (adj_mat[i][j] == 1 )
                out_deg++;
            printf("\n\n %5d\t\t\t%d\t\t%d\t\t%d\n\n",i,in_deg,out_deg,in_deg+out_deg);
    }
    return;
}
 
int undir_graph()
{
    int adj_mat[50][50];
    int deg, i, j, n;
    printf("\n How Many Vertices ? : ");
    scanf("%d", &n);
    read_graph(adj_mat, n);
    printf("\n Vertex \t Degree ");
    for ( i = 1 ; i <= n ; i++ )
    {
        deg = 0;
        for ( j = 1 ; j <= n ; j++ )
            if ( adj_mat[i][j] == 1)
                deg++;
        printf("\n\n %5d \t\t %d\n\n", i, deg);
    } 
    return;
} 
 
int read_graph ( int adj_mat[50][50], int n )
{
    int i, j;
    char reply;
    for ( i = 1 ; i <= n ; i++ )
    {
        for ( j = 1 ; j <= n ; j++ )
        {
            if ( i == j )
            {
                adj_mat[i][j] = 0;
  continue;
            } 
            printf("\n Vertices %d & %d are Adjacent ? (Y/N) :",i,j);
            scanf("%c", &reply);
            if ( reply == 'y' || reply == 'Y' )
                adj_mat[i][j] = 1;
            else
                adj_mat[i][j] = 0;
 }
    } 
    return;
}

$ gcc graph.c -o graph
$ ./graph
 A Program to represent a Graph by using an Adjacency Matrix method 
 
 1. Directed Graph 
 2. Un-Directed Graph 
 3. Exit 
 
 Select a proper option : 
 How Many Vertices ? : 
 Vertices 1 & 2 are Adjacent ? (Y/N) : N
 Vertices 1 & 3 are Adjacent ? (Y/N) : Y
 Vertices 1 & 4 are Adjacent ? (Y/N) : Y
 Vertices 2 & 1 are Adjacent ? (Y/N) : Y
 Vertices 2 & 3 are Adjacent ? (Y/N) : Y
 Vertices 2 & 4 are Adjacent ? (Y/N) : N
 Vertices 3 & 1 are Adjacent ? (Y/N) : Y
 Vertices 3 & 2 are Adjacent ? (Y/N) : Y
 Vertices 3 & 4 are Adjacent ? (Y/N) : Y
 Vertices 4 & 1 are Adjacent ? (Y/N) : Y
 Vertices 4 & 2 are Adjacent ? (Y/N) : N
 Vertices 4 & 3 are Adjacent ? (Y/N) : Y
 Vertex   In_Degree   Out_Degree   Total_Degree 
 
     1   2  0  2
 
 
 
     2   1  2  3
 
 
 
     3   0  1  1
 
 
 
     4   1  1  2
 
 
 A Program to represent a Graph by using an Adjacency Matrix method 
 
 1. Directed Graph 
 2. Un-Directed Graph 
 3. Exit

08:13

Algorithm: Inorder Tree Traversal without Recursion

Algorithm Algorithms C c++ data structure inorder Programming traversal

Algorithm: Inorder Tree Traversal without Recursion

Its been a long time since I'd posted something about programming and algorithms. I've been reading a lot more about algorithms, so found one perfectly explained article, thought I should share it with you people.

Using Stack is the obvious way to traverse tree without recursion. Below is an algorithm for traversing binary tree using stack.
See this for step wise step execution of the algorithm.

1) Create an empty stack S.
2) Initialize current node as root
3) Push the current node to S and set current = current->left until current is NULL
4) If current is NULL and stack is not empty then
     a) Pop the top item from stack.
     b) Print the popped item, set current = current->right
     c) Go to step 3.
5) If current is NULL and stack is empty then we are done.

Let us consider the below tree for example:

            1
          /   \
        2      3
      /  \
    4     5

Step 1 Creates an empty stack: S = NULL

Step 2 sets current as address of root: current -> 1

Step 3 Pushes the current node and set current = current->left until current is NULL
     current -> 1
     push 1: Stack S -> 1
     current -> 2
     push 2: Stack S -> 2, 1
     current -> 4
     push 4: Stack S -> 4, 2, 1
     current = NULL

Step 4 pops from S
     a) Pop 4: Stack S -> 2, 1
     b) print "4"
     c) current = NULL /*right of 4 */ and go to step 3
Since current is NULL step 3 doesn't do anything.

Step 4 pops again.
     a) Pop 2: Stack S -> 1
     b) print "2"
     c) current -> 5/*right of 2 */ and go to step 3

Step 3 pushes 5 to stack and makes current NULL
     Stack S -> 5, 1
     current = NULL

Step 4 pops from S
     a) Pop 5: Stack S -> 1
     b) print "5"
     c) current = NULL /*right of 5 */ and go to step 3
Since current is NULL step 3 doesn't do anything

Step 4 pops again.
     a) Pop 1: Stack S -> NULL
     b) print "1"
     c) current -> 3 /*right of 5 */

Step 3 pushes 3 to stack and makes current NULL
     Stack S -> 3
     current = NULL

Step 4 pops from S
     a) Pop 3: Stack S -> NULL
     b) print "3"
     c) current = NULL /*right of 3 */

Traversal is done now as stack S is empty and current is NULL.

Implementation:

#include<stdio.h>
#include<stdlib.h>
#define bool int

/* A binary tree tNode has data, pointer to left child
   and a pointer to right child */
struct tNode
{
   int data;
   struct tNode* left;
   struct tNode* right;
};

/* Structure of a stack node. Linked List implementation is used for
   stack. A stack node contains a pointer to tree node and a pointer to
   next stack node */

struct sNode
{
  struct tNode *t;
  struct sNode *next;
};

/* Stack related functions */
void push(struct sNode** top_ref, struct tNode *t);
struct tNode *pop(struct sNode** top_ref);
bool isEmpty(struct sNode *top);

/* Iterative function for inorder tree traversal */
void inOrder(struct tNode *root)
{
  /* set current to root of binary tree */
 struct tNode *current = root;
  struct sNode *s = NULL;  /* Initialize stack s */
  bool done = 0;
  while (!done)
  {
    /* Reach the left most tNode of the current tNode */
    if(current !=  NULL)
    {
      /* place pointer to a tree node on the stack before traversing
        the node's left subtree */
      push(&s, current);                                              
      current = current->left; 
    }      
    /* backtrack from the empty subtree and visit the tNode
       at the top of the stack; however, if the stack is empty,
      you are done */
    else                                                            
    {
      if (!isEmpty(s))
      {
        current = pop(&s);
        printf("%d ", current->data);

        /* we have visited the node and its left subtree.
          Now, it's right subtree's turn */
        current = current->right;
      }
      else
        done = 1;
    }
  } /* end of while */
}    

/* UTILITY FUNCTIONS */

/* Function to push an item to sNode*/
void push(struct sNode** top_ref, struct tNode *t)
{
  /* allocate tNode */
  struct sNode* new_tNode =
            (struct sNode*) malloc(sizeof(struct sNode));
  if(new_tNode == NULL)
  {
     printf("Stack Overflow \n");
     getchar();
     exit(0);
  }           
  /* put in the data  */
  new_tNode->t  = t;

  /* link the old list off the new tNode */
  new_tNode->next = (*top_ref);  

  /* move the head to point to the new tNode */
  (*top_ref)    = new_tNode;
}

/* The function returns true if stack is empty, otherwise false */
bool isEmpty(struct sNode *top)
{
   return (top == NULL)? 1 : 0;
}  
/* Function to pop an item from stack*/

struct tNode *pop(struct sNode** top_ref)
{
  struct tNode *res;
  struct sNode *top;

  /*If sNode is empty then error */
  if(isEmpty(*top_ref))
  {
     printf("Stack Underflow \n");
     getchar();
     exit(0);
  }
  else
  {
     top = *top_ref;
     res = top->t;
     *top_ref = top->next;
     free(top);
     return res;
  }
}

/* Helper function that allocates a new tNode with the
   given data and NULL left and right pointers. */
struct tNode* newtNode(int data)
{
  struct tNode* tNode = (struct tNode*)
                       malloc(sizeof(struct tNode));
  tNode->data = data;
  tNode->left = NULL;
  tNode->right = NULL;

  return(tNode);
}

/* Driver program to test above functions*/
int main()
{

  /* Constructed binary tree is

            1

          /   \

        2      3

      /  \

    4     5

  */
  struct tNode *root = newtNode(1);
  root->left        = newtNode(2);
  root->right       = newtNode(3);
  root->left->left  = newtNode(4);
  root->left->right = newtNode(5);

  inOrder(root);

  getchar();
  return 0;
}

Time Complexity: O(n)

This article has been shared from Geeks for Geeks. Please let me know if you have any concern about anything in this article.

Later folks.... :)

20:50

Programming: Reverse alternate K nodes in a Singly Linked List

Algorithm Algorithms C c++ Linked Lists Programming

Programming: Reverse alternate K nodes in a Singly Linked List

Given a linked list, write a function to reverse every alternate k nodes (where k is an input to the function) in an efficient way. Give the complexity of your algorithm.

Example:
Inputs:   1->2->3->4->5->6->7->8->9->NULL and k = 3
Output:   3->2->1->4->5->6->9->8->7->NULL.

Method 1 (Process 2k nodes and recursively call for rest of the list) 

This method is basically an extension of the method discussed in this post.
kAltReverse(struct node *head, int k)
  1)  Reverse first k nodes.
  2)  In the modified list head points to the kth node.  So change next
       of head to (k+1)th node
  3)  Move the current pointer to skip next k nodes.
  4)  Call the kAltReverse() recursively for rest of the n - 2k nodes.
  5)  Return new head of the list.

#include<stdio.h>

#include<stdlib.h>



/* Link list node */

struct node

{

    int data;

    struct node* next;

};



/* Reverses alternate k nodes and

   returns the pointer to the new head node */

struct node *kAltReverse(struct node *head, int k)

{

    struct node* current = head;

    struct node* next;

    struct node* prev = NULL;

    int count = 0;  



    /*1) reverse first k nodes of the linked list */

    while (current != NULL && count < k)

    {

       next  = current->next;

       current->next = prev;

       prev = current;

       current = next;

       count++;

    }

  

    /* 2) Now head points to the kth node.  So change next

       of head to (k+1)th node*/

    if(head != NULL)

      head->next = current;  



    /* 3) We do not want to reverse next k nodes. So move the current

        pointer to skip next k nodes */

    count = 0;

    while(count < k-1 && current != NULL )

    {

      current = current->next;

      count++;

    }



    /* 4) Recursively call for the list starting from current->next.

       And make rest of the list as next of first node */

    if(current !=  NULL)

       current->next = kAltReverse(current->next, k);



    /* 5) prev is new head of the input list */

    return prev;

}



/* UTILITY FUNCTIONS */

/* Function to push a node */

void push(struct node** head_ref, int new_data)

{

    /* allocate node */

    struct node* new_node =

            (struct node*) malloc(sizeof(struct node));



    /* put in the data  */

    new_node->data  = new_data;



    /* link the old list off the new node */

    new_node->next = (*head_ref);   



    /* move the head to point to the new node */

    (*head_ref)    = new_node;

}



/* Function to print linked list */

void printList(struct node *node)

{

    int count = 0;

    while(node != NULL)

    {

        printf("%d  ", node->data);

        node = node->next;

        count++;

    }

}   



/* Drier program to test above function*/

int main(void)

{

    /* Start with the empty list */

    struct node* head = NULL;



    // create a list 1->2->3->4->5...... ->20

    for(int i = 20; i > 0; i--)

      push(&head, i);



     printf("\n Given linked list \n");

     printList(head);

     head = kAltReverse(head, 3);



     printf("\n Modified Linked list \n");

     printList(head);



     getchar();

     return(0);

}

Output:
Given linked list
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Modified Linked list
3 2 1 4 5 6 9 8 7 10 11 12 15 14 13 16 17 18 20 19

Time Complexity: O(n)

Method 2 (Process k nodes and recursively call for rest of the list) 

The method 1 reverses the first k node and then moves the pointer to k nodes ahead. So method 1 uses two while loops and processes 2k nodes in one recursive call.

This method processes only k nodes in a recursive call. It uses a third bool parameter b which decides whether to reverse the k elements or simply move the pointer.

_kAltReverse(struct node *head, int k, bool b)
  1)  If b is true, then reverse first k nodes.
  2)  If b is false, then move the pointer k nodes ahead.
  3)  Call the kAltReverse() recursively for rest of the n - k nodes and link
       rest of the modified list with end of first k nodes.
  4)  Return new head of the list.

#include<stdio.h>

#include<stdlib.h>



/* Link list node */

struct node

{

    int data;

    struct node* next;

};



/* Helper function for kAltReverse() */

struct node * _kAltReverse(struct node *node, int k, bool b);



/* Alternatively reverses the given linked list in groups of

   given size k. */

struct node *kAltReverse(struct node *head, int k)

{

  return _kAltReverse(head, k, true);

}

 

/*  Helper function for kAltReverse().  It reverses k nodes of the list only if

    the third parameter b is passed as true, otherwise moves the pointer k

    nodes ahead and recursively calls iteself  */

struct node * _kAltReverse(struct node *node, int k, bool b)

{

   if(node == NULL)

       return NULL;



   int count = 1;

   struct node *prev = NULL;

   struct node  *current = node;

   struct node *next;

 

   /* The loop serves two purposes

      1) If b is true, then it reverses the k nodes

      2) If b is false, then it moves the current pointer */

   while(current != NULL && count <= k)

   {

       next = current->next;



       /* Reverse the nodes only if b is true*/

       if(b == true)

          current->next = prev;

            

       prev = current;

       current = next;

       count++;

   }

   

   /* 3) If b is true, then node is the kth node.

       So attach rest of the list after node.

     4) After attaching, return the new head */

   if(b == true)

   {

        node->next = _kAltReverse(current,k,!b);

        return prev;       

   }

   

   /* If b is not true, then attach rest of the list after prev.

     So attach rest of the list after prev */  

   else

   {

        prev->next = _kAltReverse(current, k, !b);

        return node;      

   }

}

 



/* UTILITY FUNCTIONS */

/* Function to push a node */

void push(struct node** head_ref, int new_data)

{

    /* allocate node */

    struct node* new_node =

            (struct node*) malloc(sizeof(struct node));

 

    /* put in the data  */

    new_node->data  = new_data;

 

    /* link the old list off the new node */

    new_node->next = (*head_ref);

 

    /* move the head to point to the new node */

    (*head_ref)    = new_node;

}

 

/* Function to print linked list */

void printList(struct node *node)

{

    int count = 0;

    while(node != NULL)

    {

        printf("%d  ", node->data);

        node = node->next;

        count++;

    }

}

 

/* Drier program to test above function*/

int main(void)

{

    /* Start with the empty list */

    struct node* head = NULL;

    int i;

 

    // create a list 1->2->3->4->5...... ->20

    for(i = 20; i > 0; i--)

      push(&head, i);

 

    printf("\n Given linked list \n");

    printList(head);

    head = kAltReverse(head, 3);

 

    printf("\n Modified Linked list \n");

    printList(head);

 

    getchar();

    return(0);

}

Output: Given linked list 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Modified Linked list 3 2 1 4 5 6 9 8 7 10 11 12 15 14 13 16 17 18 20 19 Time Complexity: O(n)

01:54

Programming: Print 100 to 1 without using any loops in the program

C c++ Programming

Programming: Print 100 to 1 without using any loops in the program

Hello folks, hope you people are doing well..

I have tried some of the techniques to print 100 to 1 without using any loops in the program. So here are some of the best suitable techniques. Actually I only have one right now, but will surely share others as soon as I get some better differences between them to share.

Main concept here is to use Recursion.

Method #1:

#include <iostream>

using namespace std;

void printvals(int);



void printvals(int n)

{

  if(n!=0)

  {

  cout<<n<<" ";

  printvals(--n);

  }

}

int main()

{

  int i=100;

  printvals(i);

  return 0;

}

Later Folks...... :)

23:50

Programming: Variable Storage Classes

C c++ Programming

Programming: Variable Storage Classes

Automatic: auto 

• storage is automatically allocated on function/block entry and automatically freed when the function/block is exited 
• may not be used with global variables (which have storage space that exists for the life of the program) 
• auto is the default for function/block variables 
• auto int a is the same as int a 
• because it is the default, it is almost never used

Optimization Hint: register

• register provides a hint to the compiler that you think a variable will be frequently used
• compiler is free to ignore register hint
• if ignored, the variable is equivalent to an auto variable with the exception that you may not take the address of a register (since, if put in a register, the variable will not have an address)
• rarely used, since any modern compiler will do a better job of optimization than most programmers

Static Storage: static

• if used inside a block or function, the compiler will create space for the variable which lasts for the life of the program

•   int
    counter(void)
    {
   static int cnt = 0;
  
   return cnt++;
    }
  

  causes the counter() function to return a constantly increasing number

External References: extern

• If a variable is declared (with global scope) in one file but referenced in another, the extern keyword is used to inform the compiler of the variable's existence:
  • In declare.c:

    int farvar;
    

  • In use.c:

    {
     extern int farvar;
     int a;
     a = farvar * 2;
    }
    

• Note that the extern keyword is for declarations, not definitions
• An extern declaration does not create any storage; that must be done with a global definition

Private Variables: static

• another use for the static keyword is to ensure that code outside this file cannot modify variables that are globally declared inside this file
  • If declare.c had declared farvar as:

    static int farvar;
    

    then the extern int farvar statement in use.c would cause an error
  • This use of static is commonly used in situations where a group of functions need to share information but do not want to risk other functions changing their internal variables

    static int do_ping = 1; /* start with `PING' */
    
    void
    ping(void)
    {
     if (do_ping == 1) {
      printf("PING ");
      do_ping = 0;
     }
    }
    
    void
    pong(void)
    {
     if (do_ping == 0) {
      printf("PONG\n");
      do_ping = 1;
     }
    }

Variable Initialization

• auto, register and static variables may be initialized at creation:

    int
    main(void)
    {
   int a = 0;
   register int start = 1234;
   static float pi = 3.141593;
    }
  

• Any global and static variables which have not been explicitly initialized by the programmer are set to zero
• If an auto or register variable has not been explicitly initialized, it contains whatever was previously stored in the space that is allocated to it
  • this means that auto and register variables should always be initialized before being used
  • compiler may provide a switch to warn about uninitialized variables

21:44

Programming: Converting Decimal into Binary & Binary Into Decimal

bit magic C c++ Programming

Programming: Converting Decimal into Binary & Binary Into Decimal

Its been very important that you know all the techniques of converting a decimal into binary or vice-versa. Here I am going to show two techniques of converting a decimal into binary, one of them is using bit-manipulation and the other one is conventional.

One conventional method of converting decimal into binary is shown below:

Here is the implementation:

#include <iostream>

#include <math.h>

using namespace std;



void dec2bin(unsigned n, int a[])

/* This method is bit-manipulation */ 

{

   unsigned i, j=0;

   for(i = 1 << 15; i>0; i = i/2)

   {
a
  if(n & i)

  {

   a[j++] = 1;

  }

  else

  {

   a[j++] = 0;

  }

   }

}



void dec2bin2(int n)

/* Conventional Method */ 

{

   if(n>1)

  dec2bin2(n/2);

  

   printf("%d", n%2);

}



int main()

{

   int a[16] = {0}, i, sum=0;

   dec2bin(4, a);

   for(i=0; i<=15; i++)

  cout<<a[i];

   cout<<endl;

   //dec2bin2(65535);

   

   /* Below method will convert the binary into Decimal */
   for(i=0; i<16; i++)

   {

  sum+=((pow(2, (15-i)))*a[i]);

   }

   cout<<"Decimal: "<<sum;

   return 0;

}

I have shown two methods of converting the decimal number into binary and one method in the main() to show the conversion of binary in decimal number...

Let me know if you have any queries or above program requires any correction...
.... Next time... :)

01:12

Programming: Finding first non-repeating character in given string

Algorithm Algorithms C c++ Programming

Programming: Finding first non-repeating character in given string

Given a string, find the first non-repeating character in it. For example, if the input string is “HelloWorld”, then output should be ‘H’ and if input string is “HelloHowAreYou”, then output should be ‘w’.

We can use string characters as index and build a count array. Following is the algorithm.

1) Scan the string from left to right and construct the count array.
2) Again, scan the string from left to right and check for count of each
 character, if you find an element who's count is 1, return it.

Example:

Input string: str = helloworld
1: Construct character count array from the input string.

  count['h'] = 1
  count['e'] = 1
  count['l'] = 3
  count['o'] = 2
  count['w'] = 1
  ……
2: Get the first character who's count is 1 ('h').

Implementation:

#include <iostream>

#include <malloc.h>

#define NO_OF_CHAR 256

using namespace std;



int *getcharcountarray(char *str)

{

    int *count = (int *)calloc(sizeof(int), NO_OF_CHAR);

    int i;

    for(i=0; *(str+i); i++)

     count[*(str+i)]++;

    return count;

}



int gettheindex(char *str)

{

    int *count = getcharcountarray(str);

    int index = -1, i;

    

    for(i=0; *(str+i); i++)

    {

     if(count[*(str+i)] == 1)

     {

         index = i;

         break;

     }

    }

    free(count);

    return index;

}



int main()

{

    char str[] = "samsungelectronics";

    int index = gettheindex(str);

    if(index == -1)

     cout<<"Either all characters are repeating or string is empty"<<endl;

    else

     cout<<"First repeating character is "<<str[index]<<endl;

    return 0;



}

21:47

Programming: Find 'n'th root of K number

C c++ Programming Square root

Programming: Find 'n'th root of K number

Hello friends,

Today I am going to share a program to find 'n'th root of a given 'k' number. So here is the program.

#include<stdio.h>

#include <math.h>

double root1(int,int);

int main()
{
    int n;
    int num1;
    double root;
    printf("Enter a number greater then 1: ");
    scanf("%d",&num1);
    if(num1>1)
    {
        printf("Enter the value for 'n'(the root to be calculated): ");
        scanf("%d",&n);
        root = root1(num1,n);
        printf("%d th Root of %d is %f\n\n", n,num1,root);
    }
    else
        printf("Wrong entry");
    return 0;
}

double root1(int a, int b)
{
    int j;
    double i,k=1;
    double incre = 0.01;

    for(i=1; i<=a; i = i+incre)
    {
        for(j=0;j<b;j++)
        {
            k=k*i;
        }
        if(a<k)
        {
            return(i-incre);
            break;
        }
        else
            k=1;
    }
}

Hope it helps... .... Later.... :)

21:45

Programming: Fastest Algorithm to Check Whether Given Number is Prime or not

Algorithm Algorithms C c++ Prime Prime Number Programming Time Complexity

Programming: Fastest Algorithm to Check Whether Given Number is Prime or not

Hello to one and all..

I am going to discuss some methods to check whether given number is prime or not. But before we go any further, notice that the reason we use different methods here is to check whether method being used, decreases the time complexity or not. So here we go.

It is required to write a function that takes an integer and returns true if that integer is prime else it returns false.
well, a number is prime if and only if it has exactly two distinct natural number divisors: 1 and itself.
So for example 2, 3, 5, 7, 11, … , 97 , … are all prime, while 24 is not prime because it is divisible by 2,3,4,6,7 and 8. To find if a number n is prime we could simply (using brute force attack) check if it divides any numbers below it. We can use the modulus (%) operator to check for divisibility:

Method 1:

bool IsPrime(int num)
{
 if(num<=1)
  return false;
 for(int i=2; i<num; i++)
 {
  if(num%i==0)
   return false;
 }
 return true;
}

We can optimize this function by noticing that we only need to check divisibility for values of i that are less or equal to the square root of num. And if we couldn’t find a divisor under the square root it is impossible mathematically to find another one above the square root because divisors of any number come in couples, the multiplication of any two couples will be the original number. 

For example 64 has the following divisors:
1           64
2           32
4            16
8           (8)

note here is a special case because 64 has a perfect square root (8) so, while checking the divisors we have to check up to the square root itself. 

Method 2 (Improvement of Method 1) : 

bool IsPrime(int num) 
{ 
 if(num<=1) 
       return false; 
 for(int i=2; i<=sqrt(num*1.0); i++) 
 { 
        if(num%i==0) 
        return false; 
 } 
 return true; 
}

sqrt() function needs you to include “cmath” file and it takes one double parameter so I multiply our int by 1.0

Another optimization is to realize that there are no even primes greater than 2. Once we’ve checked that n is not even we can safely increment the value of i by 2. We can now write the final method for checking whether a number is prime: 

Method 3 (Improvement in Previous Methods) :- 

bool IsPrime(int num) 
{ 
 if(num<=1) 
         return false; 
 if(num==2) 
          return true; 
 if(num%2==0) 
         return false; 
 int sRoot = sqrt(num*1.0); 
 for(int i=3; i<=sRoot; i+=2) 
 { 
        if(num%i==0) 
        return false; 
 } 
 return true; 
}

the check in line 5 returns true if the number is 2 because we returns false for all even numbers after it.

I used the following project to test the time needed to check if the numbers from 0 to 100000 are prime or not:


#include <iostream>
#include <ctime>
#include <cmath>

using namespace std;

bool IsPrime(int num)
{
 //past one of the previos versions
}

void main()
{
 clock_t start,end;
 start=clock();
 for(int i=0; i<=100000; i++)
  IsPrime(i);
 end=clock();
 cout<<"Version 1 takes "<<end-start<<" msec"<<endl;

}

And I got:










So the final method will decrease the time complexity from 7328 msec to 47 msec.

Its really great. This article has been shared from Holmezideas. Hope you find it helpful. .......More....Next Time.... :p

23:17

Programming: Validate All Parenthesis in an Expression

Algorithm Algorithms C c++ Node Parenthesis Validation Programming Stack Structure traversal Validation

Programming: Validate All Parenthesis in an Expression

Today, I am going to share one article about parenthesis validation in an expression. This can also be applied to a string containing parenthesis. So here we go.

Given an expression string exp, write a program to examine whether the pairs and the orders of “{“,”}”,”(“,”)”,”[","]” are correct in exp. For example, the program should print true for exp = “[()]{}{[()()]()}” and false for exp = “[(])”

Algorithm:
1) Declare a character stack S.
2) Now traverse the expression string exp.
    a) If the current character is a starting bracket (‘(‘ or ‘{‘ or ‘[') then push it to stack.
    b) If the current character is a closing bracket (')' or '}' or ']‘) then pop from stack and if the popped character is the matching starting bracket then fine else parenthesis are not balanced.
3) After complete traversal, if there is some starting bracket left in stack then “not balanced”

Implementation:

#include<stdio.h> #include<stdlib.h> #define bool int /* structure of a stack node */ struct sNode { char data; struct sNode *next; }; /* Function to push an item to stack*/ void push(struct sNode** top_ref, int new_data); /* Function to pop an item from stack*/ int pop(struct sNode** top_ref); /* Returns 1 if character1 and character2 are matching left and right Parenthesis */ bool isMatchingPair(char character1, char character2) { if(character1 == '(' && character2 == ')') return 1; else if(character1 == '{' && character2 == '}') return 1; else if(character1 == '[' && character2 == ']') return 1; else return 0; } /*Return 1 if expression has balanced Parenthesis */ bool areParenthesisBalanced(char exp[]) { int i = 0; /* Declare an empty character stack */ struct sNode *stack = NULL; /* Traverse the given expression to check matching parenthesis */ while(exp[i]) { /*If the exp[i] is a starting parenthesis then push it*/ if(exp[i] == '{' || exp[i] == '(' || exp[i] == '[') push(&stack, exp[i]); /* If exp[i] is a ending parenthesis then pop from stack and check if the popped parenthesis is a matching pair*/ if(exp[i] == '}' || exp[i] == ')' || exp[i] == ']') { /*If we see an ending parenthesis without a pair then return false*/ if(stack == NULL) return 0; /* Pop the top element from stack, if it is not a pair parenthesis of character then there is a mismatch. This happens for expressions like {(}) */ else if ( !isMatchingPair(pop(&stack), exp[i]) ) return 0; } i++; } /* If there is something left in expression then there is a starting parenthesis without a closing parenthesis */ if(stack == NULL) return 1; /*balanced*/ else return 0; /*not balanced*/ } /* UTILITY FUNCTIONS */ /*driver program to test above functions*/ int main() { char exp[100] = "{()}[]"; if(areParenthesisBalanced(exp)) printf("\n Balanced "); else printf("\n Not Balanced "); \ getchar(); } /* Function to push an item to stack*/ void push(struct sNode** top_ref, int new_data) { /* allocate node */ struct sNode* new_node = (struct sNode*) malloc(sizeof(struct sNode)); if(new_node == NULL) { printf("Stack overflow \n"); getchar(); exit(0); } /* put in the data */ new_node->data = new_data; /* link the old list off the new node */ new_node->next = (*top_ref); /* move the head to point to the new node */ (*top_ref) = new_node; } /* Function to pop an item from stack*/ int pop(struct sNode** top_ref) { char res; struct sNode *top; /*If stack is empty then error */ if(*top_ref == NULL) { printf("Stack overflow \n"); getchar(); exit(0); } else { top = *top_ref; res = top->data; *top_ref = top->next; free(top); return res; } }

Time Complexity: O(n)
Auxiliary Space: O(n) for stack.

Hope it helps. This article has been shared from Geeks for Geeks.

..... Next Time :)

21:09

Programming: Binary Representation of a given number

bit fields bit magic bits and bytes C c++ Programming

Programming: Binary Representation of a given number

Hello friends,
I've been reading one article about bits and bit fields in C, and I came across some methods to represent a number in binary form in C. So below are some methods and algorithms.

Method 1: Iterative
For any number, we can check whether its ‘i’th bit is 0(OFF) or 1(ON) by bitwise ANDing it with "2^i" (2 raise to i).

1) Let us take number 'NUM' and we want to check whether it's 0th bit is
ON or OFF
 bit = 2 ^ 0 (0th bit)
 if  NUM & bit == 1 means 0th bit is ON else 0th bit is OFF

2) Similarly if we want to check whether 5th bit is ON or OFF
 bit = 2 ^ 5 (5th bit)
 if NUM & bit == 1 means its 5th bit is ON else 5th bit is OFF.

Let us take unsigned integer (32 bit), which consist of 0-31 bits. To print binary representation of unsigned integer, start from 31th bit, check whether 31th bit is ON or OFF, if it is ON print "1" else print "0". Now check whether 30th bit is ON or OFF, if it is ON print "1" else print "0", do this for all bits from 31 to 0, finally we will get binary representation of number.

void bin(unsigned n)
{
    unsigned i;
    for (i = 1 << 31; i > 0; i = i / 2)
        (n & i)? printf("1"): printf("0");
}
int main(void)
{
    bin(7);
    printf("\n");
    bin(4);
}

Method 2: Recursive

 Following is recursive method to print binary representation of ‘NUM’.
 step 1) if NUM > 1
a) push NUM on stack
b) recursively call function with 'NUM / 2'
 step 2)
a) pop NUM from stack, divide it by 2 and print it's remainder.

void bin(unsigned n)

{
   

/* step 1 */
   

if (n > 1)

         bin(n/2);
   

/* step 2 */

     printf("%d", n % 2);

 }

 int main(void)

 {

     bin(7);

     printf("\n");

     bin(4);

 }

 This article has been shared from Geeks for Geeks. Hope it helps. ..... Next time...:)

05:14