Algorithms and Partitioning Homework (50 points)

1. The ministry of health has charged you with the task of selecting K cities in the country to stock the vaccine for a potential flu pandemic. Each of these K cities is called a "center", and you are planning for a rapid response in case of an outbreak in any city (it is more likely to see an outbreak in a few cities and towns that are close, but not simultaneous outbreaks all over the country). The minimum distance from any city v to its closest center is denoted as L(v) .You have to select the set of K centers so that the maximum L(v) among all cities is minimized.
   1. For K=1, write the pseudo-code of your algorithm that solves this problem optimally. Explain your algorithm in plain Farsi in a few sentences.
   2. What is the time complexity of your algorithm for K=1?
   3. For small values of K (e.g., K=3), how would you modify your algorithm?
   4. What is the time complexity of your algorithm in part c as a function of graph size and K?
   5. What would change if we use larger values of K (e.g., K = V/10, where V is the number of cities)? How would you modify your algorithm? I am not asking for a detailed solution: just sketches of your approach would do.
2. Consider the graph in the figure and its initial partition
   1. Write the gain values (D) of X, Y, Z and T .
   2. What is the gain of exchanging Z and T?
   3. Assume that in Mohsen's partitioning algorithm, Z and T are to be exchanged. What is the D of X and Y after the exchange?
3. In an undirected connected graph G(V,E), we want to find all "bridge" edges. An edge is a bridge if by removing it, the graph is divided into two components. Write an algorithm that finds all bridge edges. What is the time complexity of your algorithm?
   (a graph is connected if there is at least one path between any pair of nodes. A component in a graph is a maximal connected subgraph.)