CS420 Assignment one

Consider the following C program, implementing the Ackermann function:

#include <stdio.h>

int c;

main()
 { int m,n;
   scanf("%d %d", &m, &n);
   c = 0; 
   printf("ack(%d,%d)= %d \n", m,n,ack(m,n));
   printf("#calls = %d \n", c );
 }

int ack (int m, int n)
 { c = c+1;
   if        (m==0)       return(n+1);
   else if   (n==0)       return(ack(m-1,1));
	else              return(ack(m-1,ack(m,n-1)));
 }

 a) Derive recurrence relations for the values of ack(m,n) for m=1,2,3.
    These will become recurrence relations with the variable n.
    Solve these recurrence relations, creating expressions for the ack(m,n)
    values.

 b) Similarly, derive and solve recurrence relations in n for the number of 
    function calls executed by the above program (the value of c in the program) 
    for m=1,2,3.

    For m=3, the sum expressions get rather complex. You can leave these
    sum expressions as they are (or you can work them out).

    Verify your answers eg for ack(1,1), ack(2,2) and ack(3,3)

It is OK to consult sources (books, web pages, ...), but if you do so, 
you still need show the derivations, also,  you always need to quote 
your sources.