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 (V,E) a path if its nodes can be written as ui,V2, ,Un, 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 w 1. (15 points) Assume all the weights wi are integers, and denote w--i wi-Give an algorithm that takes an n-node path G with weights and returns an independent set of maximum total weight with running time 0(n-u). 2. (15 points) Give an algorithm that takes an n-node path G with weights and returns an independent set of maximum total weight with running time polynomial in n, independent of the values of the weights. (Hint: There is an algorithm with running time O(n).)