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.313 q.2).
Suppose you are managing a consulting team and each week you have to choose one of two jobs for your
team to undertake. The two jobs available to you each week are a low-stress job and a high-stress job.
For week i, if you choose the low-stress job, you get paid `i dollars and, if you choose the high-stress job,
you get paid hi dollars. The dierence with a high-stress job is that you can only schedule a high-stress
job in week i if you have no job scheduled in week i − 1.
Given a sequence of n weeks, determine the schedule of maximum pro t. The input is two sequences:
L := h`1, `2, . . . , `ni and H := hh1, h2, . . . , hni containing the (positive) value of the low and high jobs
for each week. For Week 1, assume that you are able to schedule a high-stress job.
(a) Show that the following algorithm does not correctly solve this problem.
Algorithm: JobSequence
Input : The low (L) and high (H) stress jobs.
Output: The jobs to schedule for the n weeks
for Each week i do
if hi+1 > `i + `i+1 then
Output “Week i: no job”
Output “Week i+1: high-stress job”
Continue with week i+2
else
Output “Week i: low-stress job”
Continue with week i+1
end
end
CS 577 Assignment 7 Dynamic Programming
(b) Give an e cient algorithm that takes in the sequences L and H and outputs the greatest possible
pro t.
(c) Prove that your algorithm in part (c) is correct.
Page 2 of 8
CS 577 Assignment 7 Dynamic Programming
2. Kleinberg, Jon. Algorithm Design (p.315 q.4).
Suppose you’re running a small consulting company. You have clients in New York and clients in San
Francisco. Each month you can be physically located in either New York or San Francisco, and the
overall operating costs depend on the demands of your clients in a given month.
Given a sequence of n months, determine the work schedule that minimizes the operating costs, knowing
that moving between locations from month i to month i + 1 incurs a xed moving cost of M. The input
consists of two sequences N and S consisting of the operating costs when based in New York and San
Francisco, respectively. For month 1, you can start in either city without a moving cost.
(a) Give an example of an instance where it is optimal to move at least 3 times. Explain where and
why the optimal must move.
(b) Show that the following algorithm does not correctly solve this problem.
Algorithm: WorkLocSeq
Input : The NY (N) and SF (S) operating costs.
Output: The locations to work the n months
for Each month i do
if Ni < Si then
Output “Month i: NY”
else
Output “Month i: SF”
end
end
Page 3 of 8
CS 577 Assignment 7 Dynamic Programming
(c) Give an e cient algorithm that takes in the sequences N and S and outputs the value of the optimal
solution.
(d) Prove that your algorithm in part (c) is correct.
Page 4 of 8
CS 577 Assignment 7 Dynamic Programming
3. Kleinberg, Jon. Algorithm Design (p.333, q.26).
Consider the following inventory problem. You are running a company that sells trucks and predictions
tell you the quantity of sales to expect over the next n months. Let di denote the number of sales you
expect in month i. We’ll assume that all sales happen at the beginning of the month, and trucks that
are not sold are stored until the beginning of the next month. You can store at most s trucks, and it
costs c to store a single truck for a month. You receive shipments of trucks by placing orders for them,
and there is a xed ordering fee k each time you place an order (regardless of the number of trucks you
order). You start out with no trucks. The problem is to design an algorithm that decides how to place
orders so that you satisfy all the demands {di}, and minimize the costs. In summary:
• There are two parts to the cost: (1) storage cost of c for every truck on hand; and (2) ordering fees
of k for every order placed.
• In each month, you need enough trucks to satisfy the demand di
, but the number left over after
satisfying the demand for the month should not exceed the inventory limit s.
(a) Give a recursive algorithm that takes in s, c, k, and the sequence {di}, and outputs the minimum
cost. (The algorithm does not need to be e cient.)
(b) Give an algorithm in time that is polynomial in n and s for the same problem.
Page 5 of 8
CS 577 Assignment 7 Dynamic Programming
(c) Prove that your algorithm in part (b) is correct.
Page 6 of 8
CS 577 Assignment 7 Dynamic Programming
4. Alice and Bob are playing another coin game. This time, there are three stacks of n coins: A, B, C.
Starting with Alice, each player takes turns taking a coin from the top of a stack they may choose any
nonempty stack, but they must only take the top coin in that stack. The coins have dierent values.
From bottom to top, the coins in stack A have values a1, . . . , an. Similarly, the coins in stack B have
values b1, . . . , bn, and the coins in stack C have values c1, . . . , cn. Both players try to play optimally in
order to maximize the total value of their coins.
(a) Give an algorithm that takes the sequences a1, . . . , an, b1, . . . , bn, c1, . . . , cn, and outputs the maximum total value of coins that Alice can take. The runtime should be polynomial in n.
(b) Prove the correctness of your algorithm in part (a).
Page 7 of 8
CS 577 Assignment 7 Dynamic Programming
5. Implement the optimal algorithm for Weighted Interval Scheduling (for a de nition of the problem, see
the slides on Canvas) in either C, C++, C#, Java, Python, or Rust. Be e cient and implement it in
O(n
2
) time, where n is the number of jobs. We saw this problem previously in HW3 Q2a, where we saw
that there was no optimal greedy heuristic.
The input will start with an positive integer, giving the number of instances that follow. For each
instance, there will be a positive integer, giving the number of jobs. For each job, there will be a trio of
positive integers i, j and k, where i < j, and i is the start time, j is the end time, and k is the weight.
A sample input is the following:
2
1
1 4 5
3
1 2 1
3 4 2
2 6 4
The sample input has two instances. The rst instance has one job to schedule with a start time of 1,
an end time of 4, and a weight of 5. The second instance has 3 jobs.
The objective of the problem is to determine a schedule of non-overlapping intervals with maximum
weight and to return this maximum weight. For each instance, your program should output the total
weight of the intervals scheduled on a separate line. Each output line should be terminated by exactly
one newline. The correct output to the sample input would be:
5
5
or, written with more explicit whitespace,
“5\n5\n”
Notes:
• Endpoints are exclusive, so it is okay to include a job ending at time t and a job starting at time t
in the same schedule.
• In the third set of tests, some outputs will cause over ow on 32-bit signed integers.