Laymans Views

Flickr

2010-04-21T23:41:00.001-07:00

This is a test post from , a fancy photo sharing thing.

Art of computer programming -Sorting #5

2010-03-01T03:51:00.000-08:00

Improvements that can be made on bubble sort

There are basically 2 improvements that you can make on bubble sort.

One, you can eliminate certain comparisons. For example if 2 elements i and j in an array don't change their respective positions in 2 simultaneous passes during a bubble sort. Then it means that the values are in their final positions. Such elements can be left alone when comparing.

Another distant possibility is that we can shift the base of the array left or right when we want to shift a position to left or right. This will help us in doing lesser number of comparisons. But whatever we do, it does not make the bubble sort any better than a selection sort or an insertion sort.

So layman tells you to quit using the bubble sort for practical purposes.

Thanking you,
Layman

Read firefox bookmarks using Java

2009-12-14T07:19:00.001-08:00

I've often seen people asking in various forums "how do we read firefox bookmarks from Java/C# ? ". It seemed like an interesting question and I ended up solving the question in around 2 hrs. A little bit of reading about the firefox database will be necessary. You can get that here. Now for the implementation you will need to add the jar file. You can get it here. You can add the external jar to your project and then compile the following code. The implementation only reads and lists out some fields in places.sqlite. You can modify the query and do various other things.

import java.sql.*;

public class firefoxBookmarksReader {
public static void main(String[] args) throws Exception {
Class.forName("org.sqlite.JDBC");
Connection conn = DriverManager.getConnection("jdbc:sqlite:/home/deepak/.mozilla/firefox/yvf7p20d.default/places.sqlite//"); // replace the path appropriately depending on the location of places.sqlite
if(conn==null)
{
System.out.println("ERROR");
}
System.out.println(conn.toString());

Statement stat = conn.createStatement();

ResultSet rs = stat.executeQuery("select * from moz_bookmarks;");
while (rs.next()) {
System.out.println("id = " + rs.getString("id"));
System.out.println("keyword = " + rs.getString("keyword_id"));
System.out.println("title = " + rs.getString("title"));
}
rs.close();
conn.close();
}
}

Thanks,
Layman

Go on cygwin

2009-12-08T23:00:00.000-08:00

I have a crap windows machine at my workplace and I wanted to do some work on Go during my free time. I had cygwin running and I could successfully install Google go on cygwin. So I thought I'll put this as a post.

You have to get the repository. But you wont have hg command installed(in most cases)
If you have already installed hg command for cygwin skip to step 2

1. Do the folowing commands
$ wget http://peak.telecommunity.com/dist/ez_setup.py
$ python ez_setup.py
$ easy_install -U mercurial
$ chmod +x /usr/lib/python2.5/site-packages/mercurial-1.0-py2.5-cygwin-1.5.25-i686.egg/mercurial/*.dll

2. Now that you have hg command on your machine. Do the following command.
$ hg clone https://golang-on-cygwin.googlecode.com/hg/ golang-on-cygwin

3. Now you have to setup certain environment variables.
export GOROOT=/path/to/golang-on-cygwin
export GOARCH=386
export GOOS=linux
export GOBIN=/path/to/your/local/bin
export PATH=$PATH:$GOBIN

4. Change to the source directory and run the all.bash script
cd $GOROOT/src
./all.bash

Installation will succeed and you can start with Google go

Thanks,
Layman

Thread, semaphore, signals example in C

2009-12-03T20:29:00.000-08:00

I got this question by chance. It was about creating 2 threads that would run in such a way that if one thread prints a value i, the next thread should print a value i+1.

The pthread_create() function is used to create a new thread, with attributes specified by attr, within a process. If attr is NULL, the default attributes are used. If the attributes specified by attr are modified later, the thread's attributes are not affected. Upon successful completion, pthread_create() stores the ID of the created thread in the location referenced by thread.

The pthread_join() function suspends the execution of the calling thread until the thread identified by the thread identifier terminates, either by calling pthread_exit() or by being canceled.

For our given problem we need the increment and print action for each thread to be done as atomic actions. No context switch should happen these operations. If that happens we may not get the desired result. In case a context switch happens after a read in thread one, then thread 2 might print the incremented value and thread 1 will print the old value, and there are other possibilities as well.Hence the use of semaphore cannot be avoided.

Use of SIGINT (Cntr+C) is used to quit the program.

#include < stdio.h >
#include < pthread.h >
#include < semaphore.h >
#include < signal.h >

sem_t semname;
int qval=1;

void *func1(void *arg) {
while(qval) {
sem_wait(&semname);
printf("Thread one prints # %d\n",(*(int *)(arg))++);
sem_post(&semname);
sleep(1);
}
}
void *func2(void *arg) {
while(qval) {
sem_wait(&semname);
printf("Thread two prints # %d\n",(*(int *)(arg))++);
sem_post(&semname);
sleep(1);
}
}
void quit() {
qval=0;
}

main() {
signal(SIGINT,quit);
sem_init(&semname,0,1);
int i=0;
pthread_t thread1,thread2;
pthread_create(&thread1,NULL,func1,&i);
pthread_create(&thread2,NULL,func2,&i);
pthread_join(thread1,&i);
pthread_join(thread2,&i);
printf("\nQuiting...\n");
return 0;
}

Thanks
Layman

Trie datastructure C example

2009-12-02T04:24:00.000-08:00

This post is about the trie datastructure. Here we are trying to do a lexicographic trie. It can store all the words of a dictionary in an efficient manner. In the lexicographic trie datastructure each node has 26 pointers. Each pointers represent a letter. So to store "lay" , the system will first create a path from pointer for letter l to a new node(call it ptr). Then it makes a new node and makes the ptr's pointer for letter a point to this new node and so on. The advantage is that many words start with the same substring (eg new and neo). So here the common part "n" & "e" is stored only once. Hence lesser storage space and efficiency. In terms of computational speed searching is much faster as each time we can eliminate 25 links and hence it must be log n to the base 26. This is used commonly to implement dictionaries etc.
See the code now.

CODE

#include < stdio.h >
#include < stdlib.h >
#include < string.h >

struct diction
{
struct diction *alpha[26];
int flag;
};
typedef struct diction dic;

dic *root;
int maptoptr(char a)
{
char j='a';
int i;
for(i=0; i<26 a="'a';" root="(dic" i="0;i<26;i++,a++)" t="maptoptr(a);">alpha[t]=NULL;
}
}

void insert(char ip[])
{
dic *ptr=root;
int t;
int f=0;//false
int i=0;

t=maptoptr(ip[i]);
while(ptr->alpha[t]!=NULL && f==0) //not finished searchin and if there is a path with current letter
{
if(ip[i]=='\0' && ptr->flag==1)
{
f=1;//true
}
else
{
ptr=ptr->alpha[t];
i++;
}
t=maptoptr(ip[i]);
}
if(f==1)
{
printf("Already exists\n");
}
else
{
dic *ptr1=NULL;
char temp='a';
int j;
while(ip[i]!='\0')
{
temp='a';
ptr1=(dic *)malloc(sizeof(dic));
for(j=0;j<26;j++,temp++) t="maptoptr(temp);">alpha[t]=NULL;
}
ptr1->flag=0;
t=maptoptr(ip[i]);
ptr->alpha[t]=ptr1;
ptr=ptr1;
i++;
}
ptr->flag=1;
}
}
void search(char ip[])
{
int i=0,f=1;
int t;
dic *ptr=root;
while(ip[i]!='\0'&& f==1)
{
t=maptoptr(ip[i]);
if(ptr->alpha[t]==NULL)
{
f=0;
i++;
break;
}
ptr=ptr->alpha[t];
i++;
}
if(f==1 && ip[i]=='\0' && ptr->flag==1)
printf("\nFound\n");
else
printf("\nNot found\n");
}

void bt_free(dic *ptr)
{
int i=0,t;
char a='a';
if(ptr==NULL)
return;
for(i=0;i<26;i++,a++) t="maptoptr(a);">alpha[t]!=NULL)
{
bt_free((ptr->alpha[t]));
}
}
free(ptr);
}
main()
{
char a[25];
printf("Enter the word to insert : ");
gets(a);
createroot();
insert(a);
printf("Enter another word to insert : ");
gets(a);
insert(a);
printf("Enter the word to be searched : ");
gets(a);
search(a);
bt_free(root);
}

OUTPUT

$ ./a.exe
Enter the word to insert : layman
Enter another word to insert : laymansviews
Enter the word to be searched : layman

Found

Art of computer programming -Sorting #4

2009-11-25T21:48:00.001-08:00

Bubble sort
Bubble sort is the most well known sort. The idea of bubble sort is very straight forward. We compare adjacent elements and rearrange them. So element 1 and element 2 are compared and if element 1 is > element 2 then they are swapped, next element 2 and element 3 are compared and so on. In the first pass the largest element will be swapped to position n-1. In the second pass second largest element will reach n-2 etc. So in the nth pass ith largest element will reach n-i. There are a total of n passes. Now there are very little interesting things about this sort.

Point to note
The algorithm is inefficient for small and large lists. For small lists insertion sort maybe used and O(n^2) sorting is not recommended for large lists.
Knuth says that "the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems"
Bubble sort is 40% slower than selection sort and 5 times slower than insertion sort.

Algorithm

procedure bubbleSort( A : list of sortable items ) defined as:
 do
   swapped := false
   for each i in 0 to length(A) - 2 inclusive do:
     if A[i] > A[i+1] then
       swap( A[i], A[i+1] )
       swapped := true
     end if
   end for
 while swapped
end procedure

Worst case performance : O(n^2)
Best case performance  : O(n)
Average case performance : O(n^2)
Worst case space complexity:  O(1)

Thanking you,
Layman

C/C++ teaser

2009-11-19T18:20:00.000-08:00

This is not very difficult. But just have a look.

1. Predict the outcome
#include < stdio.h >
main()
{
int a=0;
printf("%s",a);
}

2. Predict the outcome
#include < stdio.h >
main()
{
int arr[]={2,3,4,5,6};
int *iptr=arr;
iptr++;
printf("%d",*(iptr+i));
arr++;
printf("%d",*(arr+i));
}

3. Predict the outcome
#include < stdio.h >
main()
{
int arr[]={2,3,4,5,6};
int *iptr=arr;
int i=0;
printf("%d,%d%d,%d",*(iptr+i),i[arr],arr[i],*(arr+i));
}

Please answer the questions as comments. The answers will be posted soon.

Thanks
Layman

Art of computer programming -Sorting #3

2009-11-18T21:28:00.000-08:00

Shell sort
For any sorting algorithm that moves only one position at a time , then the running time will always be proportional to n^2. Hence the idea was struck to make larger leaps rather than small ones. The small leaps is one of the prime reasons for insertion sort's low efficiency. And Donald Shell proposed shell sort.
Now you will be wondering how to choose he leap/step size. In shell sort we can start with an arbitrary step size in the first pass, after every pass the step size decreases. Hence shell sort is also known as decreasing increment sort. We'll take an example. In the first pass, let the step size be 8.
So during first pass element 0 is compared with element 8, element 16 , element 24.....element n.....element( n+8) etc. During second pass the increment is reduced to 4, so element 0 is compared with element 4, element 8........element n, element(n+4) etc. In the third pass increment size be 2, comparison will be between element 0, element 2, element 4....element n,element( n+2) etc. And finally increment becomes 1 in the last pass. In the last pass element 0, element 1, element 2 ....element n, element (n+1) etc is compared.

This is how the shell sort operates. During each pass the elements being compared are re-arranged in sorted order,ie, if element i and j are compared the position of i and j are rearranged so that the series i,j is in sorted order.

Points of interest
Like the insertion sort it has best case of O(n) hence its suitable to check whether an array is sorted or not.
Choosing the increment sequence is a tricky question. If you are concerned about the efficiency I have few recommendations for you:
The Sedgewick increment sequence..
, or ......
The best known sequence according to research by Marcin Ciura is 1, 4, 10, 23, 57, 132, 301, 701, 1750

Algorithm:

input: an array a of length n with array elements numbered 0 to n − 1

inc ← round(n/2)
while inc > 0 do:
  for i = inc .. n − 1 do:
      temp ← a[i]
      j ← i
      while j ≥ inc and a[j − inc] > temp do:
          a[j] ← a[j − inc]
          j ← j − inc
      a[j] ← temp
  inc ← round(inc / 2.2)

Worst case performance : Depends on the leap/step size sequence
Best case performance : O(n)
Average case performance : Depends on the leap/step size sequence
Worst case space complexity: O(n)

Thanking you, Layman

Art of computer programming -Sorting #2

2009-11-17T23:08:00.000-08:00

Insertion sort
Insertion sort is one of those very traditional sorting methods. In this method, we scan through the list element by element and we assume that all elements preceding the present element is sorted. We start with the assumption that first element is sorted and we need to place the 2nd element to the left or the right of the first element based on whether its greater than or less than the 1st element. So we can generalize that for the i'th element we assume that the list from 0...i-1 is sorted and we can insert the ith element at the the correct position in this sorted sublist. So the problem reduces to inserting an element in a sorted list. But its not as simple as it sounds. Inserting in a sorted list may need shifting the elements of the sublist. Its a reasonably expensive operation. Hence using arrays will be quite expensive for insertion sort. Whereas if you are using linked lists, then shifting operations become much more easier(as it involves only 2-3 pointer operations).
On an average we will need a total of 0.5(1+2+...+n) shiftings ~ 0.25n^2

A method to improve this will be to use binary search to find the position of the element in the sorted list. This will reduce the position search time to log n. Hence the algorithm improves.

Points of interest
To check whether a list is already sorted insertion sort is highly recommended.
It can receive data as it is working. This is particularly useful when you have only an incomplete piece of data.
While insertion sort typically makes fewer comparisons than selection sort, it requires more writes because the inner loop can require shifting large sections of the sorted portion of the array.

Algorithm

insertionSort(array A)
begin
   for i := 1 to length[A]-1 do
   begin
       value := A[i];
       j := i - 1;
       while j >= 0 and A[j] > value do
       begin
           A[j + 1] := A[j];
           j := j - 1;
       end;
       A[j + 1] := value;
   end;
end;

Worst case performance О(n^2)
Best case performance O(n)
Average case performance О(n^2)
Worst case space complexity O(1)

Rectangle intersection problem with tree datastructure

2009-11-13T01:36:00.000-08:00

The problem here is to write a program that will find all the rectangles that intersects with a given rectangle once the left bottom and top right of the rectangles are given.

#include < stdio.h>
#include < stdlib.h>
#include < sys/stat.h>

struct rect {
int x,y;
struct rect *left,*right,*rtpoint;
};

int xmin,ymin,xmax,ymax;

typedef struct rect rec;
rec *root=NULL,*newptr=NULL;

void find(int x1,int cnd) {
rec *parent=NULL,*tptr=NULL;
rec *ptr=root;
while(ptr!=NULL) {
parent=ptr;
if(cnd==0) {
//if( ((ptr->x > x1) && (ptr->rtpoint)->x < x1) || ((ptr->x < x1) && ((ptr->rtpoint)->x>x1) ) )
if(ptr->rtpoint!=NULL) {
if(check(ptr)) {
printf("\nIntersects (%d,%d) - (%d, %d)\n",ptr->x,ptr->y,(ptr->rtpoint)->x,(ptr->rtpoint)->y);
(ptr->rtpoint)->rtpoint=NULL;
ptr->rtpoint=NULL;
}
}
}
if(ptr->x > x1)
ptr=ptr->left;
else
ptr=ptr->right;
}
if(cnd==1) {
if(parent->x > x1 )
parent->left=newptr;
else
parent->right=newptr;
}
}

int check(rec *temp) {
rec *temp2=temp->rtpoint;
int ys=temp->y,xs=temp->x;
int yr=temp2->y,xr=temp2->x,t;
if(ys>yr) {
t=ys;
ys=yr;
yr=t;
}
if(xs>xr) {
t=xs;
xs=xr;
xr=t;
}
return !( (yr <= ymin) || (ys >= ymax) || (xr <= xmin) || (xs >= xmax) );
}

void preorder(rec *ptr) {
if(ptr!=NULL) {
preorder(ptr->left);
printf("x=%d y=%d\n",ptr->x,ptr->y);
preorder(ptr->right);
}
}
void bt_free() {
if(root==NULL)
return;
bt_free(root->left);
bt_free(root->right);
free(root);
}

int main() {

FILE * fp;
int temp;
rec *temp_ptr=NULL;
struct stat stFileInfo;
char filename[50];
do {
printf ("Enter the filename to get data : ");
gets(filename);
temp=stat(filename,&stFileInfo);
if(temp!=0) {
printf("File doesnt exist!!! \n");
}
}while(temp != 0);
fp = fopen(filename,"r");
while(fscanf(fp,"%d %d %d %d",&xmin,&ymin,&xmax,&ymax) > 0) {
if(root==NULL) {
root=(rec *)malloc(sizeof(rec));
root->x=xmin;
root->y=ymin;
root->left=NULL;
root->right=NULL;
temp_ptr=root;
newptr=(rec *)malloc(sizeof(rec));
newptr->left=NULL;
newptr->right=NULL;
newptr->rtpoint=temp_ptr;
newptr->x=xmax;
newptr->y=ymax;
find(xmax,1);
temp_ptr->rtpoint=newptr;
}
else {
newptr=(rec *)malloc(sizeof(rec));
newptr->left=NULL;
newptr->right=NULL;
newptr->x=xmin;
newptr->y=ymin;
temp_ptr=newptr;
find(xmin,1);
newptr=(rec *)malloc(sizeof(rec));
newptr->left=NULL;
newptr->right=NULL;
newptr->rtpoint=temp_ptr;
newptr->x=xmax;
newptr->y=ymax;
find(xmax,1);
temp_ptr->rtpoint=newptr;
}
}
fclose(fp);
printf("Tree created successfully\nPreorder traversal follows\n");
preorder(root);
printf("\nEnter the test rectangle co-ordinates seperated by comas\n");
scanf("%d,%d,%d,%d",&xmin,&ymin,&xmax,&ymax);
if(xmin>xmax) {
temp=xmin;
xmin=xmax;
xmax=temp;
temp=ymin;
ymin=ymax;
ymax=temp;
}
find(xmin,0);
find(xmax,0);
bt_free();
return 0;
}

Sample input file
6 6 11 11
0 0 2 2
9 9 12 12
60 0 70 100
7 2 8 12

COM/Serial communication in C

2009-11-13T00:33:00.001-08:00

This program will help you to understand how to do serial communication in C.
The C program will illustrate the basics of serial communication.

/////////////////////////////////////////////////
// Serial port interface program //
/////////////////////////////////////////////////

#include < stdio.h > // standard input / output functions
#include < string.h > // string function definitions
#include < unistd.h > // UNIX standard function definitions
#include < fcntl.h > // File control definitions
#include < errno.h > // Error number definitions
#include < termios.h > // POSIX terminal control definitionss
#include < time.h > // time calls
#include < stdlib.h >
#include < sys/types.h >
#include < netinet/in.h >
int fd;
int open_port(void)
{
int fd; // file description for the serial port

fd = open("COM2", O_RDWR);

if(fd == -1) // if open is unsucessful
{
perror("open_port: Unable to open /dev/ttyS0 - ");
}
else
{
printf("Opened %d\n",fd);
}

return(fd);
}

int configure_port(int fd) // configure the port
{
struct termios oldtio,port_settings; // structure to store the port settings in
tcgetattr(fd,&oldtio);
//cfsetispeed(&port_settings, B115200); // set baud rates
//cfsetospeed(&port_settings, B115200);

bzero (&port_settings, sizeof (port_settings));
port_settings.c_cflag = B115200 | CLOCAL | CREAD;
port_settings.c_cflag &= ~PARENB; // set no parity, stop bits, data bits 8N1
port_settings.c_cflag &= ~CSTOPB;
port_settings.c_cflag &= ~CSIZE;
port_settings.c_cflag |= CS8;
port_settings.c_iflag = IGNPAR | ICRNL;
port_settings.c_oflag = 0;
port_settings.c_lflag &= ~ICANON;
tcflush(fd, TCIFLUSH);
tcsetattr(fd,TCSANOW,&port_settings);
return(fd);
}

int query_modem(int fd) // query modem with an AT command
{

int k=0;
char str[5];
str[0]=2;
str[1]=str[2]='f';
str[3]=str[4]=3;
k=write(fd,str,strlen(str)); // send an AT command followed by a CR
printf("command %d\n",k);

}
int dsadas()
{
printf("In fm");
int bytesRead;
char *str;
char *buff;
//str=(char *)malloc(100*sizeof(char));
//buff=(char *)malloc(1024*sizeof(char));
while(1)
{

//printf("In while");
if(read(fd,str,10)>0)
{
printf("in if");
buff="";
printf("yesyeysyes %s\n",str);
//strcpy(buff,str);
do
{
//sleep(100);
//append
printf("Buffer = %s",buff);
strcat(buff,str);
bytesRead=read(fd,str,10);
}while(bytesRead>0);
//send bytes to ip
printf("Buffer = %s",buff);
}
}
}

int main(void)
{
pthread_t thread1,thread2;
fd = open_port();
configure_port(fd);
query_modem(fd);
int iret1, iret2;
//iret1 = pthread_create( &thread1, NULL, dsadas);
//pthread_join(thread1, NULL);
return(0);
}

Create tree from preorder traversal

2009-11-13T00:20:00.000-08:00

#include < stdio.h >
#include < stdlib.h >

int current=0;

struct bstree {
int val;
struct bstree *left,*right;
};

typedef struct bstree node;

node* tree_build(int* inarr,int* prearr,int left,int right);
void sort(int inarray[], int begin, int end);
void swap(int *a,int *b);
void inorder_traverse(node *ptr);
void bt_free(node *ptr);

main() {
int i;
int prearr[]={10,4,3,2,5,6,11,13,12};
int inarr[10];
for(i=0;i<9;i++)
inarr[i]=prearr[i];
sort(inarr,0,9);
node* root = tree_build(inarr,prearr,0,9);
printf("\n\nTREE CREATED. NOW DOING AN INORDER TRAVERSAL ON THE TREE...\n\n");
inorder_traverse(root);
printf("\n\n");
bt_free(root);
}

void bt_free(node *ptr) {
if(ptr==NULL)
return;
bt_free(ptr->left);
bt_free(ptr->right);
free(ptr);
}

void swap(int *a,int *b) {
int temp=*a;
*a=*b;
*b=temp;
}

void sort(int inarray[],int begin,int end) {
if (end > begin + 1) {
int pivot=inarray[begin],l=begin+1,r=end;
while(l if (inarray[l] <= pivot)
l++;
else
swap(&inarray[l],&inarray[--r]);
}
swap(&inarray[--l],&inarray[begin]);
sort(inarray,begin,l);
sort(inarray,r,end);
}
}

node* tree_build(int inarr[],int prearr[],int left,int right) {
int i,position;
if(left==right)
return NULL;
node *temp=(node *)malloc(sizeof(node));
temp->val=prearr[current];
if(left+1==right)
return temp;
i=left;
while(i if(inarr[i]==prearr[current])
break;
i++;
}
for(position=0;inarr[position]!=inarr[i];position++);
if(position>left) {
current++;
temp->left=tree_build(inarr,prearr,left,position);
}
if(position+1 current++;
temp->right=tree_build(inarr,prearr,position+1,right);
}
return temp;
}

void inorder_traverse(node *ptr) {
if(ptr==NULL)
return;
inorder_traverse(ptr->left);
printf(" %d - ",ptr->val);
inorder_traverse(ptr->right);
}

TCPIP communication in C

2009-10-23T01:14:00.000-07:00

Server.c
/* A simple server in the internet domain using TCP
The port number is passed as an argument */
#include < stdio.h >
#include < sys/types.h >
#include < sys/socket.h >
#include < netinet/in.h >

void error(char *msg)
{
perror(msg);
exit(1);
}

int main(int argc, char *argv[])
{
int sockfd, newsockfd, portno, clilen;
char buffer[256];
struct sockaddr_in serv_addr, cli_addr;
int n;
if (argc < 2) {
fprintf(stderr,"ERROR, no port provided\n");
exit(1);
}
sockfd = socket(AF_INET, SOCK_STREAM, 0);
if (sockfd < 0)
error("ERROR opening socket");
bzero((char *) &serv_addr, sizeof(serv_addr));
portno = atoi(argv[1]);
serv_addr.sin_family = AF_INET;
serv_addr.sin_addr.s_addr = INADDR_ANY;
serv_addr.sin_port = htons(portno);
if (bind(sockfd, (struct sockaddr *) &serv_addr,
sizeof(serv_addr)) < 0)
error("ERROR on binding");
listen(sockfd,5);
clilen = sizeof(cli_addr);
newsockfd = accept(sockfd,
(struct sockaddr *) &cli_addr,
&clilen);
if (newsockfd < 0)
error("ERROR on accept");
bzero(buffer,256);
n = read(newsockfd,buffer,255);
if (n < 0) error("ERROR reading from socket");
printf("Here is the message: %s\n",buffer);
n = write(newsockfd,"I got your message",18);
if (n < 0) error("ERROR writing to socket");
return 0;
}

Client.c
#include /* for printf() and fprintf() */
#include /* for socket(), connect(), send(), and recv() */
#include /* for sockaddr_in and inet_addr() */
#include /* for atoi() and exit() */
#include /* for memset() */
#include /* for close() */
#include
#define RCVBUFSIZE 200024 /* Size of receive buffer */

void DieWithError(char *errorMessage); /* Error handling function */

int main(int argc, char *argv[])
{
int sock; /* Socket descriptor */
struct sockaddr_in echoServAddr; /* Echo server address */
unsigned short echoServPort; /* Echo server port */
char *servIP; /* Server IP address (dotted quad) */
char *echoString; /* String to send to echo server */
char echoBuffer[RCVBUFSIZE]; /* Buffer for echo string */
unsigned int echoStringLen; /* Length of string to echo */
int bytesRcvd, totalBytesRcvd; /* Bytes read in single recv()
and total bytes read */

servIP = "10.64.122.26"; /* First arg: server IP address (dotted quad) */
echoServPort = atoi("9000"); /* Use given port, if any */

/* Create a reliable, stream socket using TCP */
if ((sock = socket(PF_INET, SOCK_STREAM, IPPROTO_TCP)) < 0)
DieWithError("socket() failed");

/* Construct the server address structure */
memset(&echoServAddr, 0, sizeof(echoServAddr)); /* Zero out structure */
echoServAddr.sin_family = AF_INET; /* Internet address family */

echoServAddr.sin_addr.s_addr = inet_addr(servIP);

echoServAddr.sin_addr.s_addr = inet_addr(servIP); /* Server IP address */
echoServAddr.sin_port = htons(echoServPort); /* Server port */

/* Establish the connection to the echo server */
if (connect(sock, (struct sockaddr *) &echoServAddr, sizeof(echoServAddr)) < 0)
DieWithError("connect() failed");

/* Receive the same string back from the server */
totalBytesRcvd = 0;
printf("Received: "); /* Setup to print the echoed string */
while (1)
{
/* Receive up to the buffer size (minus 1 to leave space for
a null terminator) bytes from the sender */
if ((bytesRcvd = recv(sock, echoBuffer, RCVBUFSIZE - 1, 0)) > 0)
{
echoBuffer[bytesRcvd] = '\0'; /* Terminate the string! */
printf("%s\n", echoBuffer); /* Print the echo buffer */
}

}

printf("\n"); /* Print a final linefeed */

close(sock);

exit(0);
}//-- end main --//

void DieWithError(char *errorMessage)
{
perror(errorMessage);
exit(1);
}

Thanking you
Layman

C code to check for the existance of a file

2009-10-13T19:14:00.001-07:00

Recently I came across this question to check if a file exists in a given directory. The question looks pretty simple, but most of those guys just out of college will have trouble doing this, its for them that I write this down. Actually, you are supposed to know all this. But nothing happens as expected during college. So lets look at it at least now. There are many ways to do the same.
You can do a fopen and if it fails then you can probably assume that the file doesn't exist. The standard practice in the software industry is to use a stat() function.

Includes:
#include
Code:
int intStat;
struct stat stFileInfo;
intStat = stat(filename,&stFileInfo);
if(intStat==0)
printf("File already exists!!!\n ");
else
printf("File doesnt exist\n ");

So,this is how you will check whether a file exists or not with the stat function. From now on use this method rather than checking whether fopen fails
Thanking you,
Layman

Art of computer programming -Sorting #1

2009-09-05T21:30:00.001-07:00

Long since Ive posted something. This time we will learn sorting. Sorting is familiar to you and to me for many years. But there are aspects of it which I haven't heard about ever since I first knew it. Those will be the points of discussion here.

Sorting by counting :
I cant say this is the best method. But every method has its advantages and disadvantages when used appropriately.

set count[i]=0 for all i from 0 to n-1
for(i=n;i>1;i++) {
for(j=i-1;j>=1;j++) {
if element[i]>element[j] count[i]++;
else count[j]++;

Now we have an auxiliary table within which we have the position of the elements in the sorted list.
Distribution counting sort:
This technique is applicable when we have to sort the numbers which belongs to a small range.
That is all the values to sort should be less than v(upper limit) and greater than u(lower limit) and v-u is small(<10 i="0;i). In such cases we can use the sorting by counting method to its full use and it'll give much better efficiency than any other method.
Thanks
Layman

Mini/Main CS Project ideas

2009-07-05T09:52:00.000-07:00

Its been sometime since I wanted to post some project ideas.

Develop a debugger for C/CPP : gdb is a well known debugger in linux. On similar lines you can write a debugger for C/CPP. A debugger should contain functionalities to setup break points , view variable status etc. You can use Eclipse and see how ideally a debugger should work. I recommend you to do a mini-version of gdb. You will have many references since many debuggers including gdb are open-source.

Virtual private server : VPS will provide multiple virtual hosting environments on the same physical server. This will eliminate the need for separate physical servers for hosting different websites. It will also provide clients with an economical solution for hosting their website and allow web hosting providers (WHPs) to use their resources efficiently. Each VPS acts as a dedicated server with full root access. The benefits from such products are efficient use of existing resources by sharing them between various customers, provides more security than other sharing hosting techniques, provides root access inside each VPS though with limited capabilities, faster context switching, and minimum modifications to kernel.
Octave Gtk : Octave-Gtk aims to bring a full-featured toolkit like GTK to GNU Octave, to make scientific computing tools with a GUI front-end scripted from Octave itself. This directly translates to end users as a new and powerful paradigm for constructing GUIs with minimal knowledge of the constructs and easy interface for scientific programs in a really short time. Octave-Gtk is an Octave Gtk binding, which helps you access the GTK C API from the GNU Octave, an interpreted language. This cross language interoperability is achieved by Octave-Gtk binding code, which enables type safe, idempotent access of functions and objects from the either domains of Octave and C in a clean, and transparent manner, hiding the details to the end user.
CrossTalk : CrossTalk is a VoIP client for Windows and Linux. It allows users to talk in real time (like telephone calls) and explores the exciting world of Internet Telephony. CrossTalk will implement a simple user interface allowing users to easily make calls anywhere. It will support the encryption of the data stream, low latnecy, use of minimum bandwidth and maybe multiple conferencing as well. I intend to develop CrossTalk clients for both Linux and Windows. All of the above 'abstracts' are what I intend to do, whether I can do it, or, maybe even better it is to be seen.
A Highly secure steganographic file system : Magikfs is a highly secure steganographic file system with the plausible deniability feature being implemented on the Linux platform particularly over an ext2/ext3 partition without structural modifications. The data which is already present in the file system is not harmed at all. Magikfs will be user friendly,easy to install and easy to give your files the highest kind of security ever offered by file systems that exists today.
Secure PC to PC communication : PC to PC communication is essential to share the information. The SENDTO command is used to directly send the message over the network. So, it is not possible to send the secured information. The sent message is not secured and can be mis utilized or eavesdropped. RSA is a public key algorithm. Public key cryptography uses 2 keys a "public key" and "private key" to implement an encryption algorithm that does not require two parties to first exchange a secret key in order to conduct secure communication. Two types of primitive are specified in this document, organized in pairs: encryption and decryption. An encryption primitive produces a cipher text representative from a message representative under the control of a public key, and a decryption primitive recovers the message representative from the cipher text representative under the control of the corresponding private key. Its security is based on difficulty of factorizing large integers.
Mobile based collaboration : Mobiles are increasingly becoming high-end not only in terms of hardware but also in operating system cum software support. Hence, there is much demand of feature packed applications which are as good or even better than their PC based counterparts. Our application, a mobile based collaboration tool, beautifully packs features from different popular domains (like google calendar, maps, drawing tools, text chat etc.) into an application which allows collaboration with other users. Online document creation made popular by Google Docs has paved the way for creation of similar utilities to make a users experience wholesome. The very idea of an amateur internet user being able to share and communicate with his/her friends, relatives and business associates over the internet through simplistic yet powerful tools is very encouraging. Realizing this fact, we have developed an application that can collaboratively share information and data among a group of trusted users. Our main utility is a drawing tool for Android (Open Source Mobile SDK) which is based on the principle that inherent capability of human beings to express and understand is much better in terms of colorful figures than through plain text. In addition to this, we have incorporated several other features in our application, Google calendar, maps, advanced drawing features, text chat etc., that allow users to use the shared information enhancing the overall experience.

Courtesy: Red hat scolarships
Thanking you,
Layman

Regular expressions quick list

2009-06-30T22:50:00.000-07:00

One of the most essential things you need to know as a software engineer or as a software engineering student is regular expressions. This post will brief you about the basics of regular expressions, again remember this is just a layman's view and not a geeks perspective, so read this and move on.....

Metacharacters -------------------------Matches

. -------------------------------Anything except newline character
\n -----------------------------Newline
* ------------------------------Zero or more copies of preceding expression
+ -----------------------------One or more occurrence of preceding expression
? ------------------------------Zero or one copies of preceding expression
^ -----------------------------Beginning of a line
$ ------------------------------End of line
a|b ---------------------------a or b
(ab)+ -----------------------One or more copies of ab (grouping)
"a+b" -----------------------Literal "a+b"
[] ------------------------------Character class

Examples :-

abc------------------------------------- abc
abc* -----------------------------------ab abc abcc abcc abccc ......
abc+ ----------------------------------abc abcc abccc.....
a(bc)+ -------------------------------abc abcbc abcbcbc....
a(bc)? --------------------------------a abc
[abc] ----------------------------------one of:a,b,c
[a-z] -----------------------------------any letter, a-z
[a\-z] ----------------------------------one of : a,-,z
[-az] ---------------------------------- one of : - , a, z
[a-zA-Z0-9]+ ----------------------one or more alphanumeric characters
[ \t\n]+ -------------------------------whitespace
[^ab] ---------------------------------anything except : a,b
[a^b] ---------------------------------one of : a, ^, b
[a|b] ----------------------------------one of : a, | , b
a|b ------------------------------------one of : a, b
^[a-z] --------------------------------line starting with a character from a-z
[a-z]$ --------------------------------line ending with a character from a-z
^[a-z]$ -----------------------------line containing only a character from a-z

Thanking you,
Layman

Linux Commands: Quicklist

2009-06-29T20:25:00.000-07:00

Who…….whoami
date
use of ; to separate commands
man
ls………. –F folder /…………. –l line by line
cat Types contents onto screen …… -n option for line no -b for line no excluding blank lines
wc word count -l for line count -w for word count -c for character count
cp copy source file to destination -i ask before overwrite

-r option for copying directories ……multiple directories may also be specified

More than one sources can be specified. Last one will be taken as destination

mv ……. –i option is available for preventing the overwrite.

mv can also be used along with directories(moving)

rm removes the files
rmdir removes a directory
ls –l gives the permissions …………..

1^st 3 charas give owner permissions

2^nd 3 gives group permissions

3^rd 3 gives other privileges

chmod

expression is either symbolic or octal. In symbolic letters are used. In octal nos from 0-7 are used to set the permissions.

In symbolic form the syntax is (who) (action) (permission)

Letter Represents

u Owner

g Group

o Other

a All

Symbol Represents

+ Adding permissions to the file

- Removing permission from the file

= Explicitly set the file permissions

Letter Represents

r Read

w Write

x Execute

eg. $ chmod guo+rx *

gives read and execute permissions to group, owner and others(all).More than one set of permissions can be set by separating by commas.

Octal methods

Read permission value = 4; Write permission value=2; Execute permission value=1;

Adding the value of the required permission will give us a value b/w 0-7. We can use this no to specify the permission for the owner, group, and others in the respective order.

$ chmod 0777 *

Will mean to add rwx permissions to all

$chmod 0770 *

will add rwx permissions to owner and group members whereas others will be prevented from reading , writing or executing the file.

Here * specifies that the change of permission is applicable for all the files in the pwd (present working directory)

chown option user : group files

chown is used to change the ownership of a file or group of files.

Option is basically all crap. Don’t worry over that.

User will be a an existing user . This will specify the new owner of the file(s)

Group files will be a path. It can be a single file or maybe a directory path.

In recent systems chgrp is a new command available.

For portability sake we better skip this option and stick on to chown.

This command lists all the presently running processes. Each process has a unique id called process id or PID. It will be unique during a runtime. Its usually a 5 digit number. Max value of PID is 32767.

Each process will have a PID and a Parent PID attached to it. Each process will have a parent process. We will note that most processes have the PPID as the PID of shell.

With all commands we may run them in foreground or background. If we run smthing on foreground we cannot do any other process until it completes. So to save time we can simply put them on to the background. To run a command as a background process just add a ‘&’ sign at the end of the command. Eg. $ps &

TIP : stty –a command will give you the list of all key combinations for various functions.

bg %job number

To move a foreground process to background we can use the ^Z key combination so that the process is suspended and then using the bg command. By default if no job number is specified bg command resumes the most recently suspended process to background.

fg %job number

To move a suspended process or maybe a background process to foreground we can use this command. Job number maybe specified. In case it’s not supplied, the shell takes it as the last job suspended.

nohup

This command can be prefixed with any other command. It suppresses the action of the hang up signal and thus causes a command to run even after the user logs out. This command is usually used to run commands in background. The results if not redirected will go to a file called nohup.out . Otherwise it can be suitably redirected

Eg. $nohup ls & will redirect the op to nohup.out

wait

wait can be used to put the shell to wait state until background process(es) proceed to completion. The optional parameter maybe a process id , a process number prefixed by % sign , it maybe blank. In case the parameter is blank(absent) the shell waits until all background processes attain completion.

jobs

This command shows the list of all processes that the user has suspended and also the ones running in the background. In the op we can see – and + signs appear. The job holding + sign will be the most recent one.

kill

The word says it all. It can kill a process. The parameter maybe a PID or it may be the process no prefixed by the %sign. Actually the kill command sends a TERM signal to the process. The process may ignore this signal or otherwise it can perform an orderly shutdown. In case it ignores we can go for the kill -9 (or kill –KILL) command followed by the parameter so that it will be forcibly killed.

exec

This command replaces the current process with a new process specified in the command. The real mechanism is overlaying the new process on the older running one.

Variables

Scalar variables are available in unix. The variable assignment is fairly simple.

Variable name=value

The lexical rules for variable names are same as that of C. In case we need to get the value of a variable we need to prefix the variable name by a $ sign. When the variable name prefixed by the $ sign is parsed, the idea is to textually substitute for the $variable by its value . Use $ along with the variable name only when the value is needed and not anywhere else. When assigning a string better use quotes.

So far we have seen how to use scalar variables. Now we shall move on to the more organized arrays. The concept of arrays is same as in C. Array initialization is fairly simple.

Array name[index]=value

Array name =(element1 element2 element3 …….elementn)

Array name=([index1]=element1 [index5]=element5…….)

Accessing an array element is a different matter. The syntax will be…

{Arrayname[index]}

Unlike C ,here the shell doesn’t keep track of all the positions in an array. Rather it keeps track of those elements that are assigned values. To access all elements in an array 2 options are available.

{arrayname[*]}

{arrayname[@]}

If we assign a value to the arrayname, its equivalent of assigning to the 0^th element in the array.

We may set a variable as read-only by the following command

readonly variablename

Once a variable has been set as readonly, then we can’t overwrite it.

Just like we declared variables we can unset or rather remove them from the computer’s memory. The command format is shown below. This is same for both arrays as well as scalar variables. But we cannot use this command format to remove variables that have been set readonly.

unset variablename

So far we have discussed about variables. Now we shall see the different types of variables.

Local variable : Those variables which we had used until now. These are user modifiable and can be set by the user. These are the variables that are currently available within the shell and are not available to other processes of the shell.
Environment variable : These are variables that are accessible to every child process of the shell. These are also user-modifiable. Only those environment variables that are required for the proper functioning of the child program is usually reserved.
Shell variable : These are special types of variables that are set by the shell (and none else) for the proper functioning of itself. They maybe of either local or environment type.

Now we will see how to export a variable to the environment.

export varname=value varname1=value1……….varnamen=valuen

Substitutions

There are basically 4 types of substitutions

Filename substitution or globbing
Value based variable substitution
Command substitution
Arithmetic substitution

In globbing we basically use three wildcards to match filenames. They are *(which matches any no of any characters),? (which matches any 1 character), [character list] (which matches any 1 character from the character list). Rules that are to be used in the character list are same as those that we have learnt in Perl (minor differences yet exist .for eg negation is specified by ! and not by ^).

In value based substitutions, a value is substituted or replaced for a parameter according to certain conditions. There are basically 4 forms shown below.

${parameter:-word} Will mean to substitute the word for the parameter in case the parameter is either unset or is null. Here its blind substitution of the word instead of the parameter as in case of a macro and it’s the word that matters, not its value.

${parameter:=value}

………………………………….

Command substitution is yet another form. Its fairly simple. The basic idea is that the command itself gets replaced by the output of a command. The usual context of implementation is in the case of assigning an output to a variable.

Variable=’command’

Arithmetic substitution basically deals with an expression as shown below. Here all the basic operations like +,-,*,/ exists. Also its possible to change the precedence by using braces. Arithmetic is integer arithmetic. Hence floating point values maybe truncated.

$((expression))

Flow control

If statement:

If list1

then

list2

elif list3

then

list4

else

list5

if statement finds application in error handling. List1 can be any operation, it maybe a encode operation or maybe a file creation operation. In any case if the operation fails(ie it returns nonzero) list2 is not executed.

There is yet another representation.

if list1 ; then list2; elif list3 ;then list4; else list5; fi

test is a command used in association with if statement. It returns 0 or 1 based on the expression it receives as argument. Syntax is shown below.

test expression

[ expression ]

Now we shall see the various kind of tests.

File tests
String comparisons
Numerical comparisons

File tests are used for testing files. The syntax is shown below.

[ option filename ]

Some of the options are:

-b if file exists and if it’s a block special file

-c if the file exists and if it’s a character special file

-d if the file exists and id it’s a directory

-e if file exists

-f if file exists and if it’s a regular file

-r if file exists and it is readable

-w if file exists and it is writable

-x if file exists and its executable

Now we shall take a look at test operations on strings. There are basically 2 things we would like to find out.

Check whether a string is empty
Check whether 2 strings are equal

[ -z string ] checks whether a string is of zero length

[ -n string ] checks whether a string is of nonzero length

[ string1=string2 ] if the strings are equal returns 0

[ string1 != string2 ] if the strings are unequal returns 0

Test can be done on integers by the following format.

[ int1 operator int2 ]

Operator can be:

-eq equal to

-le less than or equal to

-lt less than

-gt greater than

-ge greater than or equal to

Here I would like to mention a very important point.

When we try a command in the prompt we get the status of the command immediately. Errors will be immediately reported. Whereas in a shell script this won’t happen. So we must have some provision to check whether the last command was successful.

The exit status of the last command will be stored in a special variable $?. We can simply check this variable for the value 0 to make sure the last command was successful.

Continuing with our discussion, now we will see compound expressions. These include combining simple test expressions into a compound expression. The general form is shown below.

[ expression1 ] operator [ expression2 ]

Operator maybe

-a and

-o or

Its also possible to negate the outcome of an expression by using the following format

[ ! expression ]

Some important points need special mention. The spaces in the formats can’t be ignored. Also all these test expressions are used in association with if expression.

Case statement:

Switch case statements serve the same purpose as in C. The syntax is shown below.

case word in

pattern1)

list1

;;

pattern2)

list2

;;

esac

case word in

pattern1) list1 ;;

pattern2) list2 ;;

esac

Here the word is matched with each pattern provided. If it matches the corresponding list is executed.

Each pattern may include the wildcards.

Loops
while loop:

All of us know how a while loop works. The syntax is shown below.

while command

list

done

while command ; do list ; done

Command is usually a test expression that we have already dealt with.

List is any set of commands.

It’s possible to nest loops as in any other language.

There exists yet another loop. The until loop runs the list as long as the command(test expression) is false. Syntax is shown below.

until command

list

done

for loop:

The for loop is a slightly different concept from the for loop we know. It repeats a set of commands for each item in a list after assigning the item in the list to a variable. This is not the exact functioning of the loop. But for simplicity’s sake we shall look at it that way. Whatever be the loop deals with repeating a set of statements for each value in a list specified. Syntax is shown below.

for name in word1 word2 word3……….wordn

list

done

for name in word1 word2 word3……wordn ; do list ; done

Here the loop assigns each word to the name and then performs the list for each word.

Select loop:

This loop finds application in menu driven programs. The syntax is shown below.

select name in word1 word2 word3……….wordn

list

done

Here the bash prints a numbered list in the order word1…….wordn. Then it waits for the user to input. The input from the user is expected to be a number preceding any item that was displayed. If it is then the corresponding word is stored into the name.

Loop control

There are basically 2 loop control instructions.

break This command will break the control out of the loop.
continue This command will move the control out of the loop for the current iteration.

Input and output

Output to the terminal can be done 2 ways.

echo
printf

The usage of printf is the same as that in C.

Output of a command or a list of commands can be redirected to a file using the redirection operator.

Syntax is shown below.

{ command1; command2;…..commandn; } > filename

If no such file exists a new file is created. If it exists the file content is overwritten.

Appending to a file needs another redirection operator. Syntax is shown below.

{ command1; command2; command3; …………commandn; } >> filename

Sometimes it is necessary to write the result of commands onto the screen as well as a file. In that case we can use the following format.

command |tee filename

In input redirection, a text file can be redirected as an input to a command. The syntax is shown below.

command <>

There is yet another possibility.

command <<>

input1

input2

Inputn

delimiter

Here the redirection operator reads the input from the user until the specified delimiter is met with again. It then feeds the output to the command as input.

Now we will learn how to read an input from the user. The syntax is very simple.

read variable

Pipelining is yet another concept available.

command1 | command2……………

Here the output of command1 is fed to the input of command2 and so on.

File handles

We can associate a number with each filehandle and then use it to do operations on files.

3 file descriptors are always open along with each and every command.

STDIN value 0
STDOUT value 1
STDERR value 2

We can associate a filehandle with a file using the following command.

'exec n> filename'

'exec n>>filename'

Here n is any integer. If n is 1 then STDOUT is explicitly redirected to the specified file. In the second form the file is open in append mode.

Now to redirect the output of a command to a file we can use the following format.

'command n> filename' (Append mode is also available)

Also to read the contents from a file to the standard input of a command the following syntax can be used.

command n<>

Here n is the filehandle.

We may redirect STDIN, STDOUT and STDERR to any of the file by simply choosing 0,1,2 as the values for n.

It’s possible to redirect the input of STDIN/STDOUT and STDERR to different files.

'command 1>file1 2>file2'

The /dev/null file requires special mention. Anything redirected to this file will be discarded.

Sometimes we may want to send both STDOUT and STDERR to the same file. In that case the syntax is shown below.

'command > filename 2>&1'

Reading input from a file

Now we shall see how to read input from a file line by line and then use it for text filtering.

while read variablename

…………..

…………

'done <>'

Now let’s move on to the most important section as far as Y! is concerned. Most questions are asked from the text filtering section.

Text Filtering

Head and tail commands

We can extract the first/last n lines of a file by using head and tail commands respectively

head [ -n ] filename

tail [ -n ] filename

n is any integer. Head will return the first n lines and tail returns the last n lines. In case no integer is specified a default of 10 lines will be returned.

Grep command

This is yet another powerful text filtering command. Syntax is shown below.

grep option word filename

Option maybe

-i for case independent match

-v for unmatched set to be returned.

-n for line no’s to be attached

-l for the list of files including the word.

transliterate(tr) command :

This is yet another powerful text filtering command. The function performed by tr is to transliterate one set into another. The syntax is shown below.

tr 'set1' 'set2'

Here the characters included in set1 in the file are searched and replaced by the ones in set2. In case the filename is not specified the shell waits for the input from the keyboard. We must be careful while using characters like [ & ]. These have a special meaning when used along with tr. Thus we must quote them (using backslash) suitably. To capitalize or to do vice versa we can use set1 as 'A-Z' and set2 as 'a-z' .

Sometimes you might feel that all characters of set1 are being mapped to a single character of set2. In fact some versions of tr behaves differently. So to be on the safer side its always better to use the same number of characters in set1 and set2 (just in case tr behaves differently).

There is yet another option available for transliterate. This is the SQUEEZE option. The syntax is shown below.

tr -s 'set1'

Here if the shell finds multiple consecutive occurrences of any character in set1 then it gets replaced by a single occurrence.

Sort and uniq commands :

Sort command as we know sorts each line of input. We can use the tr command to transliterate the each word in the text input to a new line. Then we can sort the lines.

Syntax is shown below.

sort filename for ascending order sort

sort -r filename can be used for reversing the result.

Text filtering

Sed

Its the short for stream editor ,all the input we feed into it goes through it and finally reaches the STDOUT. It doesn't change the input file.

With each line of the input file specified it makes a copy of the line and then pattern matches the line with the pattern specified. If a match is found then the corresponding action is performed. Then it proceeds to the next pattern and repeats the same procedure. Since the matching is done on the copy of the line and not the real line the changes that are done on the line doesn't affect the real line.

Syntax is shown below.

sed [option] '/pattern1/' action1

'/pattern2/' action2

.......

...................... filenames

patterns are usually regular expressions. We are already familiar with regular expressions. The only major difference is that there is no + meta character here. Although we are already familiar with regular expressions I would like to add a few important points here.

[^chars] matches character set not specified by chars.

^[chars] matches character set that starts with any one specified in chars

[chars]$ matches character set that ends with a character specified in chars.

sed '/pattern/p' file prints the lines that can be matched by pattern

sed '/pattern/d' file prints the lines after deleting those lines that matches pattern

sed '/pattern/s/pattern1/pattern2/' file

First a list of all the lines that match pattern are created then in these lines those characters that match pattern1 are replaced by pattern2. Then the entire lines are printed.

sed 's/pattern1/pattern2/' file

here all those characters that match pattern1 in a line are substituted by pattern2.

But there is a problem with the last 2 cases. Only the first character set in a line that matches the pattern1 is substituted. All other patterns in the same line are not substituted. In case we need to replace all the character sets that match pattern1 then the following syntax is to be used.

sed 's/pattern1/pattern2/g' file

The following syntax replaces the 4^th pattern match in a line by the substitute provided.

sed 's/pattern1/pattern2/4' file

Sometimes we may need to replace the a pattern by another only if it doesn't contain a particular pattern. In that case we can use the following syntax.

sed '/pattern1/!s/pattern2/pattern3/g'

Here sed replaces all pattern2 by pattern3 for all the lines that doesn't match pattern1.

Deleting leading white spaces

sed 's/^[ \t]*//g'

Deleting trailing white spaces

sed 's/[ \t]*$//g'

Sometimes it becomes necessary to reuse a value in an expression. Suppose that we need to append a $ sign in front of all the numbers(floating) that is in a textfile. Then we can use the following syntax.

sed 's/[0-9][0-9]*\.[0-9][0-9]*/\$&/'

Its also possible to redirect the output of the sed command to a file by the following pattern.

sed '/pattern/' action filename >destination filename

Sometimes there occur situations in which there is a need to do more than one substitutions. In that case we can use the following syntax to perform the substitution.

sed 's/pattern1/pattern2/g' -e 's/pattern3/pattern4/g' ......................

Here the shell searches for pattern1 and substitutes all occurrences of pattern1 by pattern2 also it does the same thing with pattern3 and 4.

So far we have dealt with the easy ones that sed can give you. Now we will consider pattern space as a buffer. Just imagine that there are 2 buffers pattern buffer that holds the pattern to be printed and hold buffer that holds the current line. With this idea in mind read along.

= To print the current line number

sed = filename

x To exchange contents of pattern and hold

sed '/pattern/x' filename

Initially hold has null and pattern has 1^st line(that matches the pattern) then it exchanges their content and then prints the content of pattern. Next pattern gets next pattern matched. Hold has 1^st pattern matched. They exchange the content and then prints content of pattern.

n or N To read the next line in to the pattern space

sed '/pattern/n' filename

Here whenever a pattern is matched the next line is read into the pattern buffer.

g or G Copy/append hold buffer to pattern buffer.

sed '/pattern/g' filename

h or H Copy/append to pattern buffer to hold buffer.

sed '/pattern/h' filename

w filename Write the current pattern buffer to file

sed '/pattern/w filename' filename1

r filename Append text read from file

sed '/pattern/r filename' filename1

Double spacing a line that matches pattern

sed '/pattern/G' filename

Double space a file that has already blank lines in it.

sed '/^$/d;G' filename here the blanklines are first removed and then doublespaced

Delete double spacing

sed 'n;d' filename

Insert a blank line above every line that matches a pattern

sed '/pattern/{x;p;x}' filename

Insert a blank line below every line that matches a pattern.

sed '/pattern/G' filename

Insert a blankline above and below a pattern.

sed '/pattern/{x;p;x;G}'

Inserting the line number at the beginning of the every line

sed = filename | sed 'N;s/\n/\t/'

The first part of the command will give us the line nos attached to the lines but the line nos and lines are on separate lines. Hence we append every line (along with \n to the pattern buffer which initially contains the line number. Then we substitute tab for newline.

Inserting line number along with lines but print the linenos only if line is not blank]

sed '/./=' filename | sed 'N;s/\n/\t/'

Count the number of lines in a file

sed -n '$=' filename

Thanking you,

Layman

SEO 3

2009-06-29T11:44:00.000-07:00

I haven't yet seen any response for my previous posts. But I'm a self driven person and will keep on writing. So I'd like to give you my third and probably the final post on SEO. In my last post I talked to you about a brute force approach. Here I shall talk to you about a new approach , which is almost the opposite of what you have.

If you have a site on which you have some contents and you want to extract the useful data from the site (typically names of people, technology names ....etc). We shall call them entities. You need to put in some data and you need to get an array of words in the list which has some semantic importance. Have you guys come across any such system ?? . My boss was the first one to recommend me such a system. It is called CALAIS.

www.opencalais.com

You can go in there and find out its functionality.

So my recommendation,
Whenever a new post is made , get all the terms returned by calais and then do a google sktool search for the keywords related to each term.
Get the list returned by Google sktool and then add these terms to the link farm mentioned in the post SEO2
This will help you to build a linkfarm withou much burden on the server.
Thanking you
Layman

SEO 2

2009-06-26T06:01:00.000-07:00

The last post was for babies. I call those things for babies because they are things which any person who has heard of SEO will know. So this is what would actually help you. In this post I shall explain to you about how to bring about a revolutionary change with your site traffic. I will give you one way by which you can bring in a large traffic.
This is about keywords. Iam sure you would have heard about keywords. It was a practice that revolutionized the search engine market before years. Here people can add keywords to the html field and then search engines are more likely to show your page when someone searches for your page.

Im sure you are now feeling that I'm gonna retell you the story about keywords, which you would have heard for many years. NO. I have an idea here. And Iam going to present it before you. No matter what you people say, this is going to help you later.

PICK UP THE TOP 100000 keywords search queries in G, Y! or the newcomer B.
Search for relevant content in your site for these keywords.
If your site has relevant content then add your keyword to a link farm( basically a page full of links, filled with keywords here).
Each keyword in the linkfarm points to a page which shows the search results for the keyword within your site.
So basically the user isn't pissed off and you have a whole page of keywords.
I would recommend you to use only 100 links/page.
And the last step. Get the linkfarm indexed by the G or Y! or B.

Note: To get the linkfarm indexed you can submit it to google via a 'Add a result link' at the bottom of a page.

SEO 1

2009-06-23T23:42:00.000-07:00

You might have read a 1000 tips about bringing more traffic to your site. And yet you might feel that those tips arent really helping you. Well I would say ideally, if your site contains relevant content traffic should follow. When you don't have content and yet you want traffic, I cant call you anything short of being self-centered. And this article is not for those self-centered people.
This article has been a long time coming, and this is aimed at people who have relevant content on their site and yet cant get enough traffic because of 'n' number of reasons. I understand how bad it feels when you've done all the work and finally you cant make it because of one big 'G' or another shaky 'Y' and rarely cos of the just begun 'B'.

Basically recommending something for a site in general is something I really don't believe in . But there are general practices to be followed , and these may not help you with an outburst of traffic (or more pages indexed). But they are the basics and without them you cant get any outbursts. SO READ THE FOLLOWING EXTRACT...

Search engine optimization (SEO) is the process of improving th

Search engine optimization (SEO) is the process of improving the volume or quality of traffic to a web site from search engines via "natural" ("organic" or "algorithmic") search results.

As an Internet marketing strategy, SEO considers how search engines work and what people search for. Optimizing a website primarily involves editing its content and HTML coding to both increase its relevance to specific keywords and to remove barriers to the indexing activities of search engines.

Search engine optimizers may offer SEO as a stand-alone service or as a part of a broader marketing campaign. Because effective SEO may require changes to the HTML source code of a site, SEO tactics may be incorporated into web site development and design

Initially, all a webmaster needed to do was submit a page, or URL, to the various engines which would send a spider to "crawl" that page, extract links to other pages from it, and return information found on the page to be indexed.^[1] The process involves a search engine spider downloading a page and storing it on the search engine's own server, where a second program, known as an indexer, extracts various information about the page, such as the words it contains and where these are located, as well as any weight for specific words, as well as any and all links the page contains, which are then placed into a scheduler for crawling at a later date.

Early versions of search algorithms relied on webmaster-provided information such as the keyword meta tag, or index files in engines like ALIWEB. Meta tags provide a guide to each page's content. But using meta data to index pages was found to be less than reliable because the webmaster's choice of keywords in the meta tag could potentially be an inaccurate representation of the site's actual content.

While graduate students at Stanford University, Larry Page and Sergey Brin developed "backrub," a search engine that relied on a mathematical algorithm to rate the prominence of web pages. The number calculated by the algorithm, PageRank, is a function of the quantity and strength of inbound links. PageRank estimates the likelihood that a given page will be reached by a web user who randomly surfs the web, and follows links from one page to another. In effect, this means that some links are stronger than others, as a higher PageRank page is more likely to be reached by the random surfer.

Any content that is hidden using CSS or other forms of subterfuge, regardless of intent, may be regarded

as an invisible factor and devalued. At worst, if employed excessively, the page or site may be penalized as

a whole.

Page Title

The page title is a string of text, defined by contents of the element in the <head> section of the HTML document. The title is visible both in the title bar of a browser window, as well as the headline of a search engine result. It is arguably one of the most important factors in search engine optimization because it is both an important factor in search engine rankings, as well as a critical call to action that can enhance the click-through rate (CTR). Vanessa Fox of Google states, “Make sure each page has a descriptive <title> tag and headings. The title of a page isn’t all that useful if every page has the same one.” One of the biggest mistakes web developers make is to set the title for all pages on a web site to the same generic text. Frequently, this text is the company name and/or a slogan. In this case, at best your pages will be indexed poorly. At worst, the site could receive a penalty if the search engines see the pages as duplicate content. Be sure all pages on a dynamic site have unique and relevant titles. When writing titles, it is also wise to insert some targeted keywords. You should not lose sight, however, that a title is also a call to action. Even if a title successfully influences a search engine to rank a page highly, that ranking effectiveness is then multiplied by your CTR. Keyword stuffed titles are not always effective for CTR, though they may rank well. As a reminder, these keywords should also appear in the document’s copy. People will also frequently use a page title for the anchor text of an inbound link. Anchor text is an important off-page factor, and its beneficial effect is discussed later in this chapter. <title>BrandAdda: Community for Companies & Consumers around Brands & Products

<title>Mentos, Community, News, Review, Ideate, Rate, Discuss, Polls, Blog, Ads, Promotions, Photos, Videostitle>

Page Headings

Page headings are sections of text set off from web page copy to indicate overall context and meaning.

They are usually larger in size than the other copy within the document. They are typically created using

tags in HTML, where x is a number between 1 and 6. They have been abused in the past to manipulate

search rankings, but they are still an important on-page factor, and they also serve to help the user

navigate a page.

<h1>Mentosh1>a>

div>

<h3>Description: h3>

<h2 class="drupal-tabs-title">Last Weekh2>

Page Copy

It is intuitively clear that a page that contains the keywords that a user is looking for should be relevant

to his or her search query. Search engine algorithms take this into account as well. Keyword insertion,

however, should not be done in the excess. Mentioning the keywords in various inflections (plural, singular, past, present, and so on) is likely beneficial, as well as varying word order (“chocolate

chip cookies” versus “cookies with chocolate chips”). Excessive and contrived keyword repetition—

“keyword stuffing” — however, could actually be perceived as spam.

Because the search engine algorithms are unknown, “excessive” is an unfortunately vague qualifier.

This is one of the times we will reference something requisitely in an imprecise manner.

SEO copywriting aims to produce content on a web site in such a way that it reads well for the surfer,

but also targets specific search terms in search engines. It is a process that legitimately, without the use

of spamming techniques, seeks to achieve high rankings in the search engines. SEO copywriting is an

art, and it takes time to master. There is no magic solution that will make it easy to create copy that is

persuasive, contains relevant keywords a few times, and sounds like it is not contrived specifically to

do so. There are a few tricks, and a few useful hints, however.

One of our favorite tricks is to use the end and beginning of a sentence to repeat a keyword subtly.

Example: “Miami Hotels: You may want to try one our fine hotels in Miami. Hotel accommodations at

the Makebelieve Hotel will exceed your wildest expectations.”

The copy should also contain words that are related, but not necessarily inflections of your targeted key

phrase. For example, a search engine algorithm would likely see a page on cookies that also contains the

words “chocolate chip” or “cakes” as relevant. This tends to happen naturally with well-written prose,

but it is worth mentioning.

Mentos is a brand of mints, of the "scotch mint" type, sold in many markets across the world by the Perfetti Van Melle corporation. Mentos was first produced in the Netherlands during the 1950s. The slogan of Mentos is "The FreshMaker."

Outbound Links

Search engines will evaluate the links that a document contains. A related link on a web page is valuable

content in and of itself, and is treated as such by search engines. However, links to totally irrelevant or

spam content can potentially hurt the rankings of a page. Linking to a “bad neighborhood” of spam sites

or even lots of irrelevant sites can hurt a site’s rankings.

<a href="http://www.mentos.com/"

Keywords in Page URL and Domain Name

It is likely that keywords contained by a URL, both in the domain name or in the file name, do have a

minor but apparently positive effect on ranking. It also likely has an effect on CTR because keywords in

the URL may make a user more likely to click a link due to an increase in perceived relevance. The URL,

like the page title, is also often selected as the anchor text for a link. This may have the same previously

mentioned beneficial effect.

http://brandadda.com/bh/mentos

Internal Link Structure and Anchors

Search engines may make the assumption that pages not linked to, or buried within a web site’s internal

link structure, are less important, just as they assume that pages that are not linked well from external

sources are less important than those that are. Linking from the home page to content that you would

like to rank can improve that page’s rankings, as well as linking to it from a sitemap and from various

related content within the site. This models real-world human behavior as well. Popular products are

often prominently featured in the front of a store.

One horrible way to push pages down the link hierarchy is to implement pagination using “<>

“next >” links, without linking directly to the individual pages. Consider the example of the fourth page

of an article that is split into four parts. It is reached like this:

Home Page ➪Article Part 1 ➪Article Part 2 ➪Article Part 3 ➪Article Part 4

This fourth page is harder to reach not only by humans (who need to click at least four times), but also

by search engines, which would probably consider the content in that page as less important. We call the

effect of this link structure “death by pagination,” and we suggest two possible approaches for mitigating

the problem:

1. Don’t use simple pagination. Page with “<>” links, but also add links to the

individual pages, that is, “<>.” This creates a better navigation scheme to all

pages.

2. Add a sitemap with links to all the pages.

Invisible factors

Meta Description

For the most part, the importance of a meta description lies in the fact that search engines may choose to

use it in the SERPs, instead of displaying relevant bits from the page (this is not guaranteed, however).

Speaking from a marketing point of view, this may improve CTR. A meta description may also have a

minor effect on search engine rankings, but it is definitely not a critical factor in that regard. Here is an

example:

cookies that make you wish thousands of calories were actually good for you!” />

...

Meta Keywords

This criterion is widely regarded as totally unimportant because it is completely invisible and subject

to manipulation. It is wise to place a few major keywords as well as their misspellings in the meta keywords

tag, but the effectiveness of targeting misspellings this way has been disputed:

cookies, choclate, cokies” />

...

Alt and Title Attributes

Because these tags are mostly invisible, they are likely not an important ranking factor. Many assert

that their value is higher on hyperlinked images. They are important, however, for screen readers and

text-based browsers — that is, for accessibility and usability in general, so they should not be ignored

for that reason alone. Neither of these attributes will make or break you, but blind visitors using screen

readers will thank you in any case. This is a case where accessibility, usability, and search engine optimization

coincide. The descriptions should be short. Keyword stuffing in an alt tag will irk blind

users using screen readers, and possibly “irk” the search engines as well. Alt tags can only be used in

image tags, whereas title attributes can be used in most tags. Here is an example of the alt attribute

in an image:

chocolate chip cookie”>

And the title attribute on a link:

Page Structure Considerations

Search engines use block-level elements, for example

, , or elements to group related

text. Using block-level elements indiscriminately for layout, as illustrated in the following example, may

be harmful:

Dog

food

is likely to be less relevant than:

dog food

Time-Based Factors

Try as you might, but the only criterion that cannot be manipulated in any way is time. Old men and

women are often sought for their knowledge and experience. And the price of wine is directly proportional

to its age for a reason.

This is a useful analogy. Because time cannot be cheated, an old site that slowly accumulates links over

time and regularly adds new knowledge is what we term “fine wine.” Search engines tend to agree, and

give the deserved credit to such fine wines.

Many users previously purchased expired domain names that used to house an older popular web site

in the interest of tricking search engines into thinking a site is not new. Search engines are now aware

of this practice and reset the “aging-value” of any site that is housed by an expired domain name,

as well as devalue its preexisting links. In fact, there may also be a penalty applied to such expired

domain names, as discussed later in this chapter in the section “The Expired Domain Penalty.” There

are still opportunities, however, in buying domains directly from users with old existing web sites.

The time-based factors that are used as ranking factors are the site and page age, and the age of the links

referring to it. The registration length of a domain name may also influence rankings.me may also influence rankings.

External links

Quantity of Inbound Links

A site with many inbound links is likely to be relevant because many people voted for it by placing the

link on their sites. There are some caveats here with regard to whether the links are detected to be part of

an artificial link scheme, and quality is also a concern as explained in the next section. However, more is

generally better.

Quality of Inbound Links

A popular web site that links to you prominently that itself has many inbound links and a good reputation

is likely to mean more than a link from a random page from an unimportant web site with few

links. There is no absolute definition that describes “quality.” Search engines themselves struggle with

this definition and use very complicated algorithms that implement an approximation of the human

definition. Use your judgment and intuition.

Relevance of Inbound Links

A search engine is likely to view a link from a semantically related web page or site as more valuable than

a link from a random unrelated one. Usually, a series of links with very similar anchor text from unrelated

sources is an indicator of an artificial link scheme, and they may be devalued. Too many links from irrelevant

sources may result in a penalty. This has led to speculation that competitors can hurt your web site

by pointing many such links to your web site. Google states in its Webmaster Help Center, however, that

there is “almost nothing a competitor can do to harm your ranking or have your site removed from our

index” (http://www.google.com/support/webmasters/bin/answer.py?answer=34449). The

verdict is out on MSN Live Search, as documented at http://www.seroundtable.com/archives/

006666.html.

Link Churn

Links that appear and disappear on pages are likely to be part of a linking scheme. The rate at which

these links appear and disappear is termed “link churn.” If this happens frequently, it may be regarded

as spam. Those links will either be devalued, or at worst your web site will be regarded as spam and

penalized. Unless you are participating in such a scheme, this should probably not be a concern.

Link Acquisition Rate

An algorithm may view the acquisition of many thousands of links by a new site as suspicious, if not

also accompanied by relevant highly ranked authority sites. Usually this is an indicator of a linking

scheme. This consideration was affirmed by Google engineer Matt Cutts in one of his videos at http://

www.mattcutts.com/blog/more-seo-answers-on-video/.

Link Anchor Text and Surrounding Copy

Inbound links that contain semantically related anchor text to the content they point to have a positive

effect on rankings. The copy surrounding the link, if present, may also do the same. Some even posit

that this copy is as important as the link anchor text itself. Links with such surrounding copy are widely

believed to be valued more by search engines, because links without copy surrounding it are frequently

purchased and/or less indicative of a vote.

Manipulating link anchor text and the surrounding copy, if done en masse, can be used to manipulate

search results by creating a phenomenon called “Google bombing” (http://en.wikipedia.org/

wiki/Google_bomb). One popular example of this is illustrated, at the time of writing, with a

query to Yahoo!, Google, or MSN, with the keyword “miserable failure.” The top result is the White

House’s official biographical page for President George W. Bush, which doesn’t contain either of the

words “miserable” or “failure” in the copy, but is linked from many sites that contain the words

“miserable failure.” This particular Google bomb, and a few related ones, are described at http://

en.wikipedia.org/wiki/Miserable_failure.

Reciprocal Links

A long time ago, webmasters used to trade links strategically to achieve radical improvements in rankings.

This created an artificial number of self-serving votes. Over time, search engines became wiser and they

devalued such reciprocal links. In response, search engine marketers created link-exchanging schemes with

multiple parties to avoid detection. Modern search engines can detect such simple subterfuge as well. That

is not to say that reciprocal linking is bad, but it should be balanced by several one-way links as well. The

combination of the two models something more natural-looking and will result in higher ranking.

Number of Links on a Page

A link on a page with few outbound links is generally worth more than a link on a page with many outbound

links. This concept is also implied by the formula for Google’s PageRank.

Semantic Relationship among Links on a Page

A search engine may assume that a page with many links to pages that are not semantically related is a

links page, or some sort of page designed to manipulate rankings or trade links. It is also believed that

even naming a page with the word “links” in it, such as links.php, may actually devalue links contained

within that particular page.

IP Addresses of Cross-Linked Sites

It is sometimes useful to think of an IP address as you do a phone number. For this example’s sake, format

a hypothetical phone number, (123) 555-1212, differently—as if it were an IP:

123.555.1212

The first number, 123, is the area code, the second, 555, is the exchange, and the third, 1212, is the number

within that exchange. The numbers go from most significant to least significant. 123 probably indicates

“somewhere in this or that state.” 555 means “some county in the state,” and so on. So we can assert that

the person answering the phone at 123.555.1212 is in the same neighborhood as 123.555.1213.

Likewise, IP addresses located in the same C class — that is, addresses that match for the first three

octets (xxx.xxx.xxx.*) — are very likely to be nearby, perhaps even on the same server.

When sites are interlinked with many links that come from such similar IP addresses, they will be regarded

suspiciously, and those links may be devalued. For example, a link from domainA on 100.100.1.1 to

domainB on 100.100.1.2 is a link between two such sites. Done excessively, this can be an indicator

for artificial link schemes meant to manipulate the rankings of those web sites. Matt Cutts affirms that

Google scrutinizes this sort of interlinking in his video at http://www.mattcutts.com/blog/seoanswers-

on-google-video/.

Perhaps you host quite a few sites with similar themed content for whatever reason, and do not wish

to worry about this. There are a few vendors that offer hosting in multiple C classes. We don’t have

experience working with any of these providers, and do not make any recommendations. This is just

a list of hosting services that we’ve found that

TLD of Domain Name for a Link

It is widely believed that .edu and .gov domain names are less susceptible to manipulation and therefore

weighed more heavily. This is disputed by some search engine marketers as the actual factor, and

they assert that the same effect may be as a result of the age (most schools and governmental agencies

have had sites for a while), and amount of links that they’ve acquired over time. Matt Cutts coincides

with this view (http://www.mattcutts.com/blog/another-two-videos/). It is mostly irrelevant,

however, what the underlying reason is. Getting a link from a site that fits this sort of profile is very

desirable — and most .edu and .gov domains do.

Link Location

Links prominently presented in content near the center of the page may be regarded by the search

engines as more important. Links embedded in content presented near the bottom of a page are usually

less important; and external links at the bottom of a page to semantically unrelated sites may, at worst,

be a criterion for spam-detection. Presentation location is different than physical location. The physical

location within the document was historically important, but is less of a factor more recently. Ideally, the

primary content of a page should be early in the HTML source of a web page, as well as prominently

displayed in the center region of a web page. More on this topic is discussed in Chapter 6, “SE-Friendly

HTML and JavaScript.”

Web Standards Compliance

Standards compliance and cleanliness of code is historically unimportant, but the recent accessibility

work may eventually make it become a small ranking factor. That said, Matt Cutts downplays it because

40% of the web doesn’t validate (http://www.mattcutts.com/blog/more-seo-answers-on-video/).

Content on google.com itself does not validate, at the moment of writing this text. You can use the W3C

Markup Validation Service at http://validator.w3.org/ to test your web pages for compliance.

Detrimental “Red-Flag” Factors

Obviously writing spammy content, launching thousands of spammy doorway pages simultaneously, or

soliciting spammy links that actually get detected as such are detrimental in nature, but we will not continue

in that vein. Some of these factors are discussed in more detail in Chapter 8, “Black Hat SEO.”

UNIX script Q

2009-06-22T02:38:00.000-07:00

Long time since any posts...so here is one for all of you who would love to do some unix questions...

I have a file pattern.txt and another file lines.txt. I want the list of all lines in lines.txt that match any pattern in pattern.txt

The command maybe simple to all of you
grep -f pattern.txt lines.txt

Here I want the list of all lines in fileA but not in fileB

sort fileA fileB| uniq -u

Kill all processes by a user

kill -9 `ps -u -o "pid="`

List all files modified last week

find / -mtime -7 -print
+7 will give you more than a week ago

Thanking you,
Layman

Simulate SCP using SSH

2009-05-21T02:37:00.000-07:00

An interesting question
How to simulate scp using ssh ...
Using the same way you sud be able to run a script in your machine on the remote machine.

I assume that the reader is aware of what SCP and SSH is.

Lets try this...

deepak@deepak-laptop:~$ cat abcd.txt | ssh deepak@jeeves ' cat > abcd.txt;chmod 0777 abcd.txt;./abcd.txt;'

deepak@jeeves's password:
abcd.txt
Desktop

Thu May 21 14:40:58 IST 2009
/home/deepak
jeeves

deepak@deepak-laptop:~$ cat abcd.txt

ls
date
pwd
hostname

deepak@deepak-laptop:~$

So how does this work...
The cat wud obviously get the contents of the file and pipe it to the STDIN of the remote system. At the remote system the cat would redirect the contents of STDIN into the file (thereby creating the file) and then changing its permissions and then executing it.
Simple enough but not easy to find at once.

Other recommended scripts would be

cat abcd.txt | ssh deepak@jeeves ' cat -|bash' # remote exec of command
cat abcd.txt | ssh deepak@jeeves ' cat > filename' # scp

Thanking you
Layman

Learn to morph

2009-05-20T03:37:00.000-07:00

People look at morphing as a satanic act. To me , I feel there is nothing like that. I've loved morphing ever since I learned to do it. I have done many morphs which finally had some quality in it. I've loved outputs...results have always been my passion. So I guess thats one of the many reasons why I learned it. Later I gave up the act for a loved one. So here Iam to teach you how to morph...

You would either be on windows or linux . On windows I'm guess you would be using photoshop, and for all those linux users I would recommend using GIMP. I'm using GIMP to demonstrate this to you.

Get the 2 pics and open them in gimp

Use the scissor tool to cut out the face of the person

Select the face

Cut the face and paste it on a new transparent background page

Remove the unwanted areas of the image

Cut a small portion from the image (of arnie)

Paste it over the face of the image

Go to the layers window and select overlay. This will help you to match the color of the 2 images

Copy and paste the new image onto arnie

Scale the image suitably to match the head size of arnie

Use the smudge, blur and sharpen tools suitably to give the image a good look

The final image is ready

This doesnt look really good , I know, but I couldn't spend more time on this. If you would like to know more about morphing pls comment with your gtalk usernames.

I would have loved to show you how good I'm at this but I'm sorry blogger doesn't allow explicit images :p ;) . So please bear with me.

Thanking you
Layman

Enhanced public key cryptography

2009-05-19T03:32:00.000-07:00

I'm sure all of us would have heard about public key cryptography. Here I would like to propose a new idea which I suppose would enhance public key cryptography. This paper is no mumbo-jumbo. Its very simple and surprising. Please have a look and let me know...

AI'm sure all of us would have heard about public key cryptography. Here I would like to propose a new idea which I suppose would enhance public key cryptography. This paper is no mumbo-jumbo. Its very simple and surprising. Please have a look and let me know...

Definitions
Cipher - a cryptographic algorithm used to encrypt and decrypt files
and messages.
Ciphertext - the disguised (or encrypted) file or message.
Code - the usage of characters or words to represent words,
sentences, or ideas. Morse code is a common example, where
combinations of dots and dashes represent letters and numbers.
Cryptanalysis - the art of breaking cryptosystems. The process of
looking for errors or weaknesses in the implementation of an
algorithm or of the algorithm itself.
Cryptography - the art of creating and using cryptosystems.
Cryptology - the study of both cryptography and cryptanalysis.
Cryptosystem - the entire process of using cryptography. This
includes the actions of encrypting and decrypting a file or message, or
authenticating the sender of an e-mail message.
Key - a collection of bits,usually stored in a file, which is used to encrypt or decrypt a message.
Plaintext - the original message or file. After a file or message has been encrypted and then decrypted you should end up with the original file or message.Private Key - the secret key of a public-private key cryptography system. This key is used to "sign" outgoing messages, and is used to decrypt incoming messages.
Public Key - the public key of a public-private key cryptography system. This key is used to confirm "signatures" on incoming messages or to encrypt a file or message so that only the holder of the private key can decrypt the file or message.
Public-private Key Cryptography System - a cryptography system that uses two different keys to lock and unlock (encrypt and decrypt) messages and files. The two keys are mathematically linked together. An individual's public key is distributed to other users and is used to encrypt messages to the individual. The individual keeps the private key secret and uses it to decrypt messages sent with the public key.

Enhanced public key cryptography : A proposition
We have seen that even a public key system with n users would need 2*n number of keys to be stored. It may not seem very large for small systems. But as the value of n increases the size of the database also grows. This in fact slows down the system. Efficiency of the system decreases. As we have already discussed our concern is to further reduce the size of the data base. The basic idea is that we don't need to store the private key into the database. We would rather express the private key as a function of the public key. Private key = f (Public key) The first time a user registers to the system , the user is asked to enter his desired user name. Once he enters a user name (that doesn't exist already) , the system supplies him with a password. This password cannot be changed by the user in future. The password or rather the private key is calculate as a function of the public key. The function maybe to
simply add the ASCII values of characters used in the public key and then give the result of computation as the private key or password. So each time a user wants to login,he is required to enter his user name and password. The system calculates the original password for the user name as f(user name). Then the system checks whether f(user name),and the entered password matches. If they match the user can connect to the system. Otherwise he is not allowed to connect. So the basic idea is to calculate the real password from the user name applying the function and then match it with the password entered by the user. The advantage here is that for n users we need to store only n entries of use names. No password is stored.
However there is one serious disadvantage for this system. If a cryptanalyst gets a number of combinations of the user names and passwords he may succeed in finding the transformation performed by the function 'f(user name)'. If that happens he will be able to get the passwords for each and every user. Then the system fails completely. To avoid such a failure what we do is that we use a number of
functions rather than a single function. So the cryptanalyst can't find any similarity in the way the passwords are generated . The function used to calculate the password for a user depends on the position of the user name in the database. We shall consider an example. Suppose there are n users already registered in the database and there are m distinct functions available in the system to calculate the
value of the password from the user name. A new user wants to register to the system. The desired user name is 'abcn1'. Then the system writes his user name at the end of the database. So position of the new user will be n+1. We then calculate the (n+1)th number in the Fibonacci series. Say the number is p. We perform p%m ( where m is the number of functions the system uses to calculate the passwords
from the user name). We know that 0 <= p%m <>
EPKC vs PCK
PCK uses the inefficient linear search for retrieving the username and password(ie the public and private keys of a user). Linear search efficieny is O(n). So this is considered inefficient. Sometimes its possible to use binary search to improve the search times. But then, sorting must be done during insertion. This is a tedious process. This will lead to greater insertion times. Thus still inefficient.
Now lets see about the proposed EPCK. Here search (or rather calculation )is done via a hashing. Once the key pairs are entered by the user to login, the system can use a hashing process to retrieve the function to calculate the private key. Then this function can map the public key to the private key in a unique way. It's well known that hashing process has a search time of O(1). There are some additional processes done before and after hashing. Considering all these processes we can sum up that EPCK search times is by all means comparable to PCK. In terms of space efficiency PCK is far behind EPCK. PCK is 50%(nearly) more space efficient. This is because in EPCK we don't store the private key of the users. And in terms of security domain. In PCK we would need to secure the database using strong firewalls. This means additional cost. Still it's not possible to be sure of 100% security. In the age of systems like the bruteforce we cant rely on any security providers. EPCK since they
don't need to store any private key don't need any protection to the database. Maybe a small amount of write protection can be done. Thus EPCK is more space efficient than PCK. Also its less expensive than PCK.

This is a picture of an EPCK database.

The proposed system requires lesser memory space(half the memory space) compared to public key systems without compromising the security of the system. Thus the efficiency of the communication system will improve tremendously,without sacrificing the security of the system.

Thanking you
Layman

Language interpreter

2009-05-19T02:35:00.000-07:00

Its been some time since I was struck with this idea of an mini-language interpreter.
I started imagining it in the lines of an interpreter that could possibly understand scripts similar to the those written it the traditional bash shell scripts.
The work took some time. I choose perl to build the interpreter. The reason is obvious . The first reason was that I'd learned perl , and I wanted to use it somewhere. Second reason was that it was easier to do pattern matching in perl. So I started with what I call now the "Language Interpreter developed in perl". I'd initially scanned the web for tutorials that could help me on the project. I couldn't find any. I failed to find any documents on the web in a similar line. So after doing a fair amount of work and obtaining reasonable amount of results I thought I should post this on the web. So here it is...

#!/usr/bin/perl -w

while(<>)
{
chomp($_);
if($_) {match1($_);}
}

sub match1
{
$_=$_[0];

if(/^while$([^$]*)\){(.*)}$/)
{
#print "\nstat1 :",$1," ",$2,"\n";
$_=$1;
my $statements=$2;
if(/^([a-zA-Z][a-zA-Z0-9]*)([<>=!]*)([a-zA-Z0-9]+)$/)
{
my $lhs=symtabretrieve($1);
my $op=match($2);
my $rhs=match($3);
my $idl=$1;
my $idr=$3;
if($rhs==8) {$rhs=symtabretrieve($3);}
elsif($rhs==1) {$rhs=$3;}
if($op==2)
{
while($lhs<$rhs)
{
if($statements) {match1($statements);}
$lhs=symtabretrieve($idl);
$rhs=match($idr);
if($rhs==8) {$rhs=symtabretrieve($idr);}
elsif($rhs==1) {$rhs=$idr;}
}
}
elsif($op==3)
{
while($lhs>$rhs)
{
if($statements) {match1($statements);}
$lhs=symtabretrieve($idl);
$rhs=match($idr);
if($rhs==8) {$rhs=symtabretrieve($idr);}
elsif($rhs==1) {$rhs=$idr;}
}
}
elsif($op==4)
{
while($lhs>=$rhs)
{
if($statements) {match1($statements);}
$lhs=symtabretrieve($idl);
$rhs=match($idr);
if($rhs==8) {$rhs=symtabretrieve($idr);}
elsif($rhs==1) {$rhs=$idr;}
}
}
elsif($op==5)
{
while($lhs<=$rhs)
{
if($statements) {match1($statements);}
$lhs=symtabretrieve($idl);
$rhs=match($idr);
if($rhs==8) {$rhs=symtabretrieve($idr);}
elsif($rhs==1) {$rhs=$idr;}
}
}
elsif($op==6)
{
while($lhs==$rhs)
{
if($statements) {match1($statements);}
$lhs=symtabretrieve($idl);
$rhs=match($idr);
if($rhs==8) {$rhs=symtabretrieve($idr);}
elsif($rhs==1) {$rhs=$idr;}
}
}
elsif($op==7)
{
while($lhs!=$rhs)
{
if($statements) {match1($statements);}
$lhs=symtabretrieve($idl);
$rhs=match($idr);
if($rhs==8) {$rhs=symtabretrieve($idr);}
elsif($rhs==1) {$rhs=$idr;}
}
}

}

return;

}

elsif(/^if$([^$]*)\){(.*)}$/)
{
#print "\nstat2 :",$1," ",$2,"\n";
$_=$1;
my $statements=$2;
if(/^([a-zA-Z][a-zA-Z0-9]*)([<>=!]*)([a-zA-Z0-9]+)$/)
{
my $lhs=symtabretrieve($1);
my $op=match($2);
my $rhs=match($3);
my $idl=$1;
my $idr=$3;
if($rhs==8) {$rhs=symtabretrieve($3);}
elsif($rhs==1) {$rhs=$3;}
if($op==2)
{
if($lhs<$rhs)
{
if($statements) {match1($statements);}
$lhs=symtabretrieve($idl);
$rhs=match($idr);
if($rhs==8) {$rhs=symtabretrieve($idr);}
elsif($rhs==1) {$rhs=$idr;}
}
}
elsif($op==3)
{
if($lhs>$rhs)
{
if($statements) {match1($statements);}
$lhs=symtabretrieve($idl);
$rhs=match($idr);
if($rhs==8) {$rhs=symtabretrieve($idr);}
elsif($rhs==1) {$rhs=$idr;}
}
}
elsif($op==4)
{
if($lhs>=$rhs)
{
if($statements) {match1($statements);}
$lhs=symtabretrieve($idl);
$rhs=match($idr);
if($rhs==8) {$rhs=symtabretrieve($idr);}
elsif($rhs==1) {$rhs=$idr;}
}
}
elsif($op==5)
{
if($lhs<=$rhs)
{
if($statements) {match1($statements);}
$lhs=symtabretrieve($idl);
$rhs=match($idr);
if($rhs==8) {$rhs=symtabretrieve($idr);}
elsif($rhs==1) {$rhs=$idr;}
}
}
elsif($op==6)
{
if($lhs==$rhs)
{
if($statements) {match1($statements);}
$lhs=symtabretrieve($idl);
$rhs=match($idr);
if($rhs==8) {$rhs=symtabretrieve($idr);}
elsif($rhs==1) {$rhs=$idr;}
}
}
elsif($op==7)
{
if($lhs!=$rhs)
{
if($statements) {match1($statements);}
$lhs=symtabretrieve($idl);
$rhs=match($idr);
if($rhs==8) {$rhs=symtabretrieve($idr);}
elsif($rhs==1) {$rhs=$idr;}
}
}

}

return;
}

elsif(/^([a-zA-Z][a-zA-Z0-9]*)=([a-zA-Z0-9]+)$/)
{
#print "\nstat3 :",$1," ",$2,"\n";
syminsert($1,$2);
return;
}

elsif(/^([a-zA-Z][a-zA-Z0-9]*\[[0-9][0-9]*\])=([a-zA-Z0-9]+)$/)
{
#print "\nstat4 :",$1," ",$2,"\n";
syminsert($1,$2);
return;
}

elsif(/^([a-zA-Z][a-zA-Z0-9]*)=([a-zA-Z0-9]+)([p\+\-\*\/\%])([a-zA-Z0-9]+)$/)
{
#print "\nstat5 :",$1," ",$2,"\n";
if(match($2)==1) {$frstopd=$2;}
else {$frstopd=symtabretrieve($2);}
if(match($4)==1) {$scndop=$4;}
else {$scndop=symtabretrieve($4);}
$op=match($3);
if($op==9)
{
$val=$frstopd+$scndop;
syminsert($1,$val);
}
if($op==10)
{
$val=$frstopd-$scndop;
syminsert($1,$val);
}
if($op==11)
{
$val=$frstopd*$scndop;
syminsert($1,$val);
}
if($op==12)
{
$val=$frstopd/$scndop;
syminsert($1,$val);
}
if($op==13)
{
$val=$frstopd+$scndop;
syminsert($1,$val);
}
return;
}

elsif(/^echo \$([a-zA-Z0-9]+)\[\$?([a-zA-Z0-9][a-zA-Z0-9]*)\]$/)
{
#print "\nstat6 :",$1," ",$2,"\n";
$index=symtabretrieve($2);
if($index==undef)
{
$index=$1."[".$2."]";
print symtabretrieve($index);
}
else
{
$pr=$1."[".$index."]";
print symtabretrieve($pr);
}
print "\n";
return;
}

elsif(/^echo \$([a-zA-Z0-9]+)$/)
{
#print "\nstat7 :",$1,"\n";
print symtabretrieve($1);
print "\n";
return;
}

elsif(/^echo ([^;]*)$/)
{
#print "\nstat8 :",$1,"\n";
print $1;
print "\n";
return;
}

elsif(/^if/ || /^while/)
{
if(/^(.*});(.*)/)
{
my @temp=split(//,$1);
my $c=$2;
my $a="";
my $b="";
my $char='';
my $count=1;
while(@temp)
{
$char=shift(@temp);
$a.=$char;
if($char eq '{')
{
while($count)
{
$char=shift(@temp);
$a.=$char;
if($char eq '{') {$count++;}
elsif($char eq '}') {$count--;}
}
}
if(!$count) {$b=join('',@temp); @temp=();}
}
#print "\nstat9 :A:",$a," B:",$b," C:",$c,"\n";
if($a) {match1($a);}
if($b) {match1($b);}
if($c) {match1($c);}
}

return;
}

elsif(/^(.*?);(.*)$/)
{
#print "\nstat10 :A",$1," B:",$2,"\n";
my $a=$1; my $b=$2;
if($a) {match1($a);}
if($b) {match1($b);}
return;
}

}

sub match
{
$_=$_[0];
if(/^[0-9]+$/) {return 1;}
elsif(/^<$/) {return 2;}
elsif(/^>$/) {return 3;}
elsif(/^>=$/) {return 4;}
elsif(/^<=$/) {return 5;}
elsif(/^==$/) {return 6;}
elsif(/^!=$/) {return 7;}
elsif(/^[a-zA-Z0-9]+/) {return 8;}
elsif(/^\+/) {return 9;}
elsif(/^\-/) {return 10;}
elsif(/^\*/) {return 11;}
elsif(/^\//) {return 12;}
elsif(/^\%/) {return 13;}
else {return 0;}
}

sub syminsert
{
$symtab{$_[0]}=$_[1];
}

sub symtabretrieve
{
return $symtab{$_[0]};
}

The results I should say is only a miniature version of the project. And the code isn't fully shown. Your comments would be greatly appreciated.

Thanking you,
Layman