Flickr

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

Art of computer programming -Sorting #5

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

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

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

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

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

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