Program Analysis Term 1, 2015 Problem Sheet 9
1. Let G = (V,E) be an undirected graph with n nodes. A subset of the nodes is called an independent set if no two of them are joined by an edge. Finding large independent sets is difficult in general; but here we’ll see that it can be done efficiently if the graph is “simple” enough.
Call a graph G = (V,E) a path if its nodes can be written as v1,v2,…,vn, with an edge between vi and vj if and only if the numbers i and j differ by exactly 1. With each node vi, we associate a positive integer weight wi.
Consider, for example, the five-node path drawn in Figure 1. The weights are the numbers drawn inside the nodes.
18636
Figure 1: Path with weights on nodes.
The goal in this question is to solve the following problem:
Find an independent set in a path G whose total weight is as large as possible.
(a) Give an example to show that the following algorithm does not always find
an independent set of maximum total weight.
The “heaviest-first” greedy algorithm
start with S equal to the empty set while some node remains in G
pick a node vi of maximum weight add vi to S
delete vi and its neighbours from G
return S Model Answer:
232
(b) Give an example to show that the following algorithm also does not always find an independent set of maximum total weight.
let S1 be the set of all vi where i is an odd number
let S2 be the set of all vi where i is an even number
(Note that S1 and S2 are both independent sets)
Determine which of S1 or S2 has greater total weight, and return it
Program Analysis Model Answer:
Term 1, 2015
2112
(c) Give a dynamic programming algorithm that takes an n-node path G with weights and returns the total weight of the independent set of maximum total weight. The running time should be polynomial in n, independent of the values of the weights.
Model Answer: Given a path G = (V,E) as defined in the question, for eachiwhere0≤i≤n,letGi =(Vi,Ei)bethesubgraphofGwhereVi = {v1,…,vi} and
Ei ={{vj,vj+1}|1≤j
len ← len+|wj|+1 j←j−1
(b) Discuss the efficiency of your algorithm.
Model Answer: The outer loop is iterated n times. The number of itera- tions of the inner loop (the while loop) is O(K), since at each iteration len increases and it cannot exceed K. Thus the total running time is O(K · n).
Program Analysis Term 1, 2015
4. You run a highly successful business that employs a select group of outstand- ing programmers. Your company specialises in extremely fast software devel- opment, only taking on projects that can be completed within one week. You only takes on jobs where the client is available to directly support with your team throughout the week, and this means that when clients submit a proposal to your company, they are required to identify a particular week during which they are able to absolutely guarantee that they are available to liaise with your programming team. Because your company is so wildly successful you are al- ways completely inundated by requests for your programmers to take on jobs, and you have the luxury of being able to be highly selective as to which jobs to take on. Each week you are responsible for allocating your programming team a single job to work on for that week, and with a view to maximising your busi- ness’ profits, you periodically go through the following process in order to decide which jobs to allocate to your team over the following n weeks.
Your first step in this planning process is to classify all of these available jobs as either “straightforward” or “challenging”. You expect “straightforward” jobs to be ones that the team can complete in a week without having to work evening or weekends, but the “challenging” jobs are expected to require significant extra weekend and evening effort in order to complete within a week.
Your second step is to select, for each of the next n weeks, precisely two jobs: the most lucrative “straightforward” job that is on offer for that week, and most lucrative “challenging” job that is on offer for that week. We will assume that there is at least one “straightforward” and one “challenging” job available for each week.
• We will refer to the most lucrative “straightforward” job for week i as si. • We will refer to the most lucrative “challenging” job for week i as ci.
• The value to the business of job si is v(si), and the value of job ci is v(ci).
The final step involves solving the problem that this question is considering. It involves choosing, for each week i (where i ranges from 1 to n), one of three possible options:
• to take on the most lucrative “straightforward” job available that week, i.e. job si, which will be worth v(si);
• to take on the most lucrative “challenging” job for that week, i.e. ci, which will be worth v(ci); or
• to take on no job at all for that week which will be worth nothing to the company.
The reason for this third option is that one of the secrets of your company’s suc- cess is that you have the following policy regarding how you assign jobs to your team. If your team takes on a “challenging” job in week i then they are not as- signed any work at all in the previous week (week i − 1). However, if they take
Program Analysis Term 1, 2015
on a “straightforward” job in week i then they can take on any kind of job in previous week (week i − 1), even one that is “challenging”. You are allowed to allocate a “challenging” job in week 1.
So the problem here is to find a plan with maximal value, where the value of a plan is the sum of the values of the task selected each week.
Example. Suppose n = 4, and the values of si and ci are given by the following table. Then the plan of maximum value would be to choose no task in week 1, c2 inweek2,s3 inweek3ands4 inweek4. Thevalueofthisplanwouldbe 0+60+20+20 = 100.
Week 1 Week 2 Week 3 Week 4
si 10 10 20 20 ci 15 60 5 5
(a) Explain why the algorithm below will not solve this problem, by showing an example where it doesn’t give the right answer.
let i = 1 while i ≤ n
ifi
allocate no task for week i’
select a “challenging” task for week i + 1’ i←i+2
else
select “straightforward” task for week i” i←i+1
Model Answer: This algorithm could take a challenging task too soon, missing an even better challenging task that is available later. Consider the following example.
Week 1 Week 2 Week 3
si 2 2 2 ci 1 5 10
The algorithm would take a challenging job in week 2. A better solution would be to choose a straightforward job in week 1, nothing in week 2 and a challenging job in week 3.
(b) Give an efficient dynamic programming algorithm that solves this problem. It takes as input values for s1,s2,…,sn and c1,c2,…,cn and returns an op- timal plan.
Program Analysis Term 1, 2015 Model Answer: Let B[i] be the value of the most lucrative plan for weeks
1 to i.
The recursive specification for this is as follows.
0
B[i] = max(s1,c1)
max(si + B[i − 1], ci + B[i − 2])
The algorithm is as follows.
if i = 0
if i = 1 otherwise
Note that in addition to table B, this algorithm completes a table C that holds information that will be used to recover the plan (see algorithm GetPlan below).
B[0] ← 0
if s1 ≥ c1 then
B[1] ← s1
C[1] ← straightforward else
B[1] ← c1
C[1] ← challenging for i ← 2 to n:
if si +B[i−1] ≥ ci +B[i−2]) then B[i]←si +B[i−1]
C[i] ← straightforward
else
B[i]←ci +B[i−2] C[i] ← challenging
The following recursive algorithm recovers the optimal plan from C. GetPlan(C, i):
if i = 0 then return ⟨ ⟩
else if i = 1 then return ⟨C[1]⟩
else
if C[i] = straightforward then
return Append (GetPlan(C, i − 1), ⟨straightforward⟩) else
return Append (GetPlan(C, i − 2), ⟨free, challenging⟩) Recovering the full plan involves making the call lGetPlan(C, n)