What are P, NP, NP-complete, and NP-hard ?

P (Polynomial time decidable problems) is a class of problems which can be decided in polynomial time i.e., there’s an algorithm for such a problem which tells whether the solution of a given instance of a problem is true/false in O(n^k) time for some constant k.
For example, deciding whether there exists a path of at most k links between two vertices u and v is in P.

NP (Non-deterministic polynomial time decidable problems) is a class of problems which have short accepting certificates and efficient verification algorithms i.e., given a certificate of a solution, it is easy to check if the problem is satisfied.
Accepting certificate is information which can be used to decide if the answer is true or false.
Formally, a problem is in NP if there exists a verification algorithm A such that for any input x for which the answer is “true”, there is a certificate c such that |c| is polynomial and A(x,c) = true. For any x for which the answer is true, there is no certificate c such that |c| is polynomial and A(x,c) is true.
For example, given a graph G and a number k, deciding whether there exists a clique (complete subgraph) of size k, is in NP.

P is a subset of NP i.e., any problem that is in P is also in NP. It is easy to see that for any problem that can be decided in polynomial time, there exists a verification algorithm that given any certificate just ignores the certificate and returns the result of the polynomial-time algorithm.

Whether NP is also a subset of P (i.e., P = NP) is an open question. No one knows yet.

NP-hard is a class of problems which are hardest of all problems in NP. These are the problems such that if we can solve them fast, then we can solve all problems in NP fast and P would equal NP. NP-hard problems may be of any type: decision problems, search problems, or optimization problems so they may not even be in NP.
For example, the clique problem discussed above is NP-hard.

NP-complete is a class of problems which are in NP and are NP-hard. NP-complete problems transform to each-other by polynomial-time many-one reductions so if a polynomial-time algorithm exists for any one of them, then polynomial algorithms exist for all of them. However, no polynomial algorithm for any NP-complete problem has yet been found.
For example, the clique problem discussed above is NP-complete.

Programm For Finding Binary Number Addition

Programm For Finding Binary Number Addition
———————————————————————


#include <stdio.h>
int main ()
{
  int a[6]={1,0,0,1,1,1},b[6]={1,1,0,1,1,0},c[7], carry=0, j;
  for(j=5;j>=0;j--)
   {
       c[j+1]=a[j]^b[j]^carry;
       carry = (a[j]*(b[j]^carry))+(b[j]*carry);
   }
  c[j+1]=carry;
  for (j=6;j>=0;j--)
   {
     printf ("%d",c[j]);
   }
return 0;
}

Importance of Loop Invariant in programming

Introduction:

It is hard to keep track of what is happening with loops. Loops which don’t terminate or terminate without achieving their goal behavior is a common problem in computer programming. Loop invariants help. A loop invariant is a formal statement about the relationship between variables in your program which holds true just before the loop is ever run (establishing the invariant) and is true again at the bottom of the loop, each time through the loop (maintaining the invariant).

Why Loop Invariant:
It captures what the loop does not do, i.e., what it leaves unchanged over any single execution of the loop body (and hence over the entire execution of the loop)

Loop Invariant

  •     Invariant means unchanged
  •     The person who writes the loop, also writes the loop invariant which describes what remains unchanged
  •     Permits understanding what the loop does without having to understand (at the same time) how it does it.
  •     We can reason about the loop’s effect on the larger program without hand tracing each loop iteration.

 General Pattern of loop invariant in Code

...
// the Loop Invariant must be true here
while ( TEST CONDITION ) {
// top of the loop
......
......
// bottom of the loop
// the Loop Invariant must be true here
}
// Termination + Loop Invariant = Goal
...
invariant + termination => goal

Below code is example of Loop Invariant

  
  int j = 10;
  for(int i=0; i<11; i++)
   {  
     // Your loop code stuff
     j--;
   } 
  At the end i+j = 10
  so here J= 10 is loop invariant

If you Understand Give me the answer of

 if (i % 2 == 0)
 {
   while (i>=0)
    {
       i = i/2;
       if (i%2 != 0)
         {
       i =i-1;
     }
       else
         {
           i= i-2
         }
    }
 }

 What is appropriate loop invariant for the while loop _________

Reference Link: http://www.cs.miami.edu/~burt/learning/Math120.1/Notes/LoopInvar.html

http://stackoverflow.com/questions/3221577/what-is-a-loop-invariant

Page keyword: What is loop invariant, loop invariant in while loop, loop invariant example, loop invariant code example

Code Optimization Technique: In Programming Language

Code Optimization technique part 1:   Write only those code that makes you better coder.

In this post we will consider loop whose casual use can slow down your program performance.

Note: This post for all of those who write code in any language it is general programming basic concept.

Loop Optimization
The code optimization can be significantly done at loop statement in any language. In loop of the program , specially inner loop is a placed where program spend a large amount of time.

1) Code motion : If there is some expression in the loop , whose result is remain unchanged even after executing the loop for several times then , such an expression will be placed just before the loop.

Bad Practice:

while (i<=max-1)
{
   sum = sum +a[i];
}

Good Practice:

n= max-1
while (i<=n)
{
   sum = sum+a[i];
}

Loop invariant:
It is the technique of avoiding computation /calculation inside loop.

Bad Practice:

for( i=0;i<=10;i++)
{
k= i+a/b;
}

Good Practice:

n=a/b;
for ( i=0; i<=10;i++)
{
  k=i+n;
}

Bad Practice:

for (i=0; i<=10;i++)
{
   add();
}

Good Practice:

for ( i=0; i<=10;i++)
{
// Write definition or inline code of add().
}

Loop Fusion:
– It is technique of measuring several loop into one loop.

Bad Practice:

for ( i=1; i<=10;i++)
{
  for (j=1;j<=10;j++)
  {
   printf ("NIshant");
  }
}

Good Practice:

for ( i=1;i<=100;i++)
{
   printf ("Nishant");
}

 Loop Unrolling:
It is the technique of number of jump and test will be reduced by writing the code two times.

Bad Practice:

int i = 1;
while (i<=100)
{
   a[i] = b[i];
   i++;
}

Good Practice: 

int i = 1;
while (i<=100)
{
   a[i] = b[i];
   i++;
   a[i] = b[i];
   i++;
}

Feel free to comment on above thumbs rule for loop which I follows in my daily coding routine. And any suggestion and any new things from your side is always welcome.

Happy coding:)