A natural attempt of a greedy algorithm for this problem is to take the vertex with the largest weight, then delete that vertex’s neighbors (because they cannot also be in an independent set). Repeat this process until there are no more vertices which can be included. Give a counterexample which shows that this algorithm may not give an optimal solution.(b) Let a[i] denote the weight of a maximum-weight independent set when only considering the first i vertices of the path. Give the values a[1], a[2], a[3], and a[4] for the example given above.(c) Define a recursive definition of a[i]. Don’t forget the base case.(d) Give a bottom-up dynamic programming algorithm based off your recursive definition. What is the running time of your algorithm?