Problem 1-1. Restaurant Location Drunken Donuts, a new wine-and-donuts restaurant chain, wants to build restaurants on many street corners with the goal of maximizing their total profit. The street network is described as an undirected graph G = (V, E), where the potential restaurant sites are the vertices of the graph. Each vertex u has a nonnegative integer value Pu, which describes the potential profit of site u. Two restaurants cannot be built on adjacent vertices (to avoid self- competition). You are supposed to design an algorithm that outputs the chosen set U CV of sites that maximizes the total profit ueu Pu. First, for parts (a)-c), suppose that the street network G is acyclic, i.e., a tree. (a) Consider the following "greedy" restaurant-placement algorithm: Choose the highest- profit vertex up in the tree (breaking ties according to some order on vertex names) and put it into U. Remove up from further consideration, along with all of its neighbors in G. Repeat until no further vertices remain. Give a counterexample to show that this algorithm does not always give a restaurant placement with the maximum profit. (b) Give an efficient algorithm to determine a placement with maximum profit. (c) Suppose that, in the absence of good market research, DD decides that all sites are equally good, so the goal is simply to design a restaurant placement with the largest number of locations. Give a simple greedy algorithm for this case, and prove its correctness. (d) Now suppose that the graph is arbitrary, not necessarily acyclic. Give the fastest cor- rect algorithm you can for solving the