1. Write a C++ program to compute the Binomial Coefficient to construct a 2D arr
ID: 3766280 • Letter: 1
Question
1. Write a C++ program to compute the Binomial Coefficient to construct a 2D array using two input parameters: n and k Then once the table is constructed Display the entire table according to rows and columns. Give user a choice of computing the Binomial coefficient at various values of n and k using this table,i.e. prompt the user to enter a value of i and j (i <= n and j <= k), code first test if the input for i and j are within the limits, then using the B table constructed, display the value of B[i][j]
Explanation / Answer
Binomial Coefficient
Write a function that takes two parameters n and k and returns the value of Binomial Coefficient
C(n, k). For example, your function should return 6 for n = 4 and k = 2, and it should return 10
for n = 5 and k = 2.
Optimal Substructure :
The value of C(n, k) can recursively calculated using following standard formula for Binomial Cofficients. C(n, k) = C(n-1, k-1) + C(n-1, k) C(n, 0) = C(n, n) = 1
Overlapping Subproblems
Following is simple recursive implementation that simply follows the recursive structure mentioned above.
// A Naive Recursive Implementation
#include<stdio.h>
// Returns value of Binomial Coefficient C(n, k)
int binomialCoeff(int n, int k)
{ // Base Cases
if (k==0 || k==n) return 1;
// Recur return binomialCoeff(n-1, k-1) + binomialCoeff(n-1, k);
}
/* Drier program to test above function*/
int main()
{ int n = 5, k = 2;
printf("Value of C(%d, %d) is %d ", n, k, binomialCoeff(n, k)
);
return 0;
}
It should be noted that the above function computes the same subproblems again and again. See the following recursion tree for n = 5 an k = 2. The function C(3, 1) is called two times. For large values of n, there will be many common subproblems.
C(5, 2)
/
C(4,1) C(4,2)
/ /
C(3,0) C(3,1) C(3,1) C(3,2)
/ / / /
C(2,0) c(2,1) C(2,0) C(2,1) C(2,1) C(2,2)
/ / /
C(1,0) C(1.1) C(1,0) C(1,1) C(1,0) C(1,1)
Since same suproblems are called again, this problem has Overlapping Subprolems property. So the Binomial Coefficient problem has both properties of a dynamic programming problem. Like other typical Dynamic Programming(DP) probmles, recomputations of same subproblems can be avoided by constructing a temporary array C[][] in bottom up manner. Following is Dynamic Programming based implementation.
// A Dynamic Programming based solution that uses table C[][] to calculate
the // Binomial Coefficient
#include <studio.h>
// Prototype of a utility function that returns minimum of two integers
int min(int a, int b);
// Returns value of Binomial Coefficient C(n, k)
int binomialCoeff (int n, int k)
{
int C[n+1][k+1];
int i, j;
// Caculate value of Binomial Coefficient in bottom up manner
for (i = 0; i <= n; i++)
{
for (j = 0; j <= min(i, k); j++)
{
// Base Cases
if (j == 0 || j == i)
C[i][j] = 1;
// Calculate value using previosly stored values
else
C[i][j] = C[i-1][j-1] + C[i-1][j];
}
}
return C[n][k];
}
// A utility function to return minimum of two integers
int min (int a, int b)
{
Return (a<b)?a:b;
/* Drier program to test above function*/
int main()
{
int n = 5, k = 2;
printf ("Value of C(%d, %d) is %d ", n, k, binomialCoeff(n, k) );
return 0;
}
Time Complexity: O(n*k)
Auxiliary Space: O(n*k)
// A space optimized Dynamic Programming Solution
int binomialCoeff(int n, int k)
{
int* C = (int*)calloc(k+1, sizeof(int));
int i, j, res;
C[0] = 1;
for(i = 1; i <= n; i++)
{
for(j = min(i, k); j > 0; j--)
for(j = min(i, k); j > 0; j--) C[j] = C[j] + C[j-1];
}
res = C[k]; // Store the result before freeing memory
free(C);
return res;
Time Complexity: O(n*k)
Auxiliary Space: O(k)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.