ACKERMANN RECURSION MYSTERY

RECURSION   is one of the beautiful techniques of programming. Instead of repeating the whole code, several programmers are using this technique in their programs. But using recursion is not a good programming methods, since it will consume memory space and other resources. There are large number of problems in computer science which depends upon the recursion for their result. Some of them are Fibanocci numbers, Factorial, Towers of Hanoi problem, N-queens problem, DFS,BFS, most of the tree and graph related problems etc.

ACKERMANN function is a problem which works using the principles of recursion, especially tail recursion. The peculiarity of the function is that the output will be obtained for the small values very rapidly and if the input values exceed one particular number then the function behaves like an algorithm which never comes up with the answer. The tracing of the function for small values can be done with ease effort. The function is described as follows

                                              A(m,n) =   n + 1 ,                         if    m=0;
                                                            =   A(m-1,1),                  if    n=0;
                                                            =   A(m-1, A(m, n-1))   otherwise;


The values m and n must be greater than or equal to zero. If we execute this program with the values A(3,2) we will get 29. similarly if A(3,3) we will get 61. If we go beyond 4 or 5 it will take large amount of time, Sometimes years!!!!!!!!!!!!!. In that condition the complexity of the program as explained in some books looks like


                                                               .....
                                                             .... 
                                                           2
                                                         2
                                                       2


A slope of 2's arranged one above the other..

Ackermanns function is a typical example of tail recursion.. Some people may say as a joke that running complex recursive algorithms are worth enough  for giving training to the processors...

UNROLLING "DFS" :: THE SLOWEST APPROACH

DFS: Depth First Search is the most familiar graph traversal method which is used in large number of searching application. A graph traversal is a systematic procedure of visiting all the nodes. The basic data structure for the DFS is stack. And we implement the procedures using the basic elements of programming.

Beyond all these implementation details, these methods convey various other concepts. Some of them are described below.
1. E-Node.
2. L-Node.
3. D-Node.
4. Discovery time.
5. Departure time.

Sometimes while programming we didn't pay attention to these stuffs. But they can provide a great information, when we extend the algorithms for solving the network related issues.

E-NODE ( Expanding or Exploring)

Node which is currently being explored or whose children is being generated is E-Node. There can be only one E-Node at a time during the traversal.

L-NODE (Live Node)

The node which has not been fully explored or all of the two children has not been generated is live node. There can be many number of live nodes during the traversal.

D-NODE(Dead Node)

The node which is not explored or all of its children has been generated is Dead Node.

TWO TIME CONCEPTS:

DISCOVERY TIME:

It is the time when we discover a particular node.

DEPARTURE TIME:

It is the time when we leave a node after exploring all the children

We usually say DFS as multiple DFS, because E-Node can be started from any node.

The unrolling of DFS can be visualised by the following graph


 The working of the DFS algorithm based on the concepts of the nodes and times is as follows. Starting from the node 1. At time 1 we discovered the node numbered 1. At present the E-NODE is node 1. From the first node we have two possibilities. Either we can go for the 2nd or 3rd. For the time being we are going to discover the node numbered 2. At the moment we reach the node 2, node 1 will become the live node and node 2 will becomes the E node. Similarly the discovery time of the node 2 is 2. From 2nd node we can go to either 4 or 5. We are going to the 4th node correspondingly the node 2 will becomes the LIVE-NODE and node 4 will becomes the E-NODE. The discovery time is 3. Similarly we are going to other nodes in the sequence from the 4th node is as follows  4--8--7--3--6---. The corresponding discovery times is in the sequence 3--4--5--6--7. And the nodes except the 6th node will become the live node. The sixth node will becomes the E-NODE. The sixth node is devoid of any children which is unexplored. So the first departure takes place at the sixth node. The departure time is 8. we will return form the sixth node to the previous node. and it will become dead. On reaching the node 3 , there also no children remained unexplored. So returns to node number 7. and the node 3 will becomes dead. The departing time from the node 3 is 9. On reaching the node 7 the same process will happens. The departing time is 10. On reaching the node 8, Checks for any unexplored child. Here node 5 is unexplored. So the discovery time of the node 5 is 11...and the process is continues...The Whole process will come to an end when all the nodes of the graph becomes dead nodes..

The data structure view of these process shows the usage of stack for tracking the path. When a node becomes a live node, that node will be pushed in to the stack. When ever a node becomes a dead node, It will be popped from the stack. The whole process will comes to an end when the stack is empty.

There is another method called DFT. We usually DFS and DFT unknowingly at different places. There is a crucial difference between these two. DFT( Depth First Traversal) is  used on a FOREST. It is used for traversing when the graph is disjointed or disconnected. DFS using the strategy of backtracking, it is used to know whether a graph is connected or not , Verifying whether a node is reachable and finding the articulation points in the graph, which is very essential in solving network related problems..

Thats all the story of DFS..............................................................................................

The emergence of P and NP

P :   " This is the set of all decision problems solvable by deterministic algorithms in polynomial time "
NP: " This is the set of all decision problems solvable by non- deterministic algorithms in polynomial time "

Since Deterministic algorithms are special case of Non deterministic ones, We conclude that P C NP.

COOKS THEOREM:

Cooks  theorem is better known as cooks question. Is there any single problem in NP such that if it is showed to be in P then it would imply that P=NP ?  also


Satisfiability is in P iff P=NP
 

Maximum Clique -----"MAX --CLIQUE" Problem

This problem is one of the most familiar problem in computer science. The maximal complete subgraph of a graph G is a clique. The size of the clique is  the number of vertices in it. The max-clique problem is that finding the largest possible clique in the graph.

There is another definition for the clique. A clique is a set of vertices from the original graph G in which every vertex in the set have an edge with any other vertex in the set.

This is an optimisation problem. But it can be viewed in the angles of decision problem in the following way.

Does the graph can have a clique of size 6 ---NO
Does the graph can have a clique of size 5 ---NO
Does the graph can have a clique of size 4 ---yes

Thus the maximum clique has the size of 4.

Similarly satisfiablity problem, Node cover problem
etc are viewed in this way.

The mirage of NP, P and Co-NP conepts in computer science

The concepts of NP, P, and Co-NP problems were always confusing. Even during the engineering studies, after referring the most famous "fat" book "Design and Analysis of Algorithms" amble times the idea will not be impregnated in the mind. While reading the book, at one point of the peak all the concepts will clash at last we will have the condition that Co-NP is P? or will NP become P? etc. When I went to the ACE engineering academy eminent professors made me clear what exactly is happening between the P, NP, Co-NP.  The ideas are sharing here.

Before thinking of the NP, P, Co-NP we must be aware of the basic facts about the deterministic and non deterministic algorithms, Decision problems, Optimization problems, Reducibility, Polynomial-Equivalence properties etc.

The great division  of problems 

Basically computer science problems are broadly classified into two categories.

• Decidable problems

• Undecidable problems  

Decidable problems are the problems having algorithms. They are also divided into two categories. Deterministic and Non-deterministic algorithms. The basic differentiation in this way is based on the acceptance of the problems by a Deterministic Turing machine and Non - deterministic Turing machine.
Deterministic algorithms are again divided into polynomial time and exponential time algorithms.Polynomial time algorithms are the ones that can be solved in polynomial time complexity(O(n), O(n^2) etc). Exponential time algorithms are the ones that can be solved in exponential time complexity.(2^n, 3^n etc).

Non-deterministic algorithms are also divided in the same fashion as that of deterministic algorithms.

Why the problems are categorised into NP, NP-Hard, NP-complete, P?

The basic essence in the classification of the problems is that to show that the various problems in Computer Science are related. So in future if any scientist or researcher found out that a particular problem belong to any of these categories he can also prove that the other related problems are also belongs to the same category.

Non deterministic algorithms : First tool for the Analysis.

Every decidable problems have a non-deterministic algorithms. Determinism reveals that output is distinct. Non determinism shows that there can be more than one output for the input. Non deterministic algorithm  have basically two steps. Success and failure. Success signal is generated when the algorithm is successfully completed. Its complexity is O(1). Similarly failure is the signal generated when the algorithm fails. The interesting fact of these nondeterministic algorithms is that they are theoretical.

An example for the non-deterministic algorithm for searching.

 procedure nd_search(A[], n, x)
    {
       j = choice(i,n);
       if(A[j]==x)
         {
            write[j];
             success();
          }
        else
             failure(); 
     }

The above algorithm is a search algorithm which uses only  O(1)  time for its execution and it will returns the index of the searched element in the array of size n. The explanation is like this:  The above algorithm has a function called choice(1,n). The main job of this function is that it will returns the index of the searched element with O(1) complexity.!!! Naturally we may rise the question, How this is possible, even the fastest searching deterministic algorithm will takes at least log n  complexity? The answer to this question is very interesting. If a system have to return the index of the searched element atonce, that element have to be compared with every other element in the array at once. It can be done by using sufficient number of processors which compares the searched element with consecutive elements in the array parallely. If this can be done then it is possible to return the index of the searched element in O(1) time complexity. But this method is not practical. To arrange as much as processors as that of the array size is tedious and immaterial. So it is not possible. But our focus is on the nondeterministic algorithm. Thus every decidable problems have a nondeterministic algorithm. And it will be much faster than the deterministic one.
                                                
Decision Vs Optimization problems in computer science.

Any problem which has an output either YES (TRUE)or NO(FALSE)  is known as decision problem. Finding an optimal value for the criteria described in the problem ( It can be either minimum or maximum) belongs to the Optimisation problems. Every decision and optimization problems are interchangeable. Some of the examples of decision problems are N-Queens, Hamiltonian Cycle problem (Does there exists a cycle connecting all the vertices's exactly once) etc. The examples of Optimization problems include 0/1 Knapsack problem(minimum weight and maximum profit), Travelling sales man problem, Graph colouring problem ( minimum number of colours needed to mark all the vertices's differently.) etc. Interesting fact about these type of problems is that they can be converted to either of each other. The examples include the conversion of 0/1 knapsack optimisation problem into 0/1 knapsack decision problem by looking the problem in another way. Is it possible to get filled up the knapsack to get  maximum profit? the answer will be yes or no. Similarly, Is it possible to color a graph say with four adjacent vertices with two colours? NO, with three colours? NO, with four colours? YES. In computer science there are many standard problems that can be interchangeable between these two extremities. Some of them are max- clique, Satisfiability problem, Node cover problem  etc.