Archive for the ‘Mathematics’ Category

Mathematical Genius ‘Grigori Perelman’ wins Fields Medal

August 23, 2006 2 comments

I just read that Mathematical Genius “Grigori Perelman” has shunned off the “Fields Medal” – an equivalent of Nobel Prize for Mathematics offered to him in August 2006. He claims to have solved one of seven, Millennium Prize Problems, known as Poincaré Conjecture. His claim has been severely scrutinized by a panel of extra ordinary mathematicians which includes Sir Andrew Wiles who solved the famous and toughest problem in mathematical history, “Fermats Last Theorem” and became famous world wide. Now this shows what a real humble and great human Grigori is, no charm for fame and publicity. The problem has been nominated by Clay Institute Mathematics as one of toughest problem of millennium to be solved. Grigory is a brilliant and most extra ordinary mathematician of Russia having great works in Geometric Topology and Reimannian Geometry. I am not an expert on topology or the subjects related but I have read about them and they are literally too tough, and having them solved is by far a great, great achievement. I hope I am able to reach such heights in Computer Science, one day 🙂.

Categories: General, Mathematics

Finding or detecting a loop/cycle in Link List.

July 27, 2006 1 comment

One of famous questions asked in programming technical interviews is “Finding a loop in a linear linked list”. Apparently this problem is easy, but if one has interest in Algorithms and Complexity Theory this is a very interesting problem also related to number theory.

The most famous method to solve this problem is to use Floyd’s algorithm to find cycle in lists also known as “The Hare and the Tortoise Algorithm”, intersting :). If a list has a cycle in it, it can be detected using this algorithm. This algorithm can also be used to find cycles in “Pseudo-Random Sequences”. The algorithm to find the cycle in linked list is as follows.

Take two pointers pointing to head. Now advance one pointer to one node and other pointer to two nodes each time while iterating. This is the simple algorithm, and that’s it. If the first pointer enters the loop (cycle part of algorithm) it is guaranteed that the second pointer will be at some node in the loop at the same time when other pointer is pointing to same node. The result may come out by some iteration, but it’s assured. That’s because one pointer is iterating each node in loop and other is iterating alternating nodes, so at first or second iteration while in the loop it will catch the first pointer at same node. This is indeed a very good find. I tried this with moving the second pointer to three nodes at one time and it worked also though I had to iterate many times. By using this approach we can also find the number of nodes in the loop which is an interesting thing to try.