Archive for the ‘algorithms’ Category

There is really an interesting fact associated with the Theory of Computation (ToC). Like we say failures are stepping stones to success, the different aspects of ToC flourished out of failures.

McCulloch and Pitts were initially trying to formalize a mathematical model to simulate the functioning of brain through abstract neuron networks, but it failed to capture the entire notion of brain function, but this failure lead to the development of Finite State Machines.

Noam Chomsky was trying to formalize the human languages, but he realized that to frame the human languages into a mathematical set of rules is extremely complex, but this failure lead to the development of Context Free Grammar (CFG), which eventually lead to Backus Norm Form (a notation technique for CFG). It is surprisingly similar to the grammar of Sanskrit formalized by Panini (4th century BCE). So, CFG shares the grammar of Sanskrit, and this is one way by which Sanskrit is related to computation.

David Hilbert challenged the mathematicians with a famous question – “does there exists a general procedure/method to solve all the mathematical problems?”.  Hilbert believed there exists a procedure to do so (popularly known as entscheidungsproblem). This intrigued many mathematicians, and eventually Church and Turing proved that there is no such method. Hilbert did failed in his belief, but this has lead to the development of an elegant idea called Turing Machines. Turing wanted to first formalize what does Hilbert meant by “general procedure/method”, and he came up with a formal definition for “Algorithms” based on the idea of Turing Machine, and the notion of what is computable (tractable) and what is not computable (intractable) in reasonable amount of time.

How elegant it is to see that such failures had lead to a beautiful subject called Theory of Computation :)which eventually rules the entire modern day computer innovations.

Consider a doubly linked list whose structure of the node looks like this:

struct node
 struct node *arbitrary; /* can point to any node, including self or NULL */
 int data;
 struct node *next;      /* always points to the next node */

The next pointer points to its immediate next node, unless it is the last node, which obviously points to NULL. The arbitrary node can point to any other node in the list, including itself or NULL. We need to create a clone of the original doubly linked list – this will mean, the clone should preserve the structure / connectivity of the original, as well as the data.

Upon trying to understand the problem and to start thinking about the solution, we might initially feel an O(n) solution is not possible, or we might need to use a Hash data structure, and all such strange thoughts. The arbitrary field of first node can point to last node, the last node’s arbitrary can point to second node. How to bookkeep such information? The length of the list can be thousand or million or more.

So, this problem need to be solved without using temporary variables / arrays, and should run in time polynomial to length of list, ie. with space complexity O(1) and time complexity O(n).