Problem 3: Apply [20 points] Increasingly, in remote rural areas of the world, it is becoming beneficial to create "mini-grids" to provide local electrical access rather than relying on expensive connections to a national grid 1. In this problem, we'l explore the use of graph algorithms to optimize the deployment of a minigrid in a village. Consider a village that has n homes that need access to the minigrid. Locations have already been determined for the installation of k solar generation stations, spread around the village. It is possible to connect each home to one or more generation stations, but not every home can be connected to every station (e.g., because of distance or other physical obstructions). For simplicity, assume that the cost of connecting a home to a generation station, if it is possible, is exactly proportional to the distance between the two. We will create a graph in which both homes and generation stations are vertices (i.e., the total number of vertices is n+k ). An edge exists between a home and a generation station if they can be connected; such an edge has a weight equivalent to the distance between the two. (Note: the graph is bipartite - there are no edges between generation stations and there are no edges between houses.) (a) Give an efficient algorithm to find the minimum cost to install a minigrid in the village such that every home is connected exactly one generation station. Your algorithm must be efficient, but you do not have to spend time searching for an algorithm that is asymptotically optimal. However the solution (i.e., the total cost of all the wire you need to run to connect all of the homes to stations) must be optimal. (c) Suppose there is ultimately only the ability to install k1 stations in the village. These stations must be installed at the k predetermined locations considered above, but, in the end, one location will be without a station. Assuming the same home-to-station connectivity constraints as above, give an efficient algorithm that determines whether k1 stations are sufficient to connect all of the homes to electricity and, if it is possible, outputs the optimal connectivity graph (i.e., the graph that connects all homes to stations with the least amount of wire). Again, your algorithm does not have to be asymptotically optimal, but it must be efficient and it must result in the optimal connectivity graph. (d) Give the runtime of your algorithm and briefly justify it