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

Program for line clipping usingCohen-Sutherland algorithm

//Program for line clipping usingCohen-Sutherland algorithm

#include

#include

#include

#define LEFT_EDGE 0x1

#define RIGHT_EDGE 0x2

#define BOTTOM_EDGE 0x4

#define TOP_EDGE 0x8

#define INSIDE(a) (!a)

#define REJECT(a,b) (a&b)

#define ACCEPT(a,b) (!(a|b))

#define FALSE 0

#define TRUE 1

#define ROUND(a) (int) (a+0.5)

typedef struct wcPt2{

float x,y;

};

typedef struct dcPt{

float x,y;

};

void swapPts(wcPt2*p1,wcPt2*p2)

{

wcPt2 tmp;

tmp=*p1;

*p1=*p2;

*p2=tmp;

}

unsigned char encode(wcPt2 pt, dcPt winMin,dcPt winMax)

{

unsigned char code=0x00;

if(pt.x

code=code|LEFT_EDGE;

if(pt.x>winMax.x)

code=code|RIGHT_EDGE;

if(pt.y

code=code|BOTTOM_EDGE;

if(pt.y>winMax.y)

code=code|TOP_EDGE;

return (code);

}

void swapCodes(unsigned char*c1,unsigned char*c2)

{

unsigned char tmp;

tmp=*c1;

*c1=*c2;

*c2=tmp;

}

void clipLine(dcPt winMin,dcPt winMax,wcPt2 p1,wcPt2 p2)

{

unsigned char code1,code2;

int done=FALSE, draw=FALSE;

float m;

while(!done)

{

code1=encode(p1,winMin,winMax);

code2=encode(p2,winMin,winMax);

if(ACCEPT(code1,code2))

{

done=TRUE;

draw=TRUE;

}

else if(REJECT(code1,code2))

done=TRUE;

else

{

if(INSIDE(code1))

{

swapPts(&p1,&p2);

swapCodes(&code1,&code2);

}

if(p2.x!=p1.x)

m=(p2.y-p1.y)/(p2.x-p1.x);

if(code1&LEFT_EDGE)

{

p1.y+=(winMin.x-p1.x)*m;

p1.x=winMin.x;

}

else if(code1&RIGHT_EDGE)

{

p1.y+=(winMax.x-p1.x)*m;

p1.x=winMax.x;

}

else if(code1&BOTTOM_EDGE)

{

if(p2.x!=p1.x)

p1.x+=(winMin.y-p1.y)/m;

p1.y=winMin.y;

}

else if(code1&TOP_EDGE)

{

if(p2.x!=p1.x)

p1.x+=(winMax.y-p1.y)/m;

p1.y=winMax.y;

}

}

}

cleardevice();

outtextxy(280,10,"AFTER CLIPPING");

rectangle(winMin.x,winMin.y,winMax.x,winMax.y);

line(ROUND(p1.x),ROUND(p1.y),ROUND(p2.x),ROUND(p2.y));

getch();

}

void main()

{

int gd=DETECT,gm;

wcPt2 p1,p2;

dcPt winMin,winMax;

printf("\nEnter Left-top corner coordinates of the window : ");

scanf("%f %f",&winMin.x,&winMin.y);

printf("Enter Right-bottom corner coordinates of the window : ");

scanf("%f %f",&winMax.x,&winMax.y);

printf("\nEnter coordinates of the line :-");

printf("\nFirst point : ");

scanf("%f %f",&p1.x,&p1.y);

printf("Second point : ");

scanf("%f %f",&p2.x,&p2.y);

initgraph(&gd,&gm,"e:\\tc\\bgi");

outtextxy(280,10,"BEFORE CLIPPING");

rectangle(winMin.x,winMin.y,winMax.x,winMax.y);

line(p1.x,p1.y,p2.x,p2.y);

getch();

cleardevice();

clipLine(winMin,winMax,p1,p2);

}

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

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

#include

#include

#include

#include

void rotate();

void shear();

void reflect();

void main()

{

int ch;

int gd=DETECT,gm;

initgraph(&gd,&gm,"e:\\tc\\bgi");

setcolor(WHITE);

line(100,100,200,100);

line(200,100,200,300);

line(200,300,100,100);

printf("---MENU---");

printf("\n 1)Rotate\n 2)Reflect\n 3)Shear");

printf("\nEnter your choice: ");

scanf("%d",&ch);

cleardevice();

switch(ch)

{

case 1: rotate();

break;

case 2: reflect();

break;

case 3: shear();

break;

default: printf("you have enterd wrong choice");

break;

}

getch();

closegraph();

}

void rotate()

{

float theta;

int x1,x2,x3;

int y1,y2,y3;

int ax1,ax2,ax3,ay1,ay2,ay3;

int refx,refy;

printf("\nEnter the angle for rotation: ");

scanf("%f",&theta);

cleardevice();

setcolor(WHITE);

outtextxy(240,10,"ROTATE");

outtextxy(238,20,"-------");

refx=100;

refy=100;

printf("Theta=%d",(int)theta);

theta=theta*(3.14/180);

x1=100;

y1=100;

x2=200;

y2=100;

x3=200;

y3=300;

ax1=refx+(x1-refx)*cos(theta)-(y1-refy)*sin(theta);

ay1=refy+(x1-refx)*sin(theta)+(y1-refy)*cos(theta);

ax2=refx+(x2-refx)*cos(theta)-(y2-refy)*sin(theta);

ay2=refy+(x2-refx)*sin(theta)+(y2-refy)*cos(theta);

ax3=refx+(x3-refx)*cos(theta)-(y3-refy)*sin(theta);

ay3=refy+(x3-refx)*sin(theta)+(y3-refy)*cos(theta);

setcolor(BROWN);

line(100,100,200,100);

line(200,100,200,300);

line(200,300,100,100);

setcolor(WHITE);

line(ax1,ay1,ax2,ay2);

line(ax2,ay2,ax3,ay3);

line(ax3,ay3,ax1,ay1);

}

void shear()

{

float shx;

int x1,x2,x3;

int y1,y2,y3;

int ax1,ax2,ax3,ay1,ay2,ay3;

int refy;

printf("\nEnter the shear parameter : ");

scanf("%f",&shx);

cleardevice();

setcolor(WHITE);

outtextxy(240,10,"SHEAR");

outtextxy(238,20,"-------");

refy=100;

printf("shx=%f\nyref=%d",shx,refy);

x1=100;

y1=100;

x2=200;

y2=100;

x3=200;

y3=300;

ax1=x1+shx*(y1-refy);

ay1=y1;

ax2=x2+shx*(y2-refy);

ay2=y2;

ax3=x3+shx*(y3-refy);

ay3=y3;

setcolor(BROWN);

line(100,100,200,100);

line(200,100,200,300);

line(200,300,100,100);

setcolor(WHITE);

line(ax1,ay1,ax2,ay2);

line(ax2,ay2,ax3,ay3);

line(ax3,ay3,ax1,ay1);

}

void reflect()

{

int x1,x2,x3;

int y1,y2,y3;

int ax1,ax2,ax3,ay1,ay2,ay3;

int refx;

cleardevice();

setcolor(WHITE);

outtextxy(240,10,"REFLECT(about x=320)");

outtextxy(238,20,"---------------------");

refx=320;

x1=100;

y1=100;

x2=200;

y2=100;

x3=200;

y3=300;

ax1=640-x1;

ay1=y1;

ax2=640-x2;

ay2=y2;

ax3=640-x3;

ay3=y3;

setcolor(BROWN);

line(x1,y1,x2,y2);

line(x2,y2,x3,y3);

line(x3,y3,x1,y1);

setcolor(WHITE);

line(320,50,320,400);

line(ax1,ay1,ax2,ay2);

line(ax2,ay2,ax3,ay3);

line(ax3,ay3,ax1,ay1);

}

Program to show translation and scaling in 2D

//Program to show translation and scaling in 2D

#include

#include

#include

#include

void translate();

void scale();

void main()

{

int ch;

int gd=DETECT,gm;

initgraph(&gd,&gm,"e:\\tc\\bgi");

setcolor(WHITE);

outtextxy (50,50,"Object.");

rectangle(100,100,300,200);

printf("---MENU---");

printf("\n 1)Translate\n 2)Scale");

printf("\nEnter your choice: ");

scanf("%d",&ch);

cleardevice();

switch(ch)

{

case 1: translate();

break;

case 2: scale();

break;

default: printf("you have enterd wrong choice");

break;

}

getch();

closegraph();

}

void translate()

{

int tx,ty;

setcolor(WHITE);

outtextxy(240,10,"TRANSLATION");

outtextxy(238,20,"------------");

printf("\nEnter tx: ");

scanf("%d",&tx);

printf("\nEnter ty: ");

scanf("%d",&ty);

cleardevice();

setcolor(BROWN);

rectangle(100,100,300,200);

setcolor(WHITE);

outtextxy(10,250,"After Translation");

rectangle(100+tx,100+ty,300+tx,200+ty);

}

void scale()

{

int b,r;

float sx,sy;

setcolor(WHITE);

outtextxy(240,10,"SCALING");

outtextxy(238,20,"--------");

printf("\nEnter sx: ");

scanf("%f",&sx);

printf("\nEnter sy: ");

scanf("%f",&sy);

cleardevice();

r=200*sx+100;

b=100*sy+100;

outtextxy(20,250,"After");

outtextxy(10,260,"Scaling");

setcolor(BROWN);

rectangle(100,100,300,200);

setcolor(WHITE);

rectangle(100,100,r,b);

}

Program to draw a circle using Bresenham’s circle algorithm

//Program to draw a circle using Bresenham’s circle algorithm
#include
#include
#include
#include
void cirbh(int,int,int);
void circlepp(int,int,int,int);
void main()
{
int gdriver=DETECT,gmode;
int x,y,r;
clrscr();
printf("\nEnter the coordinates of the centre : ");
scanf("%d %d",&x,&y);
printf("\nEnter the radius : ");
scanf("%d",&r);
initgraph(&gdriver,&gmode,"e:\\tc\\bgi");
cirbh(x,y,r);
getch();
}

void cirbh(int x,int y,int r)
{
int xa=0, ya=r;
int d=3-2*r;
circlepp(x,y,xa,ya);
while(xa<=ya)
{
circlepp(x,y,xa,ya);
if(d<0)
d+=4*xa+6;
else
{
d+=4*(xa-ya)+10;
ya--;
}
xa++;
}
}
void circlepp(int x,int y,int xa,int ya)
{
putpixel(x+xa,y+ya,WHITE);
putpixel(x-xa,y+ya,WHITE);
putpixel(x+xa,y-ya,WHITE);
putpixel(x-xa,y-ya,WHITE);
putpixel(x+ya,y+xa,WHITE);
putpixel(x-ya,y+xa,WHITE);
putpixel(x+ya,y-xa,WHITE);
putpixel(x-ya,y-xa,WHITE);
}

Program to draw a circle using midpoint circle algorithm

//Program to draw a circle using midpoint circle algorithm

#include
#include
#include
#include
void cirmp(int,int,int);
void circlepp(int,int,int,int);
void main()
{
int gdriver=DETECT,gmode;
int x,y,r,i;
clrscr();
printf("\nEnter the coordinates of centre : ");
printf("\nx : ");scanf("%d",&x);
printf("y : ");scanf("%d",&y);
printf("\nEnter the radius : ");
scanf("%d",&r);
initgraph(&gdriver,&gmode,"e:\\tc\\bgi");
cirmp(x,y,r);
getch();
}
void cirmp(int x,int y,int r)
{
int xa=0, ya=r;
int p=1-r;
circlepp(x,y,xa,ya);
while(xa{
xa++;
if(p<0)
p+=2*xa+1;
else
{
ya--;
p+=2*(xa-ya)+1;
}
circlepp(x,y,xa,ya);
}
}
void circlepp(int x,int y,int xa,int ya)
{
putpixel(x+xa,y+ya,2);
putpixel(x-xa,y+ya,2);
putpixel(x+xa,y-ya,2);
putpixel(x-xa,y-ya,2);
putpixel(x+ya,y+xa,2);
putpixel(x-ya,y+xa,2);
putpixel(x+ya,y-xa,2);
putpixel(x-ya,y-xa,2);
}

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

//Program to draw a line using Bresenham’s line drawing algorithm

#include

#include

#include

#include

void bresen(int,int,int,int);

void main()

{

int gdriver=DETECT,gmode;

int x1,x2,y1,y2;

clrscr();

printf("\nEnter coordinates of end points : ");

printf("\nx1 : ");scanf("%d",&x1);

printf("y1 : ");scanf("%d",&y1);

printf("x2 : ");scanf("%d",&x2);

printf("y2 : ");scanf("%d",&y2);

initgraph(&gdriver,&gmode,"e:\\tc\\bgi");

bresen(x1,y1,x2,y2);

getch();

}

void bresen(int x1,int y1,int x2,int y2)

{

int dx,dy,p,twoDy,twoDyDx,x,y,xEnd;

dx=abs(x2-x1); dy=abs(y2-y1);

p=2*dy-dx;

twoDy=2*dy;

twoDyDx=2*(dy-dx);

if(x1>x2)

{

x=x2;

y=y2;

xEnd=x1;

}

else

{

x=x1;

y=y1;

xEnd=x2;

}

putpixel(x,y,WHITE);

while(x

{

x++;

if(p<0)

p+=twoDy;

else

{

y++;

p+=twoDyDx;

}

putpixel(x,y,WHITE);

}

}



Program to draw a line using DDA line drawing algorithm

//Program to draw a line using DDA line drawing algorithm

#include

#include

#include

#include

#define round(a) (int) (a+0.5)

void dda(int,int,int,int);

void main() {

int gdriver=DETECT,gmode;

int x1,x2,y1,y2;

clrscr();

printf("\nEnter coordinates of end points : ");

printf("\nx1 : ");scanf("%d",&x1);

printf("y1 : ");scanf("%d",&y1);

printf("x2 : ");scanf("%d",&x2);

printf("y2 : ");scanf("%d",&y2);

initgraph(&gdriver,&gmode,"e:\\tc\\bgi");

dda(x1,y1,x2,y2);

getch();

}

void dda(int x1,int y1,int x2,int y2)

{

int dx,dy,steps,k;

float xinc,yinc,x,y;

x=x1;

y=y1;

dx=x2-x1;

dy=y2-y1;

if(abs(dx)>=abs(dy))

steps=abs(dx);

else

steps=abs(dy);

xinc=dx/(float)steps;

yinc=dy/(float)steps;

putpixel(round(x),round(y),WHITE);

for(k=0;k

x+=xinc;

y+=yinc;

putpixel(round(x),round(x),WHITE);

}

}