Let G = (V, E) be an undirected graph with n nodes. Recall that 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, a five node path. The weights are the numbers drawn inside the 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 neighbors from G Endwhile 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 SI and 4 are both independent sets) Determine which of S1 or S2 has greater total weight, and return this one