Problem 1 The binomial coefficient, binom(n,m), occurs frequently in mathematics

Question

Problem 1

The binomial coefficient, binom(n,m), occurs frequently in mathematics. This value can be computed recursively as follows:

binom(n,m) = binom(n-1,m) + binom(n-1,m-1), where 0 m n, binom(n,0) = 1, and binom(n,n) = 1.

Write a C program to compute binom(n,m) recursively. The values for n and m should be passed as command-line arguments with appropriate error checking.

Measure the execution time of your program as you vary the values of m and n. Plot this execution time as a function of n with different lines for various values of m. You should measure the execution time for each data point at least five times. Choose values of m and n such that your execution time ranges from less than a second to more than 30 seconds. What relationship do you see between m, n, and the execution time?

Problem 2.

Repeat Problem 1, but compute binom(n,m) iteratively, that is, without recursion. Measure the execution time of your program and compare the execution times of the two versions of the program. Which one is faster? Why?

Explanation / Answer

Here is the code for recursive and iterative implementation . It also times the execution. Please dont forget to rate the answer if it helped. Thank you very much.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/*recursive implementation */
long binomialRecursive(int n, int m)
{
/*base condtion*/
if(m == 0 || m == n)
return 1;
return binomialRecursive(n - 1, m) + binomialRecursive(n - 1, m - 1);

}

/*Iterative implementation : works by storing all calculated values in a 2D array, so that recomputatio is not needed*/
int binomialIterative(int n, int m)
{
long B[n+1][m+1];
int i, j;

/* calculate all values and store them*/
for (i = 0; i <= n; i++)
{
for (j = 0; j <= m; j++)
{
/*base condition*/
if (j == 0 || j == i)
B[i][j] = 1;

/* calculate using previosly stored values*/
else
B[i][j] = B[i-1][j-1] + B[i-1][j];
}
}

return B[n][m];
}
int main(int argc,char *argv[])
{
int n, m;
long binom;
clock_t t1, t2;
double elapsed;
if(argc != 3)
{
printf(" Usage: <program> <n> <m>");
return 1;
}
else
{
n = atoi(argv[1]);
m = atoi(argv[2]);
if(m > n)
{
printf(" m should be less than or equal to n");
return 1;
}
else
{
/*timing iterative binomial function*/
t1 = clock();
binom = binomialIterative(n, m);
t2 = clock();
elapsed = (double) (t2 - t1) / CLOCKS_PER_SEC;

printf(" Iterative binomial( %d , %d ) = %ld took %f seconds ", n, m, binom, elapsed);

/*timing recursive binomial function*/
t1 = clock();
binom = binomialRecursive(n, m);
t2 = clock();
elapsed = (double) (t2 - t1) / CLOCKS_PER_SEC;

printf(" Recursive binomial( %d , %d ) = %ld took %f seconds ", n, m, binom, elapsed);
}
}
}

output

/a.out 30 15

Iterative binomial( 30 , 15 ) = 155117520 took 0.000007 seconds
Recursive binomial( 30 , 15 ) = 155117520 took 1.374279 seconds

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.