CSE 4833/6833 Introduction to Algorithms Programming Assignment 3, due Thursday,
ID: 3604784 • Letter: C
Question
CSE 4833/6833 Introduction to Algorithms Programming Assignment 3, due Thursday, Nov 2, by midnight. Worth 25 points.
In Discrete Structures you used the binomial coefficient formula, C(n, k) = n! k!(n k)! to calculate the number of combinations of “n choose k,” that is, the number of ways to choose k objects from n objects. For example, the number of unique 5-card hands from a standard 52-card deck is C(52, 5). A problem with using the above formula to compute binomial coefficients is that n! grows very fast and overflows an integer representation before you can do the division to bring the value back to a value that can be represented. When calculating C(52, 5), for example, the value of 52! = 80, 658, 175, 170, 943, 878, 571, 660, 636, 856, 403, 766, 975, 289, 505, 440, 883, 277, 824, 000, 000, 000, 000 is much bigger than can fit into a 64-bit integer representation. Fortunately, C(52, 5) can also be defined recursively by splitting the problem into two smaller subproblems. Consider card hands containing a specific card, say the ace of clubs, and those that do not. For hands that do contain the ace of clubs, we need to choose 4 more cards from the remaining 51 cards, i.e., C(51, 4). For hands that do not contain the ace of clubs, we need to choose 5 cards from the remaining 51 cards, i.e., C(51, 5). Therefore, C(52, 5) = C(51, 4) + C(51, 5). This point of view leads to the following recurrence for computing the binomial coefficient C(n, k): C(n, 0) = 1 C(n, k) = 1, if k = n C(n, k) = C(n 1, k) + C(n 1, k 1), if 0 < k < n Given this recurrence, we can write the following recursive function to compute C(n, k). i n t C ( i n t n , i n t k ) { / / Assume 0 <= k <= n 1 i f ( k == 0 | | k == n ) 2 r e t u r n 1 ; 3 e l s e r e t u r n C ( n1, k ) + C ( n1, k1) ; 4 } 5 However, this divide-and-conquer approach to computing binomial coefficients is very slow due to redundant calculations performed by the recursive calls, similar to the slow, divide-and-conquer approach to computing Fibonacci numbers. This programming assignment has two parts. First, write a C program that uses dynamic programming, instead of divide-and-conquer, to compute C(n, k). Second, write a C program that uses memoization, which is a special form of dynamic programming, to compute C(n, k). 1 The basic dynamic programming approach is “bottom-up.” It solves subproblems in order from smallest to largest until the original problem is solved. Memoization is a dynamic-programming technique that uses the “top-down” recursive definition to solve only the needed smaller problems, and avoids redundant calculations by solving smaller-problems once and storing their solutions. The code below uses memoization to compute Fibonacci numbers. Before solving a smaller problem, it checks to see if its solution is already stored. i n t fib memo ( i n t n , i n t f i b o n a c c i [ ] ) { 1 i f ( f i b o n a c c i [ n ] == 1) { 2 f i b o n a c c i [ n ] = fib memo ( n1, f i b o n a c c i ) 3 + fib memo ( n2, f i b o n a c c i ) ; 4 } 5 r e t u r n f i b o n a c c i [ n ] ; 6 } 7 8 i n t f i b ( i n t n ) { 9 / / a r r a y t o s t o r e s o l u t i o n s 10 i n t f i b o n a c c i [ n + 1 ] ; 11 / / f i l l b a s e c a s e s 12 f i b o n a c c i [ 0 ] = 0 ; 13 f i b o n a c c i [ 1 ] = 1 ; 14 / / Use 1 f o r unknown s o l u t i o n s 15 f o r ( i = 2; i <= n ; i ++ ) { 16 f i b o n a c c i [ i ] = 1; 17 } 18 r e t u r n fib memo ( n , f i b o n a c c i ) ; 19 } 20 Using this code as a guide, implement an algorithm that uses memoization to compute binomial coefficients. What to turn in Turn in a copy of the program you wrote for computing binomial coefficients using both bottom up dynamic programming and memoization. Your code should be written in C/C++, or, if you prefer, you can use Python. In addition, turn in a demonstration that your code works correctly, and an experimental comparison of the efficiency of the divide-and-conquer, bottom-up dynamic programming, and memoization algorithms. Does the memoization algorithm solve fewer subproblems than the bottom-up dynamic programming algorithm? Briefly explain.
Explanation / Answer
Tabulation Vs Memoization :
In Tabulation we will solve the problem from bottom by taking the base values and try to calculate the main problem.
In memoization we will solve the problem top down by taking the problem and caching the result and then solving the subproblem if it is not there in the cache.
Thats why comparitively memoization will give better results for longer inputs
The following code is for memoization: (TopDown)
#include<stdio.h>
int binomialCoeff(int n,int k);
int Binom_coeff_memoization(int table[][], int i, int j);
int main()
{
int n = 8, k = 3;
printf ("Value of C(%d, %d) is %d ", n, k, binomialCoeff(n, k) );
return 0;
}
int binomialCoeff(int n,int k){
int table[n][n]; //initialize all with zeroes
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)
table[i][j]=0;
}
return Binom_coeff_memoization(&table[0][0], n, k);
}
int Binom_coeff_memoization(int table[i][i], int i, int j){
if (j==0 || j==i)
table[i][j]=1;
else
if (table[i-1][j-1]==0)
table[i-1][j-1]=Binom_coeff_memoization(table, i-1, j-1);
if (table[i-1][j]==0)
table[i-1][j]=Binom_coeff_memoization(table, i-1, j);
table[i][j]=table[i-1][j-1] + table[i-1][j];
return table[i][j];
}
The following code is for Tabulation : (Bottomup)
//Tabulation version of binomial coefficient..
// A Dynamic Programming based solution that uses table C[][] to
// calculate the Binomial Coefficient
#include<stdio.h>
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];
}
int min(int a, int b)
{
return (a<b)? a: b;
}
/* Drier program to test above function*/
int main()
{
int n = 8, k = 3;
printf ("Value of C(%d, %d) is %d ", n, k, binomialCoeff(n, k) );
return 0;
}