Hey, I\'m having trouble with this question. I\'m not sure how to go about findi
ID: 648580 • Letter: H
Question
Hey, I'm having trouble with this question. I'm not sure how to go about finding the algorithm or how the dynamic programing solution will be different than the standard solution.
Your task is to produce an algorithm for (n k) that does not require multiplication, which means that the formula (n k) = n!/(n - k)!k! is not very useful. However, you can use (a) Write the algorithm (pseudo-code) the implements the above recursive definition. (b) What is the approximate time complexity of this algorithm? Are any cases particularly bad? (c) Design a dynamic programming solution to this problem, and write the algorithm. (d) What is the time complexity of this algorithm?Explanation / Answer
a)compute(n , k){
if(n >= 0 && (k == 0 || k == n)){
return 1;
}
return (compute(n-1 , k) + compute(n-1, k-1));
}
This is the resurcive algrithm to compute nCr without using multiplication
b)The approximate time complexity will be 2^n .As it will form a complete
binary tree since at each step we are calling two instances of the function compute
c)A dynamic programming solution of the problem
compute(n,k){
int arr[n+1][n+1]
for(int i = 0; i<= n; i++){
arr[i][0] = 1; // Initialization
arr[i][n] = 1;
}
for(int i = 0; i<= n ; i++){
for(int j = 0; j<= n; j++){
arr[i][j] = arr[i-1][j-1] + arr[i-1][j]
}
}
}
d)The time complexity of the dyanamic algorithm will be O(n^2)