Description
Stirling Numbers of the Second Kind, represented as S(n, k), count (among
other things) the number of ways to divide n objects into exactly k nonempty
piles. For example, there are 7 ways to divide four objects into two piles:
{1, 2, 3} {4}
{1, 2, 4} {3}
{1, 3, 4} {2}
{2, 3, 4} {1}
{1, 2} {3, 4}
{1, 3} {2, 4}
{1, 4} {2, 3}
Stirling Numbers of the Second Kind can be calculated using the following
recurrence relation:
S(n, k) = (
1, if k = 1 or k = n
kS(n − 1, k) + S(n − 1, k − 1), otherwise
In Homework 12, you developed a memoized dynamic programming algorithm to compute S(n, k) efficiently. In this assignment, you will transform
your memoized algorithm into an iterative algorithm.
1. Draw a representation of the data structure used to compute S(6, 3). You
do not need to fill in the values. Decorate this diagram as follows:
(a) Mark the data structure element(s) representing base cases of the
recurrence with a capital ‘B’.
(b) Mark the data structure element representing S(5, 3) with a star (?).
(c) Mark the data structure element(s) representing the subproblems
that S(5, 3) depends on directly with a capital ‘D’.
(d) Mark all other data structure elements representing subproblems that
S(5, 3) depends on with a capital ‘I’. Do not “overwrite” any previous
marks.
2. Describe, either in English or using one or more loops, an order for evaluating the elements of this data structure so that
1
(a) The first elements encountered are base cases (‘B’)
(b) The dependent data elements (‘D’) always precede the element that
depends on them (?), for every element. Note that this implies that
every indirect dependency (‘I’) will precede every direct dependency
(‘D’).
3. Describe an iterative dynamic programming algorithm that computes S(n, k).
You do not need to reduce the space complexity of this algorithm relative
to the memoized algorithm, though you may, if you want.
2