Homework 12, part 2

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

## Reviews

There are no reviews yet.