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

Question

Stirling numbers of the first kind, denoted as s(n, k), represent (among other things) the coefficient of x^k in the expansion of a (x - 1)(x - 2) ... (x - n + 1). For example, when n = 2, this expression is x(x - 1) = x^2 - x, which has a coefficient of 1 for x^2 and - 1 for x^1, , so s(2, 2) = 1 and s(2, 1) -1. As another example, when n = 3, this expression is x(x - 1) (x - 2) = x^3 - 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: s(n, k) = {1, if k = n 0, if k = 0 s(n - 1, k - 1) - (n - 1) s (n - 1, k), otherwise Answer the following questions about Stirling numbers of the first kind. Give pseudocode for a naive recursive algorithm that computes s(n, k) using the given recurrence. Give pseudocode for a memoized dynamic programming algorithm that computes s(n, k) using the given recurrence.

Explanation / Answer

1. Pseudocode for naive recursive algorithm

Algo:

create a function strilingNum with two arguments n and k

then check base conditions that if(k==n) return 1;

if(k==0) return 0;

and now call the recursion with other condition

return strilingNum(n-1,k-1)-(n-1)*strilingNum(n-1,k);

program:

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

cin>>n;

cin>>k;
int r=strilingNum(n,k);
cout<<r;
return 0;
}

2. pseudocode for a memoized dynamic programing Algorithm

Algo:

create a function strilingNum with two arguments n and k

then in that function create an 2-D array of with n row and k column

int strilingNumber[n+1][k+1];

then fill the first row and first column with 0 and diagonal cells with 1

for(int i=0;i<=k;i++)
strilingNumber[0][i] = 0; ///// k=0
for(int i=0;i<=n;i++)
strilingNumber[i][0]=0;
for(int i=0;i<=n;i++)
strilingNumber[i][i]=1; //// for k=n

after this fill all the cells according to function s(n,k)=s(n-1,k-1)-(n-1)*s(n-1,k) /////otherwise

for (int i=1; i<=n; i++)
{

   // Fill for remaining values of j
   for (int j=1; j<=k; j++)
       strilingNumber[i][j] = strilingNumber[i-1][j-1] -(i-1)*strilingNumber[i-1][j];
}

then print out the last cell of array strilingNumber[n][k]

cout<<strilingNumber[n][k];

Program:

#include<iostream>
using namespace std;

void strilingNum(int n,int k)
{
int strilingNumber[n+1][k+1];
for(int i=0;i<=k;i++)
strilingNumber[0][i] = 0;
for(int i=0;i<=n;i++)
strilingNumber[i][0]=0;
for(int i=0;i<=n;i++)
strilingNumber[i][i]=1;
for (int i=1; i<=n; i++)
{
   // Fill for remaining values of j
   for (int j=1; j<=k; j++)
       strilingNumber[i][j] = strilingNumber[i-1][j-1] -(i-1)*strilingNumber[i-1][j];
}
cout<< strilingNumber[n][k];
}

int main()
{
cin>>n;
cin>>k;
strilingNum(n,k);

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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