algorithm design

Question-6: (Total Points: 10) Given G, a weighted chain graph of n nodes such as the ones shown below, we want to compute the maximum independent set (MIS) of G. Remember that an independent set (IS) of a graph is a subset of its nodes such that no two nodes have an edge between thern and a MIS is an IS with (maximum total weight) Design a dynamic programming algorithm to compute the MST for such n-node chain graph. E.g., the MST for each of the below graphs consists of the nodes drawn in dashed lines. Hint: This problem can be viewed as a special case of one of the problems we covered in class. 8 6 3 2 3 2 dhe opt- Max 1 2 3 3