2023年11月25日

算法设计代写 | COMP3121/9101 Assignment 4

本次英国cs代写为算法设计的assignment

1. There are N computers in a network, labelled f1; 2; 3; : : : ;Ng. 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 ow. 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 ow 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 nd the smallest
di which meets the requirements.

3. A large group of children has assembled to play a modi ed 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 speci es an array A[1; : : : ; n 1], where A[i] is
the maximum number of children who can jump on square i. Assuming the
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 in nite capacity. Now limit the capacity of each square appropriately and
use max ow.

4. Use max ow 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)