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 xkin 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 a naïve recursive algorithm that computes s(n, k) using the given recurrence.

2. Give pseudocode for a memoized dynamic programming algorithm that computes s(n, k) using the given recurrence.

Explanation / Answer

1. naive recursive algorithm that computes s(n, k) using the given recurrence

.------------------------------------------------------------------------------------------------------------------------------

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);
}

// code end here..

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

2.memoized dynamic programming algorithm that computes s(n, k) using the given recurrence.

---------------------------------------------------------------------------------------------------------------
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.