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

}

 

 

Run Length Encoding

#include<iostream.h>

#include<conio.h>

#include<stdio.h>

#include<string.h>

int getcount(char str[],int i,int j)

{ int count=1;

while(str[i]==str[j])

{

count++;

j++;

}

return count;

}

void display(char str[],int i,int c)

{

if(c>3)

{

cout<<“!”<<c<<” “<<str[i];

}

else

{

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

{

cout<<“\t “<<str[i];

}

}

}

void main()

{

clrscr();

char str[30];

int m;

cout<<“enter string”;

gets(str);

fflush(stdin);

m=strlen(str);

int i=0;

int c,j;

while(i<m)

{

j=i+1;

if(str[i]==str[j])

{

c=getcount(str,i,j);

display(str,i,c);

i=i+c;

}

else

{

cout<<“\t”<<str[i];

i++;

}

}

getch();

}

 

Theory:

http://netghost.narod.ru/gff/graphics/book/ch09_03.htm

 

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

FIFO-Disk Scheduling

#include<iostream.h>
#include<conio.h>
void sort(int d[],int n)
{
int temp,small,pos;
for(int i=0;i<n-1;i++)
{
small=d[i];
pos=i;
for(int j=i+1;j<n;j++)
{
if(small>d[j])
{
small=d[j];
pos=j;
}
}
temp=d[pos];
d[pos]=d[i];
d[i]=temp;
}
}
void main()
{
clrscr();
int head,d[20],n;
cout<<” enter number of disk schedulings you want to do”;
cin>>n;
cout<<“enter head”;
cin>>head;
for(int i=0;i<n;i++)
{
cout<<“\n enter”;
cin>>d[i];
}
sort(d,n);
cout<<“order is”;
for(int j=0;j<n;j++)
{
cout<<“\n”<<d[j];
}
getch();
}

 

 

First Program

#include<iostream.h>
#include<conio.h>
void main()
{
clrscr;
cout<<“this is my first program”;
getch();
}

Ellipse- Computer Graphics

#include<iostream.h>
#include<graphics.h>
#include<stdio.h>
#include<conio.h>
#include<dos.h>

void plotpixel(int x, int y)
{
// delay(10);
putpixel((x+320),(240-y),15);
putpixel((-x+320),(240-y),15);
putpixel((x+320),(240+y),15);
putpixel((-x+320),(240+y),15);

}

void ell(float a, float b)
{
float x=0,y=b;

float d = a*a*(0.25-b) + b*b;

setcolor(RED);
line(320,0,320,480);
setcolor(BLUE);
line(0,240,640,240);
setcolor(WHITE);

plotpixel(x,y);

while((b*b*(x+1))<=(a*a*(y-0.5)))
{
if(d<0)
{
d+= 1.0*b*b*(3+2*x);
x++;
}
else
{
d+= b*b*(3+2*x)*1.0+2*1.0*a*a*(1-y);
x++;
y–;
}
plotpixel(x,y);
}

d = b*b*(1.0*x+0.5)*(1.0*x+0.5)+1.0*a*a*(y-1)*(y-1)-1.0*a*a*b*b;

while(y>=0)
{
if(d<0)
{
d+= 2.0*b*b*(1+x)+1.0*a*a*(3-2*y);
x++;
y–;
}
else
{
d+= a*a*(3-2*y)*1.0;
y–;
}
plotpixel(x,y);
}

}

void main()
{
clrscr();

float a,b;
cout<<“Enter a & b : “;
cin>>a>>b;

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

ell(a,b);
getch();
closegraph();
}