本次代写主要为算法相关的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 modied 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 species 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 innite 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)