Dynamic Programming

I have fundamentally grasped the concept of DP but i am struggling to apply this to this context

Quiz 4
Advanced Algorithm Analysis Marks 20

Q 1. (10 points) Team work. You’re managing a consulting team of expert computer hackers, and each week you
have to choose a job for them to undertake. Now, as you can well imagine, the set of possible jobs is divided into
those that are low-stress (e.g., setting up a website) and those that are high-stress (e.g., approaching deliverable
deadlines for a major client). The basic question, each week, is whether to take on a low-stress job or a high-stress
job.

If you select a low-stress job for your team in week i, then you get a revenue of li > 0 dollars; if you select a
high-stress job you get a revenue of hi > 0 dollars. The catch, however, is that in order for the team to take on a
high-stress job in week i, it’s required that they do no job (of either type) in week i − 1; they need a full week of
prep time to get ready for the crushing stress level. On the other hand, it’s okay for them to take a low stress job
in week i even if they have done a job (of either type) in week i − 1.
So, given a sequence of n weeks, a plan is specified by a choice of “low-stress,” “high-stress,” or “none” for each
of the n weeks, with the property that if “high-stress” is chosen for week i > 1, then “none” has to be chosen for
week i − 1. (It’s okay to choose a high-stress job in week 1.)
The value of the plan is determined in the natural way: for each i, you add li to the value if you choose “low-stress”
in week i, and you add hi to the value if you choose “high-stress” in week i (You add 0 if you choose “none” in
week i.)

The problem. Given sets of values l1, l2, · · · , ln and h1,h2, · · · ,hn, find a plan of maximum value. (Such a plan will
be called optimal.)

Example. Suppose n = 4, and the values of li and hi are given by the following table. Then the plan of maximum
value would be to choose “none” in week 1, a high-stress job in week 2, and low-stress jobs in weeks 3 and 4. The
value of this plan would be 0 + 50 + 10 + 10 = 70.

Week 1 Week 2 Week 3 Week 4

l 10 1 10 10
h 5 50 5 1

First try. Below is an algorithm to plan the jobs taken.

For iterations i = 1 to n
If hi+1 > li + li+1 then

Output ‘‘Choose no job in week i’’
Output ‘‘Choose a high-stress job in week i + 1’’
Continue with iteration i + 2

Else
Output ‘‘Choose a low-stress job in week i’’
Continue with iteration i + 1

End If
End For

To avoid problems with overflowing array bounds, we define hi = li = 0 when i > n.

(a) (3 points) Show that the above algorithm does not correctly solve this problem, by giving an instance on
which it does not return the correct answer.
In your example, say what the correct answer is and also what the above algorithm finds.
Now use dynamic programming. Work out an efficient algorithm that takes values for l1, l2, · · · , ln and
h1,h2, · · · ,hn and returns the value of an optimal plan.

(b) (2 points) Draw the linearized DAG (topological ordering) for the example in the problem statement.

(c) (2 points) List down the optimal substructure for the problem.

(d) (4 points) Write the recursive formulation using the substructure.

(e) (3 points) Write the enumerated pseudocode of the solution.

(f) (2 points) How many subproblems?

(g) (2 points) What is the time per subproblem?

(h) (2 points) Determine the total running time?

Page 1 of 1