CIS 2520 ASSIGNMENT 1

Due: September 29, 2009

(1) (30%) Write a short C program that outputs all possible strings formed by using the characters 'c', 'a', 'r', 'b', 'o', and 'n' exactly once.

(2) (30%) Ackermann's function A(m, n), is a two argument function defined as follows:

A(0, n) = n + 1	for n >= 0
A(m, 0) = A(m-1, 1)	for m > 0
A(m, n) = A(m-1, A(m, n-1))	for m, n > 0

Write a recursive function that gives the value of Ackermann's function.

Test your program to find out that for what range of integer parameters, (m, n), does the output of your implementation not exceed the value of the maximum integer in your C system?

(3) (40%) Let x be a positive real. To calculate the square root of x by Newton's method, so that the square of the solution differs from x to within an accuracy of epsilon, we start with an initial approximation a = x/2. If |a*a - x| <= epsilon, we stop with the result a. Otherwise we replace a with the next approximation, defined by (a + x/a)/2. Then, we test the result again. In general, we keep on computing and testing successive approximations until we find one close enough to stop. Write two C functions, using recursion and non-recursion respectively, to implement the above algorithm. You should use a sequence of big real numbers and a small epsilon to test your program, and try to find the differences in execution time.

Note: You should follow your TA's instruction to submit your assignment.