Optimizing Bellman Ford algorithm

Bellman Ford algorithm is used to find single source shortest path. In this algorithm, we try to relax each edge n-1 times where n is the number of vertices. Instead of running the code for each edge again and again, we can relax only those edges which are connected to the vertex which was relaxed in the last iteration.

Link to code.

Priority queue using heap

The code uses a max heap to remove the maximum element present in the data. Heap is used as it helps to perform the above operation in O(log n) time.
Link to code.

KMP string search

KMP (Knuth Morris Pratt) Pattern Searching
The naive pattern search doesn’t work well in cases where we see many matching characters followed by a mismatching character.
The KMP matching algorithm uses degenerating property (pattern having same sub-patterns appearing more than once in the pattern) of the pattern and improves the worst case complexity to O(n). The basic idea behind KMP’s algorithm is: whenever we detect a mismatch (after some matches), we already know some of the characters in the text of next window. We take advantage of this information to avoid matching the characters that we know will anyway match.
Link to code.

Count number of ones in binary of a number

#include <iostream>
using namespace std;
//count no of ones in binary representation
int count1(int n)
{
    int c=0;
    while(n)
    {
        n=n&(n-1);
        cout<<n;
        c++;
    }
    return c;
}
int main(){
 cout<<count1(6);
 return 0;
}

Finding all prime factors in minimum time complexity

//find all prime factors
#include <iostream>
#include<math.h>
using namespace std;

int main() {
    int n;
    cin>>n;
    cout<<n<<endl;
    int count=0;
    for(int i=2;i<=n;i++)
    {
        count =0;
        while(n%i==0){
            n/=i;
            count++;
        }
        if(count)
            cout<<i<<"<<"<<count<<endl;
    }
    
 return 0;
}

Reversing Link List in group of n nodes without using any other data type in O(n) time

Some ways of reversing a link list using other data types are-
1.Use the stack. We can push all the elements on to the stack and then poop out each element. 
2.Similarly, we can also create a new link list. Starting from the head of the current list, we can create  new list by adding nodes in the front of the new list.

A link list can be reversed without using any other data type by using three pointers as shown in the code below.

//created by Aditya Vijayvergia

//uploaded on thecodingedge.blogspot.com

#include<stdio.h>

#include<conio.h>

struct node

{

  int data;

  struct node* next;

}*head;

typedef struct node node;

node* rev(int n)

{

  node *p,*q,*r,*t2,*t1;

  int c=0,start=1;

  t2=head;

  t1=NULL;

  p=head;

  q=head->next;

  r=q->next;

  while(q!=NULL)

  {

    //printf("c<n-1\n\t%d",p->data);

    //getch();

    if(c==n-1)

    {

      //printf("c=n-1");

      //getch();

      c=0;

      if(t1!=NULL)

    t1->next=p;

      t1=t2;

      t2=q;

      if(start==1)

      {

    start=0;

    head=p;

      }

      p=q;

      q=p->next;

      r=q->next;

    }

    q->next=p;

    p=q;

    q=r;

    r=r->next;

    c++;

  }

  t1->next=p;

  t2->next=NULL;

  return head;

}

void main()

{

  node *q;

  node* p;

  int i;

  clrscr();

  head=(node*)malloc(sizeof(node));

  p=head;

  //q->next=NULL;

  head->data=1;

  //p->next=NULL;

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

  {

    q=(node*)malloc(sizeof(node));

    q->next=NULL;

    q->data=i;

    p->next=q;

    p=p->next;

  }

  p=head;

  printf("Initial link list is:\n");

  while(p!=NULL)

  {

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

    p=p->next;

  }

  printf("\n\n\n\nUsing n=3\n");

  head=rev(6);

  p=head;

  printf("\n\n\nReversed link list is:\n");

  while(p!=NULL)

  {

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

    p=p->next;

  }

  getch();

}

The output of the program is given below.

Converting Postfix Expression to Prefix Expression and Infix Expression in C

In prefix expression, the operator comes before the operands where as in postfix expression, the operator comes in the end. So to convert a postix expression to a prefix expression, we just have to 

bring the operator in the front for each sub expression.

For doing this we use a stack that stores a 2D character array. We can visualize it like a 1D character array that stores operands. The push operation pushes an operand to the stack and the pop operation returns a pointer to the last operand.

First push the operands on to the stack until an operator is encountered. When an operator is encountered we pop the last two operands and create a new character array.

 Now if we want to convert to infix expression then we store the first operand then the operator and then the second operand. Similarly for prefix expression we first store the operator and then the two operands in order.We then push this newly created character array to the stack.

The logic is that the character array that we pushed will now act as an operand for further operations.

The source code for prefix expression is given below.

//created by Aditya Vijayvergia
//uploaded on thecodingedge.blogspot.com
#include<stdio.h>
#include<conio.h>
#include<ctype.h>
#define size 20
struct stack
{
  char data[size][size];
  int top;
}s;
void push(char x[20])
{
  int i;
  s.top++;
  for(i=0;i<strlen(x);i++)
   s.data[s.top][i]=x[i];
}
char* pop()
{
char *p;
if(s.top==-1)
  return NULL;
return s.data[s.top--];
}

void main()
{
  char q[50],c[50];
  char *a,*b;
  int i,j,a1,b1;
  s.top=-1;
  clrscr();
  printf("\nenter postfix expression:");
  gets(q);
  for(j=0;j<strlen(q);j++)
  {
  if(q[j]>='a'&&q[j]<='z')
    {
    s.data[++s.top][0]=q[j];
    //printf("\npush %c",q[j]);
    }
  else
  {
  b=pop();
  a=pop();
  //printf("\na=%s\tb=%s",a,b);
  c[0]=q[j];
  a1=strlen(a);
  b1=strlen(b);
  for(i=0;i<a1;i++)
    {
    c[i+1]=*a;
    a++;
    }
  for(i=0;i<b1;i++)
    {
    c[a1+i+1]=*b;
    b++;
    }
  push(c);
  //printf("\npushed operand %s",c);
  }
  a=NULL;
  b=NULL;
  }
  printf("\n\nPrefix expression : %s",pop());
  getch();
}