Dynamic Programming

See attached pdf

Also attached are example solutions to show expected format

Problem description

The Jim Thornton Coffee House chain is planning expansion into Calgary. It has selected many
possible sites for new coffee houses. The possible sites are joined by roads that form a spanning tree.
To eliminate competition with itself, the company has determined that it should not choose two
sites that are adjacent in this tree. From its market evaluation, the company has also determined
the expected profit per year for each site. Your job is to determine what sites Jim Thornton should
choose for his coffee houses.

a. Define this problem precisely, by defining the required Input and the required Output. Use
mathematical notation.

b. Write a recursive equation for the function that maximizes the profit per year. Include a
short argument that your equation is correct.

c. Write an efficient algorithm that computes the maximum profit per year, and also computes
the sites that should be chosen. Your algorithm should run in time that is polynomial in the
input size.

d. What is the asymptotic running time of your algorithm? Defend your answer.

Your algorithm and proofs should be precise and concise (as well, of course, as correct.) Elegance
of your solution counts.

2

CPSC

4

1

3

— Winter,

2

013

Home Work Exercise #

8

March 1

6

, 2013

1. Exercise 1 Chapter 6, page 312 of the textbook.

Answer:

(a) A counterexample is given in Figure 1. The given algorithm finds an independent set of
weight 8. However, the maximum total weight is 10 by adding the nodes at two ends to
the independent set.

5

58

Figure 1: A counterexample to the algorithm of 1(a)

(b) A counterexample is given in Figure 2. The given algorithm finds an independent set of
weight 11. However, the maximum total weight is 19 by adding the nodes at two ends to
the independent set.

10 12 9

Figure 2: A counterexample to the algorithm of 1(b)

(c) Input: An array A = (a1, . . . , an) of n integers. (I use “array” rather than “set” here
because the elements in a set do not have the notion of order.)
Output: A set S = {aα1, . . . , aαm} ⊆ A, which satisfies

(1)
m∑
i=1

aαi is maximum;

(2) ∀i ∈ {1, . . . , m}, ̸ ∃j ∈ {1, . . . , m} s.t. |αi − αj| = 1.

Optimization function. Indset[i] denotes the maximum independent set of an array with
i positive integers (a1, . . . , ai). Let OPT [i] denote the total weight of Indset[i]. The
optimization function is

OPT [0] = 0, OPT [1] = max{0, a1},

OPT [i] =

{
OPT [i − 1] if OPT [i − 1] ≥ OPT [i − 2] + ai
OPT [i − 2] + ai otherwise

Correctness of the optimization function. It is trivial if n = 0 or 1. When n ≥ 2, there
are two cases to be considered. Case 1: Indset[n] includes an. Then Indset[n] must not
include an−1. And Indset[n]−{an} must be a maximum independent set of (a1, . . . , an−2).
This can be easily verified by a replacement argument. If the statement is not true, then
the total weight of Indset[n] − {an} is less than OPT [n − 2]. Then Indset[n − 2] ∪ {an

}

has total weight larger than Indset[n] does, and this contradicts the fact that Indset[n]
is a maximum independent set of (a1, . . . , an). Hence Indset[n] = Indset[n − 2] ∪ {an},
and OPT [n] = OPT [n − 2] + an. Case 2: Indset[n] does not include an, then obviously
OPT [n] = OPT [n − 1].

Algorithm 1: Maximum Independent Set

Input: Array A = (a1, . . . , an).
Output: A maximum independent set of A and its total weight.
for i = 1 to n do

OPT [i] =empty;
OPT [0] = 0;
OPT [1] = max{0, a1};
MaxIndSet(n);
return SetConstruction(n, 1); // The end, and below are the function definitions

MaxIndSet(m) { // This function returns OPT [m].
if OPT [m] is empty then

MaxIndSet(m − 1);
MaxIndSet(m − 2);
OPT [m] = max{OPT [m − 1], OPT [m − 2] + am};

return OPT [m];
}

SetConstruction(m, id) { // This function returns the Maximum Independent Set of
{a1, . . . , am}. id indicates the id’th element of Indset

if m ≤ 0 then
return Indset;

if OPT [m] == OPT [m − 2] + am then
Indset[id] = am;
return SetConstruction(m − 2, id + 1); // am ∈ Indset then am−1 /∈ Indset.

else
return SetConstruction(m − 1, id); // am /∈ Indset, recursive call for m − 1.

}

Running time analysis. The running time of the initialization is O(n), and we are going to
analyse the running time of function MaxIndSet(). Each invocation of MaxIndSet() takes
O(1) time and it either (i) returns an existing value OPT [m]; or (ii) makes two recursive
calls and fills a value OPT [m]. Here we define the progress measure Φ to be the number
of nonempty entries of OPT []. Initially Φ = 0, and at the end of the algorithm Φ ≤ n.
Case (ii) increases Φ by 1, then there are at most 2n recursive calls and MaxIndSet() is

2

Week 1 Week 2 Week 3

l 1 2 3
h 2 4 50

Table 1: A counterexample for the algorithm in 2(a)

O(n). Finally, the running time for SetConstruction() is O(n). This is because there are
1 or 2 fewer element for the input in each recursive call; there are originally n elements
for the first call, and the function does not make recursive calls when the input is an
empty set. Thus the overall running time is O(n).

2. Exercise 2, Chapter 6.

Answer:

(a) A counterexample is given in Table 1. The correct answer should choose high-stress jobs
in week 1 and 3, which accounts for a revenue of 5

7

. The algorithm achieves a revenue
of only 4 by choosing a high-stress job in week 2.

(b) Input: Two arrays of n positive numbers, L = (l1, . . . , ln) (low revenues), H = (h1, . . . , hn)
(high revenues).
Output: An array of n integers A = (a1, . . . , an), where ai ∈ {0, 1, 2}, 1 ≤ i ≤ n, which
satisfies (ai = 0, 1 or 2 specifies none, a low-stress job, or a high-stress job is chosen in
week i, respectively.)
(1) if ai = 2, then i = 1 or ai−1 = 0;
(2)

∑
1≤i≤n

(Il(ai)li + Ih(ai)hi) is maximum, where the two indicator functions Il, Ih are

defined as

Il(ai) =

{
1 if ai = 1
0 otherwise

Ih(ai) =

{
1 if ai = 2
0 otherwise

Optimization functions. Let A[i] denote a job plan for weeks 1, 2, . . . , i that achieves the
maximum total revenue, and let OPT [i] denote the total revenue of A[i].

OPT [0] = 0, OPT [1] = max{l1, h1}

OPT [i] = max




OPT [i − 1]
li + OPT [i − 1]
hi + OPT [i − 2]

Notice that li + OPT [i − 1] > OPT[i − 1], then the expression can be simplified to

OPT [i] = max

{
li + OPT [i − 1]
hi + OPT [i − 2]

Correctness of the optimization function. When n = 0 or 1, the expressions for OPT [n]
are trivially correct. Suppose the functions are correct for 0 ≤ n < i, i ≥ 0, we are going to prove that it is still correct when n = i. There are three cases to be considered for OPT [i].

3

Case 0: “none” is chosen in week i, then OPT [i] = OPT [i−1] since there is no income for
week i. Case 1: a low-stress job is chosen in week i, then OPT [i] = OPT [i − 1] + li. Case
2: a high-stress job is chosen in week i, which implies that only “none” can be chosen in
week i − 1. Then OPT [i] = OPT [i − 2] + hi.

Algorithm 2: Job Plan

Input: Two arrays L = (l1, . . . , ln), H = (h1, . . . , hn).
for i = 1 to n do

OPT [i] =empty;
OPT [0] = 0, OPT [1] = max{l1, h1}; // OPT is a global array.
plan(n);
return planConstruction(n); // The end, below are the function definitions.

plan(n) {
// It calculates OPT [n]. Please note that the input to the function, n, and
the size of the input to the algorithm are independent. In the algorithm in

Exercise 1, different notations, n and m, are used to distinguish them.
if OPT [n] is empty then

plan(n − 2);
plan(n − 1);
OPT [n] = max{OPT [n − 1] + ln, OPT [n − 2] + hn};

return OPT [n];
}

planConstruction(n) {
// This function returns the optimal job plan A.

if n ≤ 0 then
return A;

if OPT [n] == OPT [n − 1] + ln then
A[n] = 1;
return planConstruction(n − 1);

else
A[n] = 2;
A[n − 1] = 0;
return planConstruction(n − 2);

}

Running time analysis. The running time of the initialization is O(n). Each invocation of
plan(n) takes O(1) time and it either (i) returns an existing value OPT [n]; or (ii) makes
two recursive calls and fills an empty value OPT [n]. Here we define the progress measure
Φ to be the number of nonempty entries of OPT []. Initially Φ = 0, and at the end of
the algorithm Φ ≤ n. Case (ii) increases Φ by 1, which implies that there are at most 2n
recursive calls. Thus the overall running time for plan(n) is O(n). planConstruction()
immediately returns when the input size is 0 and for each recursive call the input size
decreases by at least 1. It’s running time is O(n) given that the input size for the original

4

call is n. The total running time of the algorithm is O(n).

3. Exercise 3, Chapter 6.

Answer:

(a) A counterexample is given in Figure 3. The given algorithm finds a path of length 2,
(v1, v2, v5). However, the greatest path length is 3 with (v1, v3, v4, v5) being the longest
path.

v
1

v
4

v
2

v
5

v
3

Figure 3: A counterexample to the algorithm of 3(a)

(b) Input: A directed ordered graph G = (V, E), where V = {v1, . . . , vn}, for each edge
(vi, vj) ∈ E we have i < j, and for every node vi, i = 1, . . . , n − 1, there is at least one edge of the form (vi, vj). Output: An integer L which is the number of edges in a v1 − vn path and L is maximum.

Optimization function. Let P [i] denote the a longest vi − vn path, and OPT [i] is the
length of P [i]. Then

OPT [n] = 0

OPT [i] = 1 + max{OPT [j]|(vi, vj) ∈ E}

Correctness of the optimization function. When n = 0, then L[n] is trivially 0. Suppose
the function is correct for i+1 ≤ n ≤ n, 0 ≤ i ≤ n−1, we are going to prove that it is still
correct when n = i. Suppose there are t edges, Ei = {(vi, vj1), . . . , (vi, vjt)}, going out
from vi. We know from the definition of ordered graph that t ≥ 1 and jp > i, p = 1, . . . , t.
Any vi − vn path has to contain one and only one edge in Ei. If a longest vi − vn path
P contains (vi, vjp), 1 ≤ p ≤ t, then P − {(vi, vjp)} is a longest vjp − vn path, hence
OPT [i] = 1 + OPT [jp]. Thus the optimization function is true when n = i.

The answers to Exercises 1 and 2 are recursive algorithms, and the algorithm given here
rewinds the recursion, i.e. Algorithm 3 is an iterative algorithm.

Running time analysis. The running time of the initialization is O(n). In the main loop,
the running time is ∑

1≤i≤n−1

∑
i+1≤j≤n

1 =
∑

1≤i≤n−1
n − i

= n(n − 1)/2
< n2

Hence the running time of the algorithm is O(n2).

5

Algorithm 3: Maximum Path (Iterative)

Input: A directed ordered graph G = (V, E).
Output: The length of the longest v1 − vn path.
for i = 1 to n do

OPT [i] = 0;
for i = n − 1 down to 1 do

for j = i + 1 to n do
if (vi, vj) ∈ E and OPT [i] < 1 + OPT [j] then

OPT [i] = 1 + OPT [j];

return OPT [1];

4. Exercise 6, Chapter 6.

Answer: Input: An array of positive integers (c1, . . . , cn), a positive integer L.
Output: An array of integer (a1, . . . , am), which satisfies
(1) am = n;
(2) aj > ai if j > i;

(3) Li = [
ai−1∑

j=ai−1+1
(cj + 1)] + cai ≤ L, i = 1, . . . , m (a0 is defined to be 0);

(4)
m∑
i=1

(L − Li)2 is minimum.

Note that the output indicates a printing scheme where words wai−1+1, . . . , wai are printed in
one line, 1 ≤ i ≤ m.

Optimization function. A printing of words is called a pretty printing if the printing achieves
the minimum sum of the squares of the slacks of all lines. Let P [i] be a pretty printing
scheme for words wi, . . . , wn, and the sum of squares of the slacks of all lines in printing P [i]
is denoted as OPT [i]. Let E[i] be the maximum index such that words wi, wi+1, . . . , wE[i]
can be printed in a line without exceeding the maximum line length L. Then

OPT [n] = (L − cn)2

OPT [i] = min{(L − (
j−1∑
k=i

(ck + 1) + cj))
2 + OPT [j + 1]|j = i, i + 1, . . . , E[i]}

Correctness of the optimization function. When k = n, then OPT [k] = (L − cn)2 is trivially
correct. Suppose the optimization function is correct for i < k ≤ n where 1 ≤ i ≤ n − 1, we are going to prove that it is still correct when k = i. When printing words wi, wi+1, . . . , wn, we can have wi, wi+1, wj where i ≤ j ≤ E[i] printed in the first line. If it is a pretty printing, apart from the words wi, wi+1, wj printed in the first line, the printing for the remaining words wj+1, wj+2, . . . , wn must be a pretty printing, and by induction this pretty printing achieves

a minimum sum of squares of slacks, OPT [j + 1]. Hence OPT [i] = (L − (
j−1∑
p=i

(cp + 1) + cj))
2 +

OPT [j + 1].

6

Algorithm 4: E-Calculation

Input: An array (c1, . . . , cn) and an integer L.
// Calculate E[].
sum[0] = 0;
for i = 1 to n do

sum[i] = sum[i − 1] + ci;
E[0] = 1;
for i = 1 to n do

for j = E[i − 1] to n do
if sum[j] − sum[i − 1] + (j − i) > L then

E[i] = j − 1;
break;

if j == n then
E[i] = n;

return E;

Algorithm 5: Pretty Printing (Iterative)

Input: An array C = (c1, . . . , cn) and an integer L.
Output: An array representing a pretty printing scheme.
E =E-Calculation(C, L);
OPT [n] = (L − cn)2, OPT [n + 1] = 0;
prn[n] = n;
// In a pretty printing for wi, . . . , wn where wi, . . . , wj are printed in one line,
then the definition of prn[i] is prn[i] = j.
for i = n − 1 down to 1 do

temp = ci;
OPT [i] = (L − temp)2 + OPT [i + 1];
prn[i] = i;
for j = i + 1 to E[i] do

temp = temp + 1 + cj; // temp =
∑

i≤k≤j−1
(ck + 1) + cj.

if OPT [i] > (L − temp)2 + OPT [j + 1] then
/* Each time we update OPT [i] to be a smaller value, when we go
through i, i + 1, . . . , E[i] we achieve minimum value for OPT [i]. */
OPT [i] = (L − temp)2 + OPT [j + 1];
prn[i] = j;

// Below calculates the pretty printing scheme a[].
cur = 1, id = 1;
while cur < n do

a[id] = prn[cur];
cur = prn[cur] + 1, id = id + 1;

return a;

7

Running time analysis. Algorithm 5 calls function E-Calculation to calculate E. There is a
nested loop in E-Calculation. During the execution, suppose we break out of the inner loop
when j = k for some k ∈ [1, n], then for the next time we enter the inner loop, we start with
j = k −1 (if k < n) or j = k (if k equals n); so in the global view, j goes from E[0](= 1) to n, which is O(n), but take a step back (of size 1 or 2) each time entering the inner loop. Notice that we enter the inner loop for n times in total, so the total “stepback” taken is O(n). Thus the running time of E-Calculation is O(n). The nested for loop in Algorithm 5 is also O(n2). The while loop in the algorithm is O(n) since prn[cur] ≥ cur then cur increases by at least 1 in each iteration and then there will be no more than n iterations. To sum up, the total running time of the algorithm is O(n2).

8