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);

}

}

Algorithm Analysis

Framework for Algorithm Analysis

We may design many algorithms for solving many different kind of problems.If we want to compare these algorithm & even just plain evaluate them, we require sound mathematical bases and that is what we are going to do.Building a formal framework using which we can evaluate and also compare them.

Basic Idea

mathematical model of computer-mentally execute algorithms on computer model and evaluate the time.

This is the basic Scheme/idea we are going to develop.In order to develop this idea we need to answer certain question-

Mathematical model-

• What is the time required by model for every operation that a algorithm might perform.
• What should be the input data.
• How does our model relate to real computers.

Outline

• Formally define some basic terms
• mathematical model.
• Analysis Strategy.
• Examples of Algorithm and their analysis.
• Discussion of limitation of models.

ALGORITHMS

In mathematics, computer science, and related subjects, an algorithm is an effective method for solving a problem expressed as a finite sequence of instructions.

Each algorithm is a list of well-defined instructions for completing a task.

In Context of Computers-

To make a computer do anything, you have to write a computer program. To write a computer program, you have to tell the computer, step by step, exactly what you want it to do. The computer then "executes" the program, following each step mechanically, to accomplish the end goal.

When you are telling the computer what to do, you also get to choose how it's going to do it. That's where computer algorithms come in. The algorithm is the basic technique used to get the job done.

UNIT 1 INTRODUCTION

Introduction: Algorithms, analysis of algorithms, Growth of Functions, Master's Theorem,

Designing of Algorithms. Sorting and order Statistics: Heap sort, Quick sort, Sorting in Linear

time, Medians and Order Statistics.

Analysis And Design Of Algorithms-Overview

Welcome to the course on Design and Analysis of Algorithm.

In subsequent articles we will cover all the important topics in this course which help the student gating the concepts clearly.

First of all we are going to take the overview of the course and I am going to introduce you the main problem in the course & also the spirit of the course.

Algorithm

An algorithm (pronounced AL-go-rith-um) is a procedure or formula for solving a problem.

Given a set of problems, We have to solve the problem on a computer.We can solve most of the problems & design the algorithm.However awareness is needed to make a fast and optimized algorithm.

Designing a fast algorithm is a major challenge of the course.

Analysis And Design Of Algorithms-UPTU Syllabus

DESIGN & ANALYSIS OF ALGORITHMS (TCS-503)

Unit -I

Introduction: Algorithms, analysis of algorithms, Growth of Functions, Master's Theorem,

Designing of Algorithms. Sorting and order Statistics: Heap sort, Quick sort, Sorting in Linear

time, Medians and Order Statistics.

Unit -II

Advanced Data Structure: Red-Black Trees, Augmenting Data Structure. B-Trees, Binomial

Heaps, Fibonacci Heaps, Data Stricture for Disjoint Sets.

Unit -III

Advanced Design and Analysis Techniques: Dynamic Programming, Greedy Algorithms,

Amortized Analysis, Back Tracking.

Unit -IV

Graph Algorithms: Elementary Graphs Algorithms, Minimum Spanning Trees, Single-source

Shortest Paths, All-Pairs Shortest Paths, Maximum Flow, Traveling Salesman Problem.

Unit -V

Selected Topics: Randomized Algorithms, String Matching, NP Completeness, Approximation

Algorithms.

Object Oriented System (3rd sem)

What is OOS-

A software model or system designed using object oriented approach is basically a object oriented system

Object Oriented Approach

In software development, we generally uses either a function oriented approach or Object oriented Approach.

Function oriented approach is basically what you have done or observed while programming in C.

Our overall system is divided into functions that performs various operation on data.Function are the basic element of our system.

For eg. While you are going to build a software system for Library management.Using Function oriented approach while designing the system we try to identify the function making up the system.Some of the possible function might be-"returning of books by student to librarian","issuing of books","putting books on shelf" etc.

So while designing the actual system , we consider these system for carrying out the manipulation of data and providing the desired result.

Object Oriented Approach is something which is very easy to understand and implement. Actully all real world Problems can be viewed as object oriented.

Its a real world programming concept.

In this approach of design,we considers the object making up the system,and objects has the data and related function that can be used by it.

So take a real world problem for understanding it-

If you want to build a system for library management then the possible objects that make up the system are "student","librarian","shelf" etc.All these object has data(attributes of object) and methods(operations performed on data) with in them.