## Friday, 30 November 2012

### Different Types of Automata in Language Theory

It is very important for every one interested in Computer Science to understand various Automata in language theory. Often there is a big confusion about the relationship between various Automaton. There are different Automata, but the most important ones with practical applications are the following. Turing Machine (TM), Linear Bounded Automata (LBA), Push Down Automata (PDA) and Finite Automata (FA).

Each one of theses Automata are having a Deterministic and non deterministic variant associated with them. It is often confusing since there are eight different types of Automata to account for. Here I have included simple Venn diagrams to show the hierarchy of Automata. The outer most set is the one with the most power. Here power is the ability to accept strings belonging to complicated languages. The Automata with more power can accept more complicated strings. Remember here I have used layman's terms.

The Venn diagram given below shows a power comparison between the four types of Automata. A hierarchy of different Automata

Now let us see how a Deterministic Turing Machine (DTM) is related to  a Non deterministic Turing Machine (NTM). The Venn diagram given below gives an idea about the two Automata. Turing Machine Hierarchy

Next is the least known of all the four Automata. The Linear Bounded Automata (LBA). Well here we don't have a clear answer about the relationship between a Deterministic LBA (DLBA) and a Non deterministic LBA (NLBA). It is still an unsolved problem in Computer Science. So I give a Venn diagram showing both the possibilities. Here is an Open Problem. You could give it a try.
Now we have Push Down Automata (PDA). The relationship between Deterministic PDA (DPDA) and Non deterministic PDA (NPDA) is shown in the Venn diagram given below. DPDA and NPDA are having different powers

Finally we have Finite Automata. Both Non deterministic Finite Automata (NFA) and Deterministic Finite Automata (DFA) are having equal powers. The Venn diagram below shows their relationship. NFA and DFA

The last figure given below shows the relationship between various Grammars associated with the above mentioned Automaton. Hierarchy of Grammars

## Wednesday, 28 November 2012

### Beamer Template for Simple Presentations.

Research communities all over the world prefers presentations created using Latex. But most of us still use prefer Proprietary software like MS Word. The main reason for such preferences is not often the ignorance regarding open source alternatives. Many of us are simply afraid of working with a new technology, especially if it involves a few commands.

LATEX is a very good document preparation tool. Once you create a few documents using LATEX you will enjoy working with it. To create presentations LATEX provides a class called Beamer. Here I have included a Template for creating simple presentations. I have also included a presentation in PDF format which was created by running the program with Beamer Theme "beamerthemesidebar". Please compile the Program twice. Only then you will get a correct Table of Contents listing.

## Tuesday, 27 November 2012

### Latex Template for IEEE Conference Papers

It is difficult to produce quality results in research. But some times it is even more difficult to produce a good quality IEEE Format paper. You have to worry about the font styles, alignment, margins and what not if you are using MS Word or some such word processor. If you are using Latex often you have to worry about different commands and packages. So here I try provide a simple LATEX Template for creating IEEE Conference Papers. I have tried to make it as simple as possible, and I have also given sufficient comments where ever required. Here I give two links the first one is to the tex file which you need to run in Texmaker. If you want you can also download the pdf file you will get when you run the tex file without making any modifications.

## Sunday, 11 November 2012

### Function Pointers in C

//Program illustrates how function pointers are used to call various functions.

#include<stdio.h>
void apple(int x)
{
int i;
printf("\n From Function apple\n");
for(i=0;i<3;i++)
{
printf("%d\t",x[i]);
}
}

void ball(int x)
{
int i;
printf("\n From Function ball\n");
for(i=0;i<3;i++)
{
printf("%d\t",x[i]);
}
}

void cat(int x,void (*fp1)(int ))

/*cat is a function which receives a 1 Dimensional integer array and a function pointer as arguments*/

printf("\n\n From function cat\n");
(*fp1) (x);      /*Calling function pointed by function pointer fp1 with array x as argument*/
}

int main()
{

int arr1={111,222,333};
int arr2={444,555,666};

void (*e) (int );
/* 2 Function Pointers e and e which can point to a function with
one Dimensional integer array as argument and returns void          */

void (*fp) (int , void (*e) (int ) );
/* Function Pointer fp which can point to a function with
one Dimensional integer array and function pointer as arguments and returns void        */

e=apple;              /*function pointer e points to function apple*/
e=ball;                 /*function pointer e points to function ball   */
fp=cat;                     /*function pointer fp points to function cat       */

(*e) (arr1);          /*caling function apple with array arr1 as argument*/
(*e) (arr2);          /*caling function ball with array arr2 as argument   */

(*fp) (arr1,e);      /*caling function cat with array arr1 and function pointer e as arguments */
(*fp) (arr2,e);      /*caling function cat with array arr2 and function pointer e as arguments */
(*fp) (arr1,apple);
/*caling function cat with array arr1 and function pointer using function name apple as arguments */
(*fp) (arr2,ball);
/*caling function cat with array arr2 and function pointer using function name ball as arguments    */
return 0;
}

### Generic Classes in C++

//Program illustrates the working of generic classes in C++.
#include<iostream>
#include<fstream>
using namespace std;

template <class x,class y> void swap(x *a,y *b)
{
x temp;
temp=*a;
*a=*b;
*b=temp;
}

int main()
{
int n1=10,n2=20;
float f1=11.11,f2=22.22;
cout<<"\nn1 is: "<<n1<<"\nn2 is: "<<n2;
cout<<"\nf1 is: "<<f1<<"\nn2 is: "<<f2;
swap(&n1,&n2);
swap(&f1,&f2);
cout<<"\nn1 is: "<<n1<<"\nn2 is: "<<n2;
cout<<"\nf1 is: "<<f1<<"\nn2 is: "<<f2;
return 0;
}

### Program illustrating Reinterpret Cast in C++

//Program illustrates the working of reinterpret_cast keyword in C++
#include<iostream>
#include<typeinfo>
using namespace std;

int main()
{

char *s="Hello Friends";
int i;

i=reinterpret_cast<int>(s);
cout<<"\ni is: "<<i;
cout<<"\ns is: "<<s;

return 0;
}

### Program illustrating Static Cast in C++

//This Program illustrates how static_cast keyword is used in C++
#include<iostream>
#include<typeinfo>
using namespace std;

int main()
{

int i;
const int x=100;
i=static_cast<int>(x);
cout<<"\ni is: "<<i;

return 0;
}

### Program illustrating Dynamic Cast in C++

//Program illustrates how dynamic_cast keyword in C++ is used

#include<iostream>
#include<typeinfo>
using namespace std;

class a
{
public:
virtual void show()=0;
};
class b : public a
{
public:
void show()
{
cout<<"\nshow() in class B\n";
}
};
class c : public a
{
public:
void show()
{
cout<<"\nshow() in class C\n";
}
};
class d : public a
{

public:
void show()
{
cout<<"\nshow() in class D\n";
}
};
int main()
{
int i,j;
b b1,b2;
c c1;
d d1;
a *a1={&b1,&c1,&d1,&b2};

for(i=0;i<4;i++)
{
b *b3=dynamic_cast<b *>(a1[i]);
if(b3)
{
cout<<"\nFrom B\n" ;
b3->show();
}
else
{
cout<<"\nNot From B\n";
cout<<"a1["<<i+1<<"] is pointing to"<<typeid(*a1[i]).name()<<"\n";
a1[i]->show();
}

}

return 0;
}

## Saturday, 10 November 2012

### Program illustrating Namespaces in C++

//The following programs illustrates namespaces in C++
//Compare the syntax of the three Programs you will understand the scope of namespaces in C++
//Program 1 begins here.

#include<iostream>
#include<typeinfo>
using namespace std;
namespace{
int i=444;
}
namespace ns1
{

int j=555;
namespace ns2
{
int k=666;
}
}

int main()
{
cout<<"\ni is: "<<i;
cout<<"\nj is: "<<ns1::j;
cout<<"\nk is: "<<ns1::ns2::k;
return 0;
}

//Program 2 Begins here.
#include<iostream>
#include<typeinfo>
using namespace std;
namespace{
int i=444;
}
namespace ns1
{

int j=555;
namespace ns2
{
int k=666;
}
}
using namespace ns1;
using namespace ns1::ns2;
int main()
{
cout<<"\ni is: "<<i;
cout<<"\nj is: "<<j;
cout<<"\nk is: "<<k;
return 0;
}

//Program3 begins here.
#include<iostream>
#include<typeinfo>
using namespace std;
namespace{
int i=444;
}
namespace ns1
{

int j=555;
namespace ns2
{
int k=666;
}
}

using namespace ns1::ns2;
int main()
{
cout<<"\ni is: "<<i;
cout<<"\nj is: "<<ns1::j;
cout<<"\nk is: "<<k;
return 0;
}

## Friday, 9 November 2012

### Why we must support Distributed Computing Projects?

When I had a chat with some of my friends recently, I had a shocking revelation. Not many of us are familiar with distributed computing projects. What is a distributed computing project and why we must support them?

Well a distributed computing project tries to solve a big problem by dividing it into a number of small sub problems and then by solving and combining the sub problem we will get a solution for the first problem. Some of the problems can be easily divided into sub problems for solution. Consider the problem of finding the factors of a very large number. The problem can be solved using a large number of computers by assigning each computer with a range of values to check whether it can be a factor of the given large number.

Some of the practical problems need a very large amount of computing power. So one solution is to divide the problem into a large set of sub problems each of which can be solved by personal computers or laptops without much power. There are hundreds of distributed computing projects in need of our computing resources which are freely available and often under utilized. All we need to do is go to a particular projects home page and download the program. Most of the programs are very small in size. They will run automatically in your computer and once in a while they will communicate with the server to send back the results and get new assignments.There are no hidden viruses or trojans and with a single click you can uninstall the programs.

The two projects I run on my computer are The Great Internet Mersenne Prime Search (GIMPS) and Folding@home (FAH or F@h).

GIMPS tries to identify large Mersenne prime. A clear understanding of Mersenne primes will help us develop better cryptographic algorithms.

Wikipedia Article on GIMPS

FAH is a project for disease research that simulates protein folding. The results are very useful in cancer treatment. The idle CPU in your computer can be used as an effective tool to fight cancer.

Wikipedia Article on FAH

There are other interesting distributed computing projects also. The Link to the wikipedia article is given below.

Wikipedia article on Distributed computing Projects

### Program illustrating Const Cast in C++

//The following Program illustrates the working of const_cast

#include <iostream>
using namespace std;

void print (char * str)
{
cout<<"\nFrom Function print\n";
cout << str;
}

int main () {
const char * c = "Hello Friends";
cout<<"\nFrom main Function\n";
cout<<c;
print ( const_cast<char *>(c) );
return 0;
}

//The following given below is equivalent to the above Program

#include <iostream>
using namespace std;

void print (char * str)
{
cout<<"\nFrom Function print\n";
cout << str;
}

int main () {
const char * c = "Hello Friends";
cout<<"\nFrom main Function\n";
cout<<c;
print ( (char *)(c) );
return 0;
}

// The Program given below will not work.

#include <iostream>
using namespace std;

void print (char * str)
{
cout<<"\nFrom Function print\n";
cout << str;
}

int main () {
const char * c = "Hello Friends";
cout<<"\nFrom main Function\n";
cout<<c;
print ( c );
return 0;
}

### Xgraph for plotting in NS-2

After running your NS-2 program you will have a trace file as output.

Let us assume the name of the output file is "trace1.tr"

The trace file might look like below

+ 1             0 2 cbr 210 ------- 0 0.0 3.1 0 0
- 1              0 2 cbr 210 ------- 0 0.0 3.1 0 0
r  1.00212  0 2 cbr 210 ------- 0 0.0 3.1 0 0
+ 1.00212  0 2 cbr 210 ------- 0 0.0 3.1 0 0
+ 1.055      0 3 cbr 210 ------- 0 0.0 3.1 0 0

I am not explaining the meaning of the trace file. Instead I am giving instructions to use xgraph to draw a graph involving data extracted from the trace file.

To use xgraph we need 2 columns of data. The Unix command called "cut" is used for this purpose.

Open terminal and type the following commands

###############################

cut  -d  " "  -f  2  trace1.tr  >  file1

cut  -d  " "  -f  6  trace1.tr  >  file2

paste      file1     file2    >   output

xgraph   output

###############################

This will extract columns 2 and 6 and then draw a graph using the xgraph utility.

for "cut" keyword -d specifies the delimiter between columns.
Here the delimiter is white space ("  ").
-f specifies the column number of the data to be extracted.

### 1 D and 2 D array pointers in C

#include<stdio.h>
void main()
{
int a={111,222,333,444,555,666,777,888,999};
int i,j,*p;
int (*m);  /* Pointer to a 2 Dimensional Array*/
int (*n);     /* Pointer to a 1 Dimensional Array*/
p=a;
m=a;
n=a;

for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
printf("%d ",*p++);
}

}
printf("\n");

for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
printf("%d ",a[i][j]);
}

}
printf("\n");

for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
printf("%d ",*(*(*m+i)+j));
printf("%u \n",m+i);
}
}
printf("\n");

for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
printf("%d ",*(*(n+i)+j));
printf("%u \n",n+i);
}
}
}

### C Program to Print Enumerated Variables

#include<stdio.h>
#include<io.h>
void main()
{
enum a{x=111,y=222,z=333};
enum a b;
b=z;
printf("\nThe enum x is %d",x);
printf("\nThe enum y is %d",y);
printf("\nThe enumeration variable b is %d",b);
}

/* You don't need typecasting to print enumerated variables. But the following Program will also work. */

#include<stdio.h>
#include<io.h>
void main()
{
enum a{x=111,y=222,z=333};
enum a b;
b=z;
printf("\nThe enum x is %d",(int)x);
printf("\nThe enum y is %d",(int)y);
printf("\nThe enumeration variable b is %d",(int)b);
}