2. Suppose we are given a \"chain\" of n nodes as shown below. Each node i is \"

Question

2. Suppose we are given a "chain" of n nodes as shown below. Each node i is "neigh- bors" with the node to its left and the node to its right (if they exist). An inde- pendent 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 10

Explanation / Answer

(b)
Let a[i] denote the weight of a maximum weight independent set when only considering first i vertices of the path.
a[1] = 15
a[2] = 20
a[3] = 15 + 7 = 22
a[4] = 20+10 = 30

(c)
Let chain[i] represent the ith element in the given “chain” of nodes. Following is the recursive strategy for the given problem

a[0] = chain[0]
a[1] = max(a[0], chain[1])
a[2] = max(a[0]+chain[2], a[1]);
a[3] = max(a[1]+chain[3], a[2]);
.
.
a[i] = max(a[i-2]+chain[i], a[i-1]);

sum(chain, i)
1.   if i==0
2.       return chain[0]
3.   else if i==1
4.       return = max(chain[0], chain[1])
5.   else
6.       return max(sum(chain, i-2)+sum(chain, i-1))

(d) Here is a Dynamic programming approach
a[n]
for i=0 to n-1
   if i==0
       return chain[0]
   else if i==1
       a[1] = max(chain[0], chain[1])
   else
       a[i] = max(a[i-2]+chain[i], a[i-1])
return a[n-1]

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.