Every Thing that Happens is for Good !!!

Diameter of a Tree

2006-01-04T01:34:00.000-08:00

This is a *ed problem in CLR (Algo Text Book).
Diameter of a tree is defined as the longest of all the shortest distances between any pair of nodes of the tree.

The Algorithm for finding the Diameter is.
1) Take any node and apply BFS.
2) Find the node that is farthest from the starting node.
3) Apply DFS with the farthest node as the starting node.

This will give the Diameter of the tree.

More Bit Manipulations !!!

2005-11-27T11:20:00.000-08:00

This Page contains really good bit manipulations. You will really start appreciating the magic of bit manipulations after going over the algos in this Page.

http://aggregate.org/MAGIC/ .

Happy reading.

Snoob

2005-11-26T00:16:00.000-08:00

This function calculates the next highest number with the same number of bits. Below is the source code of the function which I got from the site http://tykje.com/talk/


unsigned snoob(unsigned x) {
   unsigned smallest, ripple, ones;
                                // x = xxx0 1111 0000
   smallest = x & -x;           //     0000 0001 0000
   ripple = x + smallest;       //     xxx1 0000 0000
   ones = x ^ ripple;           //     0001 1111 0000
   ones = (ones >> 2)/smallest; //     0000 0000 0111
   return ripple | ones;        //     xxx1 0000 0111
}

Wonderful function this is.I have started admiring what bit manipulations can do.

next_permutation !!!

2005-11-25T12:05:00.000-08:00

STL provides a simple and a very useful function called next_permutation which takes a sequence and generates permutation in a lexicographical order. This function does not even generate repeated permutations when some of the elements of the sequence are repeated. So this makes it much more useful. Suppose we write a normal recursive function for generating permutations we have to take special care of the repeating characters.

Following is the algo for the next permutation.
Consider a permutation a1,a2,a3,... an.
find a pointer i such a(i)< a(i+1). Once u find this pointer i , repeat again from the right end of the array to find a value >= a(i). Let this value pointed by the pointer j.
Now swap (a(i) , a(j)) and then reverse array from a(i+1) to a(n).
This permutation will be the next permutation. The order of this Algo is O(n) where n is the number of elements of the array. The condition a(i) < a(i+1) is responsible for non repetition of permutations when a element occurs more than once in the array.

Absolute value of a floating point number.

2005-11-25T09:47:00.000-08:00

Simplest way,
a = a>0?a:-a; where a is the floating point nnumber.

But if we notice the way the floating point numbers are stored in a system using IEEE format... Then we will find that a separate bit is assigned for the sign of this number. Now this sign bit is 0 for positive numbers and 1 for negative numbers. So Just manipulating this bit will give the absolute value of a floating point number.

*((int*)&a) &= 0x7fffffff;
will do the same as the above mentioned method. Now how will you find the absolute value of a Double precision floating point number ?? :)

Diff Algorithm!!!

2005-11-17T01:40:00.000-08:00

I use diff a lot for many sorts of stuff.... But I never thought about what the algorithm for the diff util could be. I came to know that Diff uses LCS (Longest common subsequence) Algorithm. Still want to learn how they have efficiently implemented matching lines for the algo.

So iam trying to see through the Diff source code. Will update this post once I have done with the Diff source code.

Hello World !!

2005-11-16T00:42:00.000-08:00

This is my first blog. :) . Most probably will be a technical one . Just to remember all that I have learnt and all that I would like to learn.