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
(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
(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.
Program Analysis
2. Consider the SubsetSum algorithm given below. SubsetSum(n, W ):
let B(0,w) ← 0 for each w ∈ {0,…,W } for i ← 1 to n
for w ← 0 to W ifw
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
(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.