COMP3121/9101 Term 2, 2021 Assignment 4
Due date Friday, August 6, 2021 at 8 PM sharp.
You have four problems, marked out of a total of 100 marks.
NOTE: Your solutions must be typed, machine readable .pdf files. All submis- sions will be checked for plagiarism.
1. 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? (25 pts)
2. You have n warehouses and n shops. At each warehouse, a truck is loaded with enough goods to supply one shop. There are m roads, each going from a warehouse to a shop, and driving along the ith road takes di hours, where di is an integer. Design a polynomial time algorithm to send the trucks to the shops, minimising the time until all shops are supplied. (25 pts)
Hint: Combine a binary search with a max flow. By sorting you can assume that di form an increasing sequence. Fix i and consider only roads which take ≤ di hours to travel from a warehouse to the corresponding shop and use max flow to see if they are enough to obtain a matching of warehouses with shops which is of size n. Use a binary search on i to find the smallest di which meets the requirements.
3. A large group of children has assembled to play a modified version of hop- scotch. The squares appear in a line, numbered from 0 to n, and a child is successful if they start at square 0 and make a sequence of jumps to reach square n. However, each child can only jump at most k < n squares at a time, i.e., from square i they can reach squares i + 1,i + 2,...,i + k but not i + k + 1, and a child cannot clear the entire game in one jump. An additional rule of the game specifies an array A[1, . . . , n − 1], where A[i] is the maximum number of children who can jump on square i. Assuming the
CS Help, Email: tutorcs@163.com
children co-operate, what is the largest number of children who can success- fully complete the game?(25 pts)
Hint: Connect every square i with squares i + 1, . . . , i + k with a directed edge of infinite capacity. Now limit the capacity of each square appropriately and use max flow.
4. Use max flow algorithm to solve the following problem. You are given a usual n × n chess board with k white bishops on the board at the given cells (ai,bi), (1 ≤ ai,bi ≤ n, 1 ≤ i ≤ k). 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 any of the k bishops (recall that bishops go diagonally).(25 pts)
Programming Help