6 Zombie breakout (from the Exam 2014) A zombie breakout has occurred in the country 1D...

Transcribed Image Text:

6 Zombie breakout (from the Exam 2014) A zombie breakout has occurred in the country 1D and you have been asked by the prime minister to help find solutions to stop the infection. You are given a map of the country, with coordinates of all cities. There are X infected cities and Y uninfected cities. The map also contains information about all roads between cities. A road goes directly to from one city to another and all roads are directed. There are R roads. A city is reachable from the capital if you can follow one or more roads from the capital to the city. You can assume that the travel time from the capital to any reachable city is no more than a day. 6.1 Save the capital The zombies only travel on the roads. The capital is still uninfected and the prime minister wants to know how many roads that must be destroyed to keep the capital uninfected. Give an algorithm to compute the minimum number of roads that has to be destroyed to cut off the capital from the infected cities. Analyze the running time of your algorithm in terms of X, Y, and R. Remember to argue that your algorithm is correct. 6.2 Distributing the vaccine Researchers in the center in the capital have found a vaccine. To get the vaccine to the people in the uninfected cities we need to send 10 doctors to each uninfected city. The doctors can only travel on the roads. They can go through infected cities but at most 50 doctors can go through each infected city per day. Give an algorithm to decide whether we can get the vaccine out to all uninfected cities in one day. Analyze the running time of your algorithm in terms of X, Y, and R. Remember to argue that your algorithm is correct. 6 Zombie breakout (from the Exam 2014) A zombie breakout has occurred in the country 1D and you have been asked by the prime minister to help find solutions to stop the infection. You are given a map of the country, with coordinates of all cities. There are X infected cities and Y uninfected cities. The map also contains information about all roads between cities. A road goes directly to from one city to another and all roads are directed. There are R roads. A city is reachable from the capital if you can follow one or more roads from the capital to the city. You can assume that the travel time from the capital to any reachable city is no more than a day. 6.1 Save the capital The zombies only travel on the roads. The capital is still uninfected and the prime minister wants to know how many roads that must be destroyed to keep the capital uninfected. Give an algorithm to compute the minimum number of roads that has to be destroyed to cut off the capital from the infected cities. Analyze the running time of your algorithm in terms of X, Y, and R. Remember to argue that your algorithm is correct. 6.2 Distributing the vaccine Researchers in the center in the capital have found a vaccine. To get the vaccine to the people in the uninfected cities we need to send 10 doctors to each uninfected city. The doctors can only travel on the roads. They can go through infected cities but at most 50 doctors can go through each infected city per day. Give an algorithm to decide whether we can get the vaccine out to all uninfected cities in one day. Analyze the running time of your algorithm in terms of X, Y, and R. Remember to argue that your algorithm is correct.

Answer rating: 100% (QA)

Answer Input The input con... View the full answer