Problem 1. (40 pts) For each of the following problems, describe a / the greedy-approach for a solution If the greedy approach works and is guaranteed to always find an optimal solution - prove it; otherwise., give a counter example where the greedy approach fails to find an optimal solution. (a) (10 pts) The EQUAL-WEIGHT INTEGRAL KNAPSACK problem: Your input is a capacity W and a set of n non-breakable items (you either take them or leave them, no fractional takes) with values vi and weight wi, and your goal is to find a maximal set of items whose total weight is at most 1). Le., they have coins of 1c, Cc, C2. c3e, Ck up to some k. (Think of C 10 and a subset of our bills and coins.) You are a teller and you have to return to the costumer a total of r using the smallest number of coins. Your input is x, and your output is a sequence yo,Y1, , yk such that (i) r = 1ViCi and (ii) you minimize the number of coins used: yi (c) (10 pts) The MAXIMAL WEIGHTED MATCHING problem: You are given an undirected bipartite graph, where the vertex-set is partitioned into R and L and every edge connects a node in R with a node in L and where the edges have weights w : E R. A matching M in this graph is a subset of the edges of the graph which are vertex-disjoint; namely, for every node u there is at most a single edge in M that is adjacent to it. Think of this problem as a Kidney Transfer problem: on the left you have the kidney donors, on the right you have the kidney patients (who need a transplant), and each edge represents that chances that the transplant from this donor to this patient will succeed. Since each donor can give at most one kidney and each patient will receive at most one kidney, you are looking to find a matching that has the largest chances of supplying patients with functioning kidneys Your goal is to pick a maximal matching. The input is a graph G (including weights on the edges), and your output is a subset of the edges of the graph M C E such that M is a matching and you maximize the total cost of all edges in the matching: eEM (d) (10 pts) The LONGEST-PATH problem: You are given an undirected graph with weights on the edges and a pair of vertices s,t. Your goal is to find a longest simple path from s to t. (The greedy approach is a version of Dijkstra, where you pick the max-edge crossing the cut between the current set of vertices and the remaining set of vertices.)