Class NP-Non Deterministic Polynomial Bounded

Non Deterministic Algorithms
It has two phases and one output Step-
1)Non Deterministic guessing Phase
2)Deterministic verifying phase
3)Output phase

Non Deterministic guessing Phase
In this phase we arbitrarily choose a string which is considered as proposed solution/certificate for given problem.

Deterministic verifying phase
In this phase we use a fixed /deterministic procedure to verify that proposed solution is correct or not.
If the proposed solution is correct then it returns "YES" otherwise "FALSE".

Output phase
The output is "YES" if step Return "true" otherwise nothing is given as output.


An Non-deterministic algorithm is said to be polynomially bounded if it gives YES answer in polynomial time.

==>>NP is a class of problem for which we have non-deterministic polynomial bounded algorithm.
Eg. 1)Travelling Salesman Problem
      2)Hamiltonial Cycle
      3)Job sheduling

Class P-Polynomially Bounded

Polynomially Bounded

An algorithm is said to be polynomially bounded if its worst case running time is described by polynomail function of input size.

Polynomially Bounded problem

A problem is said to be Polynomially bounded if we have polynomial bounded algorithm for it.

-->P is a class of Problem that are polynomially bounded.

Ex-Sorting,Searching,Minimum Spanning Tree.

Classification of Problems

1. Class P
2. Class NP
3. Class NP-HARD
4. Class NP-Complete

Decision Problems

Decision Problem
Many optimization problems can be formullated as Decision problem
-Decision problem is YES/NO question.The question is about some input.
      It has two parts --
1)Instance Description-This part contains input specified in the problem.
2)Question Part-This is YES/NO question.
                        -The question is about input specifies in the instance description.
Eg.  P1
     Given a graph G(V,E)
           QUESTION- Is graph G is m Colourable.
  
       P2
      Given a graph G & integar m.
            QUESTION-Is graph G is m Colourable.

Let the solution of the given Decision problem is given by function θ(m^2.N^m)


Its clear from the function that problem can be solved in polynomial time whereas P2 goes into exponential time.

Theory Of NP-Completeness

Theory of Completeness
It classifies the programming problems under two broad categories-

• Tractable
• Intractable

Tractable Problems

-a problem that is solvable by a polynomial-time algorithm.
-The upper bound is polynomial.
-Running in resourcable amount of time.
-NOT SO HARD problems
Eg. n,n^2 ,n lgn etc.

Intractable Problems

-a problem that cannot be solved by a polynomial-time algorithm. The lower bound is exponential.
-HARD problems
-List all permutations (all possible orderings) of n numbers.

Eg. List all permutations (all possible orderings) of n numbers.

Computer Graphics Program

• Program to draw a line using DDA line drawing algorithm
• Program to draw a line using Bresenham’s line drawing algorithm

• Program to draw a circle using midpoint circle algorithm

• Program to draw a circle using Bresenham’s circle algorithm

• Program to show translation and scaling in 2D

• Program to show rotation,reflection, and shearing in 2D

• Program for line clipping usingCohen-Sutherland algorithm

• Program for polygon clipping using Sutherland-Hodgeman algorithm

Program for polygon clipping using Sutherland-Hodgeman algorithm

//Program for polygon clipping using Sutherland-Hodgeman algorithm

#include
#include
#include
#define MAXVERTICES 11
#define MAXCORDINATES ((MAXVERTICES * 2) + 1)

int corArray[MAXCORDINATES],nVertices=0;
int corArray2[MAXCORDINATES],nVertices2=0;
int wx_min,wx_max,wy_min,wy_max;

enum boundry {left=0,right,bottom,top};

void initialize()
{
int gDriver = DETECT,gMode;
initgraph(&gDriver,&gMode,"e:\\tc\\bgi");
cleardevice();
}
void inputPolygon()
{
printf("\nEnter No of Vertices (Min. 3,Max. %d ): ",MAXVERTICES);
scanf("%d",&nVertices);
if(nVertices <> MAXVERTICES) nVertices = 3;
for(int i=0;i wx_min);
case right:
return (x <> wy_max);
}
return 0;
}

int calcCondition(int x1,int y1,int x2,int y2,boundry b)
{
int stat1 = insideWindow(x1,y1,b);
int stat2 = insideWindow(x2,y2,b);
if(!stat1 && stat2) return 1;
if(stat1 && stat2) return 2;
if(stat1 && !stat2) return 3;
if(!stat1 && !stat2) return 4;
return 0; //never executed
}

void solveIntersection(boundry b,int x1,int y1,int x2,int y2,int &x,int &y)
{
float m = 0;
if(x2 != x1) m = ((float)(y2-y1)/(float)(x2-x1));
switch(b)
{
case left:
x = wx_min;
y = y1 + m * (x - x1);
break;
case right:
x = wx_max;
y = y1 + m * (x - x1);
break;
case bottom:
y = wy_min;
if(x1 != x2)
x = x1 + (float)(1/m) * (y - y1);
else
x = x1;
break;
case top:
y = wy_max;
if(x1 != x2)
x = x1 + (float)(1/m) * (y - y1);
else
x = x1;
break;
}
}

void addNewPoint(int x,int y)
{
corArray2[(2 * nVertices2)] = x;
corArray2[(2 * nVertices2)+1] = y;
nVertices2++;
}


void clipPolygon()
{ int j,k;
boundry i;
for(i=left;i<=top;i++) { nVertices2 = 0; for(j=0;j