Description
Dynamic Programming
Do NOT write pseudocode when describing your dynamic programs. Rather give the Bellman Equation,
describe the matrix, its axis and how to derive the desired solution from it.
1. Kleinberg, Jon. Algorithm Design (p. 327, q. 16).
In a hierarchical organization, each person (except the ranking officer) reports to a unique superior
officer. The reporting hierarchy can be described by a tree T, rooted at the ranking officer, in which
each other node v has a parent node u equal to his or her superior officer. Conversely, we will call v a
direct subordinate of u.
Consider the following method of spreading news through the organization.
• The ranking officer first calls each of her direct subordinates, one at a time.
• As soon as each subordinate gets the phone call, he or she must notify each of his or her direct
subordinates, one at a time.
• The process continues this way until everyone has been notified.
Note that each person in this process can only call direct subordinates on the phone.
We can picture this process as being divided into rounds. In one round, each person who has already
heard the news can call one of his or her direct subordinates on the phone. The number of rounds it takes
for everyone to be notified depends on the sequence in which each person calls their direct subordinates.
Figure 1: A hierarchy with four people. The fastest broadcast scheme is for A to call
B in the first round. In the second round, A calls D and B calls C. If A were to call
D first, then C could not learn the news until the third round.
The questions are on the next page.
CS 577 Assignment 8 – Dynamic Programming 2
Give an efficient algorithm that determines the minimum number of rounds needed for everyone to
be notified, and outputs a sequence of phone calls that achieves this minimum number of rounds by
answering the following:
(a) Give a recursive algorithm. (The algorithm does not need to be efficient)
Solution:
(b) Give an efficient dynamic programming algorithm.
Solution:
(c) Prove that the algorithm in part (b) is correct.
Solution:
Page 2 of 6
CS 577 Assignment 8 – Dynamic Programming 2
2. Consider the following problem: you are provided with a two dimensional matrix M (dimensions, say,
m × n). Each entry of the matrix is either a 1 or a 0. You are tasked with finding the total number
of square sub-matrices of M with all 1s. Give an O(mn) algorithm to arrive at this total count by
answering the following:
(a) Give a recursive algorithm. (The algorithm does not need to be efficient)
Solution:
(b) Give an efficient dynamic programming algorithm.
Solution:
(c) Prove that the algorithm in part (b) is correct.
Solution:
(d) Furthermore, how would you count the total number of square sub-matrices of M with all 0s?
Solution:
Page 3 of 6
CS 577 Assignment 8 – Dynamic Programming 2
3. Kleinberg, Jon. Algorithm Design (p. 329, q. 19).
String x
′
is a repetition of x if it is a prefix of x
k
(k copies of x concatenated together) for some integer
k. So x
′ = 10110110110 is a repetition of x = 101. We say that a string s is an interleaving of x and y if
its symbols can be partitioned into two (not necessarily contiguous) subsequences x
′ and y
′
, so that x
′
is a repetition of x and y
′
is a repetition of y. For example, if x = 101 and y = 00, then s = 100010010
is an interleaving of x and y, since characters 1, 2, 5, 8, 9 form 10110a repetition of xand the remaining
characters 3, 4, 6, 7 form 0000a repetition of y.
Give an efficient algorithm that takes strings s, x, and y and decides if s is an interleaving of x and y
by answering the following:
(a) Give a recursive algorithm. (The algorithm does not need to be efficient)
Solution:
(b) Give an efficient dynamic programming algorithm.
Solution:
(c) Prove that the algorithm in part (b) is correct.
Solution:
Page 4 of 6
CS 577 Assignment 8 – Dynamic Programming 2
4. Kleinberg, Jon. Algorithm Design (p. 330, q. 22).
To assess how well-connected two nodes in a directed graph are, one can not only look at the length of
the shortest path between them, but can also count the number of shortest paths.
This turns out to be a problem that can be solved efficiently, subject to some restrictions on the edge
costs. Suppose we are given a directed graph G = (V, E), with costs on the edges; the costs may be
positive or negative, but every cycle in the graph has strictly positive cost. We are also given two nodes
v, w ∈ V .
Give an efficient algorithm that computes the number of shortest v − w paths in G. (The algorithm
should not list all the paths; just the number suffices.)
Solution:
Page 5 of 6
CS 577 Assignment 8 – Dynamic Programming 2
5. The following is an instance of the Knapsack Problem. Before implementing the algorithm, run through
the algorithm by hand on this instance. To answer this question, generate the table, indicate the
maximum value, and recreate the subset of items.
item weight value
1 4 5
2 3 3
3 1 12
4 2 4
Capacity: 6
Solution:
6. Implement the algorithm for the Knapsack Problem in either C, C++, C#, Java, or Python. Be efficient
and implement it in O(nW) time, where n is the number of items and W is the capacity.
The input will start with an positive integer, giving the number of instances that follow. For each
instance, there will two positive integers, representing the number of items and the capacity, followed
by a list describing the items. For each item, there will be two nonnegative integers, representing the
weight and value, respectively.
A sample input is the following:
2
1 3
4 100
3 4
1 2
3 3
2 4
The sample input has two instances. The first instance has one item and a capacity of 3. The item has
weight 4 and value 100. The second instance has three items and a capacity of 4.
For each instance, your program should output the maximum possible value. The correct output to the
sample input would be:
0
6