Solving Part C, Please. I am really confused about how to work on these problems. Especially, the approach to come up with the recurrence and the dynamic programming algorithm.

LetG (V, E) be an undirected graph with n nodes. Recall that a subset of the nodes can be called an independent set if not 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 V v2, n, with an edge between vi and vi if and only if the numbers i and j differ by exactly 1. With each node vi, we associate a positive integer weight w Consider for examples, the five node path drawn below. 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 LetG (V, E) be an undirected graph with n nodes. Recall that a subset of the nodes can be called an independent set if not 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 V v2, n, with an edge between vi and vi if and only if the numbers i and j differ by exactly 1. With each node vi, we associate a positive integer weight w Consider for examples, the five node path drawn below. 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