Lot 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 (VE) 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 differ by exactly 1. With each node vi, we associate a positive integer weight wi. Consider, for example, the five-node path drawn in Figure 1. 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 a 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 algoritha Start with S equal to the eapty set While some node remains in G Pick a mode of maximum weight Add to s Delete and its neighbors from G Endwhile Returns (b) Give an example to show that the following algorithm also does not always find an independent set of maximum total weight. Let S, be the set of all where i is an odd number Let Sy be the set of all where i is an even number (Note that Sand Sy are both independent sets) Determine which of Sor S2 has greater total weight, and return this one (c) Give an algorithm that takes an n-node path G with weights and returns an independent set of maximum total weight. The running time should be polynomial in n, independent of the values of the weights. Figure 1: A paths with weights on the nodes. The maximum weight of an independent set is 14 (c) Create a recurrence for part (c) of problem 6.1. For now, only worry about returning the weight of the independent set of maximum total weight. Do not forget about the base cases. (e) Repeat the previous part, except using the top-down approach with memoization. This means you need a helper function and an array for storing the memoized values. You must use zero-based indexing. (1) Repeat the previous part, except using the bottom-up approach. You must use zero-based indexing. You should ideally define one function with signature FindMaxWeight(n,W) (g) Modify your bottom-up implementation from the previous part so that it retrieves the nodes that make up the independent set of maximum total weight. You should ideally define a function with signature Find MaxWeightSolution (n.) that returns both an array of the solutions to the subproblems and an array representing which "choice" is best to take in each subproblem. Additionally, define another function PrintMaxWeightSolution(n,W) that calls Find MaxWeightSolutionin, W) and uses the second array returned by that function (the one representing the choices) to print out the (one-based) indices of the vertices that make up the optimal solution. Make sure you understand how we reconstruct the solution in the coin changing or rod cutting problems before attempting this one
