1. Today was just a regular day for everyone in Krypton until a news flashed that a meteor is going to destroy Krypton in X days. Krypton has N cities connected together by bidirectional roads. It takes t(i,j) days to travel from city i to city j. In each city Ci the Krypton Government built qi pods to carry inhabitants in case of any calamity, which will transport them to Earth. City Ci has population pi. As soon as the people hear this news they try to save themselves by acquiring these pods either at their own city or in other city before the meteor destroys everything. Note that a pod can carry only one person. Find the largest number of invaders the Earth will have to deal with. (20 pts)
2. You are given a usual 8 × 8 chess board with 2 white bishops on the board at the given cells (a,b) and (c,d) (of opposite colour), (1 ≤ a,b,c,d ≤ 8). You have to determine the largest number of black rooks you can place on the board so that no two rooks are in the same row or in the same column or are under the attack of either of the two bishops (recall that bishops go diagonally).(20 pts)
3. There are N computers in a network, labelled {1,2,3,...,N}. There are M one-directional links which connect pairs of computers. Computer 1 is trying to send a virus to computer N. This can happen as long as there is a path of links from computer 1 to computer N. To prevent this, you’ve decided to remove some of the links from the network so that the two computers are no longer connected. For each link, you’ve calculated the cost of removing it. What is the minimum total cost to disconnect the computers as required, and which edges should be removed to achieve this minimum cost? (20 pts)
1
