Stirling numbers of the first kind , denoted as s ( n , k ), represent (among ot

Question

Stirling numbers of the first kind, denoted as s(n, k), represent (among other things) the coefficient of xk in the expansion of x(x - 1)(x - 2) · · · (x - n + 1).

For example, when n = 2, this expression is x(x - 1) = x2 - x, which has a coefficient of 1 for x2 and -1 for x1, so s(2, 2) = 1 and s(2, 1) = -1.

As another example, when n = 3, this expression is x(x - 1)(x - 2) = x3 - 3x + 2x, so s(3, 3) = 1, s(3, 2) = -3, and s(3, 1) = 2.

It can be shown that Stirling numbers of the first kind obey the following identity:

Answer the following questions about Stirling numbers of the first kind.

1. Give pseudocode for an iterative dynamic programming solution to this problem.
2. Can the space complexity of the iterative algorithm be reduced relative to the memoized algorithm? Why or why not?

Explanation / Answer

1.

int s_recursive(int n,int k) {
if (k == n)
return 1;
else if(k==0)
return ;
else
return s_recursive(n-1,k-1) - (n-1)*s_recursive(n-1,k);
}

------------------------------------------------------------------------------------------------------------------------------------------

2.

int s_dynamic(int n,int k) {
int maxj = n-k;

int *arr = new int[maxj+1];

for (int i = 0; i <= maxj; ++i)
arr[i] = 1;

for (int i = 2; i <= k; ++i)
for(int j = 1; j <= maxj; ++j)
arr[j] -= i*arr[j-1];

return arr[maxj];
}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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