2D Parity Checking

#include<iostream>

#include<stdlib.h>

using namespace std;

#define maxlength 10

#define maxmessages 10

void initialize(int arr[][10],int m,int n)

{

for(int i =0;i<m;i++)

for(int j=0;j<n;j++)

{

arr[i][j] = rand()%2;

}

}

void print(int arr[][10],int m,int n)

{

for(int i =0;i<m;i++)

{  for(int j=0;j<n;j++)

{

cout<<arr[i][j]<<” “;

}

cout<<endl;

}

}

void addparbit(int arr[][10],int m,int n)  // Even Parity

{

for(int i=0;i<m;i++)

{

int count = 0;

for(int j=0;j<n;j++)

{

if(arr[i][j] == 1)

count++;

}

if(count%2 == 0)

arr[i][n] = 0;

else

arr[i][n] = 1;

}

}

void induceerror(int arr[][10],int m,int n)

{

int k1,k2;

k1= rand()%m;

k2 = rand()%n;

if(arr[k1][k2]==0)

arr[k1][k2]=1;

else

arr[k1][k2]=0;

cout<<“Inducing error at line : “<<k1<<endl;

}

void checkerror(int arr[][10],int m,int n)

{

for(int i=0;i<m;i++)

{

int count = 0;

for(int j=0;j<n;j++)

{

if(arr[i][j] == 1)

count++;

}

if(count%2 == 0 && arr[i][n] != 0)

{

cout<<“Error here at line : ” <<i;

}

else if(count%2 == 1 && arr[i][n] != 1)

{

cout<<“Error here at line : ” <<i;

}

 

}

}

 

int main()

{   int m,n,arr[maxmessages][maxlength];

cout<<“Enter total number of messages”;

cin>>m;

cout<<“Enter length of each message”;

cin>>n;

initialize(arr,m,n);

print(arr,m,n);

addparbit(arr,m,n);

print(arr,m,n+1);

induceerror(arr,m,n);

print(arr,m,n+1);

checkerror(arr,m,n);

return 0;

}

 

 

 

Arithmetic Coding

#include<iostream.h>

#include<stdio.h>

#include<conio.h>

struct node

{

char ch;

float start,end;

float p;

}n[30];

void sort(node n[], int m)

{

node temp;

//float small=n[0].p;

//int pos=0;

for(int i=0;i<m-1;i++)

{

for(int j=i+1;j<m;j++)

{

if(n[i].p<n[j].p)

{

temp=n[j];

n[j]=n[i];

n[i]=temp;

}

}

}

cout<<“\nSorted array is”;

for( i=0;i<m;i++)

{

cout<<“\n”<<n[i].ch;

}

}

void getpoint(node n[], int m)

{       int i=0;

n[0].start=0.0;

//int i=0;

for(int k=1;k<m;k++)

{

n[i].end=n[i].start+n[i].p;

n[k].start=n[i].end;

i++;

}

k–;

n[k].end=1.0;

}

node check(node n[],int m, char c)

{ node temp;

for(int i=0;i<m;i++)

{

if(c==n[i].ch)

{

temp=n[i];

}

}

return temp;

}

void display(node n[],int m)

{

for(int h=0;h<m;h++)

{

cout<<“\n character”<<n[h].ch;

cout<<“\n start point”<<n[h].start;

cout<<“\n end point”<<n[h].end;

}

}

void calc(node n[],int m,node x,float a)

{

n[0].start=x.start;

int i=0;

for(int k=1;k<m;k++)

{

n[i].end=n[i].start+n[i].p*a;

n[k].start=n[i].end;

i++;

}

k–;

n[k].end=x.end;

}

void main()

{

clrscr();

int m;

cout<<“enter the size of array”;

cin>>m;

cout<<“enter”;

for(int i=0;i<m;i++)

{

cin>>n[i].ch;

cout<<“\n p ??”;

cin>>n[i].p;

n[i].start=n[i].end=0.0;

}

sort(n,m);

getpoint(n,m);

display(n,m);

char str[30];

cout<<“enter string”;

gets(str);

fflush(stdin);

node x;

float a;

a=1;

for(i=0;i<m-1;i++)

{

clrscr();

x=check(n,m,str[i]);

a=x.end-x.start;

calc(n,m,x,a);

display(n,m);

getch();

}

cout<<“\n”<<n[m-1].start<<“_>”<<n[m-1].end;

getch();

}

 

 

Longest Common Subsequence

#include<iostream.h>
#include<conio.h>
#include<stdio.h>
int printlcs(char b[30][30],char x[], int m, int n)
{
if((m==0)||(n==0))
{
return 0;
}
if(b[m][n]==’*’)
{
cout<<“TEST”;
printlcs(b,x,m-1,n);
cout<<x[m];
}
else
{
cout<<“TEST”;
if(b[m][n]==’^’)
{
printlcs(b,x,m-1,n);
}
else
{
cout<<“test”;
printlcs(b,x,m,n-1);
}
}
}
void main()
{
clrscr();
char x[30], y[30],c[30][30],b[30][30];
int m,n;
cout<<“enter the length of strings”;
cin>>m>>n;
cout<<“enter string1”;
gets(x);
fflush(stdin);
cout<<“enter string 2”;
gets(y);
fflush(stdin);
for(int i=0;i<m;i++)
{
c[i][0]=0;
}
for(int j=0;j<n;j++)
{
c[0][j]=0;
}
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
if(x[i]==y[j])
{
c[i][j]=c[i-1][j-1]+1;
b[i][j]=’*’;
}
else
{
if((c[i-1][j]>c[i][j-1])||(c[i-1][j]==c[i][j-1]))
{
c[i][j]=c[i-1][j];
b[i][j]=’^’;
}
else
{
c[i][j]=c[i][j-1];
b[i][j]='<‘;
}
}
}
}
int h;
h=printlcs(b,x,m,n);
getch();
}

 

Theory:

http://www.algorithmist.com/index.php/Longest_Common_Subsequence

http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/

Prim’s Algorithm

#include<iostream.h>
#include<conio.h>
#include<stdio.h>
struct node
{
int index;
char ch;
int status;
char prev;
}v[10];
void update(node v[],node temp,int n)
{
for(int i=0;i<n;i++)
{
if(v[i].ch==temp.ch)
{
v[i].status=1;
}
}
}
node extractmin(int graph[10][10], node v[], int n)
{
node temp;
int min;
min=100;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if((v[i].status==1)&&(v[j].status==0))
{
if(min>graph[i][j])
{
min=graph[i][j];
v[j].prev=v[i].ch;
temp=v[j];
}
}
}
}
return temp;
}
void main()
{ clrscr();
int n,graph[10][10];
cout<<“enter n”;
cin>>n;
cout<<“enter graph”;
for(int i =0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>graph[i][j];
}
}
cout<<“enter vertices’ details”;
for(i=0;i<n;i++)
{
cout<<“enter vertex”;
cin>>v[i].ch;
v[i].status=0;
v[i].index=i;
v[i].prev=’r’;
}
int counter=0;
char s;
cout<<“enter source vertex”;
cin>>s;
for(i=0;i<n;i++)
{
if(s==v[i].ch)
{
v[i].status=1;
}
}
counter++;
char path;
int p=0;
node temp;
//char prev,recent,t;
//prev=s;
while(counter<n)
{
temp=extractmin(graph,v,n);
update(v,temp,n);
cout<<“\n “<<temp.prev<<“->”<<temp.ch;
//t=getprevious(v,graph,prev,temp,n);
counter++;
}
//cout<<“path is\n “;
//puts(path);
getch();
}

 

Theory:

http://students.ceid.upatras.gr/~papagel/project/prim.htm

http://lcm.csa.iisc.ernet.in/dsa/node183.html

Dijkstra’s Algorithm

#include<iostream.h>
#include<conio.h>
#include<stdio.h>
char path[10];
int p=0;
struct node
{
int weight;
char ch;
int index;
int status;
}v[10];
node extractmin(node v[], int n)
{
int min=300;
node temp;
for(int i=0;i<n;i++)
{
if((v[i].weight<min)&&(v[i].status==0))
{
min=v[i].weight;
temp=v[i];
}
}
return temp;
}
void update(node v[],node s,int n)
{
for(int i=0;i<n; i++)
{
if(v[i].ch==s.ch)
{
v[i].status=1;
path[p]=v[i].ch;
p++;
}
}
}
void main()
{
clrscr();
int graph[10][10];
int n;
cout<<“enter the number of vertices”;
cin>>n;
cout<<“enter the matrix”;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>graph[i][j];
}
}

for(i=0;i<n;i++)
{
cout<<“enter the weight”;
cin>>v[i].weight;
cout<<“enter the name”;
cin>>v[i].ch;
v[i].index=i;
v[i].status=0;
}
node s;
int wtest;
int counter =0;
while(counter<n)
{
s=extractmin(v,n);
update(v,s,n);
for(i=0;i<n;i++)
{
wtest=s.weight+graph[s.index][i];
if(wtest<v[i].weight)
{
v[i].weight=wtest;
}
}
counter++;
}
cout<<“the weights are”;
for( i=0;i<n;i++)
{
cout<<“\n “<<v[i].weight;
}
cout<<“path is”;
puts(path);
//cout<<“hello”;
getch();
}

 

For theory:

http://www.cs.auckland.ac.nz/~jmor159/PLDS210/dijkstra.html

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/dijkstraAlgor.htm

Bellman Ford

#include<iostream.h>
#include<stdio.h>
#include<conio.h>
struct node
{
int index;
char ch;
char prev;
int weight;
int status;
}v[10];
node getprev(node x,int n)
{
for(int i=0;i<n;i++)
{
if(v[i].ch==x.prev)
{
break;
}
}
return v[i];
}
void relax(node v[],int graph[10][10], int n, int counter)
{
int wtest;
/*int min;
for(int i=0;i<n;i++)
{min=100; */
for(int j=0;j<n;j++)
{
wtest=v[counter].weight+graph[counter][j];
if(wtest<v[j].weight)
{
v[j].weight=wtest;
v[j].prev=v[counter].ch;
}
}
}
void main()
{
clrscr();
int n;
int graph[10][10];
cout<<“enter n”;
cin>>n;
cout<<“enter grAPH”;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>graph[i][j];
}
}
cout<<“enter vertex details”;
for(i=0;i<n;i++)
{
cout<<“\n name”;
cin>>v[i].ch;
cout<<“\n weight”;
cin>>v[i].weight;
v[i].status=0;
v[i].index=i;
v[i].prev=’r’;
}
int counter;
counter=0;
for(i=1;i<n;i++)
{
counter=0;
while(counter<n)
{
relax(v,graph,n,counter);
counter++;
}
}
node p;
int exp;
for(i=0;i<n;i++)
{
p=getprev(v[i],n);
//exp=v[i].weight+ graph[p.index][i];
if(p.weight>v[i].weight)
{
cout<<“\n negative cycle”;
cout<<“\n”<<v[i].prev<<“->”<<v[i].ch;
}
if(v[i].weight<0)
{
cout<<“\n “<<v[i].prev<<“->”<<v[i].ch;
}
}
cout<<“TEST”;
for(i=0;i<n;i++)
{
cout<<“\t “<<v[i].weight<<“\t”<<v[i].prev;
cout<<“\n”;
}
getch();
}

Coding Troll

 

Parabola – Midpoint Approach 1st order

#include<iostream.h>

#include<graphics.h>

#include<stdio.h>

#include<conio.h>

void put_pixel(int x, int y)

{

putpixel((x+300),(240-y),15);

putpixel((x+300),(240+y),15);

}

void para(int cx, int cy, double a)

{

setcolor(BLUE);

line(300,0,300,479);

setcolor(RED);

line(0,240,639,240);

double x=0,y=0;  /* initial coorodinates */

double d1;

d1 = (2*a) – 1;

put_pixel(x,y);

while(y<= (2*a*1.0))

{

if(d1<0)

{

d1+= 4*a-3-2*y;

x++;

y++;

}

else

{

d1-= 3 + 2*y;

y++;

}

put_pixel(x,y);

}

d1 = (4.0*a*(x+1) – (y+0.5)*(y+0.5) );

while( y < 220 )

{

if(d1<0)

{

d1+= 4*a;

x++;

}

else

{

d1+= 4.0*a – 2 – 2.0*y ;

x++;

y++;

}

put_pixel(x,y);

}

}

void main()

{

clrscr();

double a;

cout<<“Enter a : “;

cin>>a;

int gdriver = DETECT, gmode;

initgraph(&gdriver, &gmode, “c:\\tc\\bgi”);

para(0,0,a);

getch();

closegraph();

}

Hyperbola- Bresenham’s Approach

#include<iostream.h>

#include<graphics.h>

#include<stdio.h>

#include<conio.h>

 

void plotpixel(int x, int y)

{

putpixel((x+300),(240-y),15);

putpixel((-x+300),(240-y),15);

putpixel((x+300),(240+y),15);

putpixel((-x+300),(240+y),15);

}

 

void hyper(int cx, int cy, double a,double b)

{

setcolor(BLUE);

line(300,0,300,479);

setcolor(RED);

line(0,240,639,240);

double x=a,y=0;  /* initial coorodinates */

 

double d1 = (2*a*a) – (b*b) – (2*a*b*b);

plotpixel(x,y);

 

while((a*a*y) <= (b*b*x))

{

if(d1<= (-1*b*b*0.5))

{

d1+= 2*a*a*(2*y+3);

plotpixel(x,y);

y++;

}

else

{

d1+= 2*a*a*(2*y+3) – 4*b*b*(x+1);

plotpixel(x,y);

x++;

y++;

}

//plotpixel(x,y);

}

 

d1 = a*a*(y+1)*(y+1) + a*a*y*y + 2*a*a*b*b – 2*a*a*b*b*(x+1)*(x+1);

 

while(y<220)

{

if(d1<= (a*a*0.5))

{

d1+= a*a*4*(y+1) – 2-a*a*b*b*(2*x+3)*(2*x+3);

y++;

x++;

}

else

{

d1+= -2.0*b*b*a*a*(2*x+3);

x++;

}

plotpixel(x,y);

}

 

}

 

void main()

{

clrscr();

double a,b;

cout<<“Enter a and b : “;

cin>>a>>b;

 

int gdriver = DETECT, gmode;

initgraph(&gdriver, &gmode, “c:\\tc\\bgi”);

hyper(0,0,a,b);

getch();

closegraph();

}

 

 

 

 

Hyperbola-midpoint approach 1st order

#include<graphics.h>

#include<conio.h>

#include<stdio.h>

#include<dos.h>

#include<stdlib.h>

 

void main()

{

int gd=DETECT;

int gm;

initgraph(&gd,&gm,”c:\\tc\\bgi”);

float x,y;

float xc,yc;

float d,fx,fy,b,a;

d=b*b*(a+0.5)*(a+0.5)-a*a-a*a*b*b;

printf(“enter centre (xc,yc)\n”);

scanf(“%f %f”,&xc,&yc);

printf(“enter a & b”);

scanf(“%f %f”,&a,&b);

x=a;

y=0;

fx=2*b*b*a;

fy=0;

setcolor(MAGENTA);

line(0,240,640,240);

line(320,0,320,480);

while(abs(fy)<=fx)

{

if(d>=0)

{

d=d-a*a*(2*y+3);

}

else

{

d=d-a*a*(2*y+3)+b*b*(2*x+2);

x++;

fx=fx+2*b*b;

}

y++;

fy=fy+2*a*a;

putpixel(x+320+xc,240-y-yc,GREEN);

putpixel(x+320+xc,240+y-yc,GREEN);

putpixel(-x+320+xc,240-y-yc,GREEN);

delay(20);

putpixel(-x+320+xc,240+y-yc,GREEN);

delay(20);

}

x=p/2;

y=p;

d=-p;

while(y<3*p)

{

x++;

if(d>=0)

{

d=d-2*p;

}

else

{

d=d+2*y+2-2*p;

y++;

}

putpixel(x+320+xc,240-y-yc,RED);

delay(20);

putpixel(x+320+xc,240+y-yc,RED);

delay(20);

}

getch();

}