Question :

Suppose we are given a "chain" of n nodes as shown below. Each node i is "neighbors" with the node to its left and the node to its right (if they exist).

An independent set of these nodes is a subset of the nodes such that no two of the chosen nodes are neighbors. In the below example, the first and fourth vertices form an independent set, but the first, third, and fourth vertices do not (because the third and fourth are neighbors). Now suppose each node has a positive weight.

We are interested in computing an independent set such that the sum of the weights of the chosen nodes are as large as possible. In the example, the optimal solution is to choose the second and fourth vertices for a weight of 30.

(15) - (20) - (7) - (10)

(a) A natural attempt of a greedy algorithm for this problem is to take the vertex with the largest weight, then delete that vertex's neighbors (because they cannot also be in an independent set). Repeat this process until there are no more vertices which can be included. Give a counterexample which shows that this algorithm may not give an optimal solution.

(b) Let a[i] denote the weight of a maximum-weight independent set when only considering the first i vertices of the path. Give the values a[1], a[2], a[3], and a[4] for the example given above.

(c) Define a recursive definition of a[i]. Don't forget the base case.

(d) Give a bottom-up dynamic programming algorithm based off your recursive definition. What is the running time of your algorithm?