COMP3121代写、代写Java，Python编程

日期：2021-11-08 11:55

Assignment 4

COMP3121/9101 21T3

Released November 3, due November 17

In this assignment we apply maximum flow. There are five problems, for a total of 100

marks.

Your solutions must be typed, machine readable PDF files. All submissions will be

checked for plagiarism!

For each question requiring you to design an algorithm, you must justify the correct-

ness of your algorithm. If a time bound is specified in the question, you also must argue

that your algorithm meets this time bound.

Partial credit will be awarded for progress towards a solution.

1. (20 points) A school is doing a fire drill. The school consists of n rooms and m

corridors, where each corridor connects two rooms. There are x students who must

be moved from room 1 (their classroom, with teacher A) to room n (a safe room,

where teacher B is waiting).

The teachers decided to divide the class of x students into several waves. Each wave

will be released from room 1 by teacher A, and make their way through the corridors.

To prevent overcrowding, each corridor has a limit li, which is the maximum number

of students in a single wave who can use this corridor. Once all students in this wave

have reached room n, teacher B will call teacher A and instruct them to send the

next wave.

Design a polynomial time algorithm which determines the minimum number of waves

that must be formed and the number of students in the largest wave.

2. (20 points) There are some stones in a rectangular grid with r rows and c columns.

The stone in row i and column j has height hij and holds aij lizards. Both hij and

aij are non-negative integers. If hij is zero, this denotes that there is no stone at (i, j)

and hence aij is guaranteed to also be zero.

Each lizard can jump between two stones if they are separated a distance of at most

d, i.e. it can jump from a stone at (i1, j1) to an unoccupied stone at (i2, j2) if√

(i1 ? i2)2 + (j1 ? j2)2 ≤ d.

However, the stones are not stable, so whenever a lizard leaves a stone, the height

of the stone is decreased by 1. If the new height of the stone is zero, the stone has

disappeared below the surface. Any remaining lizards on this stone will drown, and

lizards will no longer be able to jump onto this stone.

1

We want to help as many lizards as possible to escape the grid. A lizard escapes if a

jump of distance k takes them beyond the boundary of the grid.

Design a polynomial time algorithm to find the maximum number of lizards that can

escape from the grid.

3. (20 points) You are the head of n spies, who are all wandering in a city. On one day

you received a secret message that the bad guys in this city are going to arrest all your

spies, so you’ll have to arrange for your spies to run away and hide in strongholds.

You have T minutes before the bad guys arrive. Your n spies are currently located

at

(x1, y1), (x2, y2), . . . , (xn, yn),

and your m strongholds are located at

(a1, b1), (a2, b2), . . . , (am, bm).

The ith spy can move vi units per minute, and each stronghold can hold only one

spy.

Design a polynomial time algorithm which determines which spies should be sent to

which strongholds so that you have the maximum number of spies hiding from the

bad guys.

4. (20 points) Alice is the manager of a cafe′ which supplies n different kinds of drink

and m different kinds of dessert.

One day the materials are in short supply, so she can only make ai cups of each drink

type i and bj servings of each dessert type j.

On this day, k customers come to the cafe′ and the ith of them wants to order one

cup of their favourite drink ci and one serving of their favourite dessert di. If Alice

refuses to serve them, or if either their favourite drink or their favourite dessert is

unavailable, the customer will instead leave the cafe′ and provide a poor rating.

Alice wants to save the restaurant’s rating. From her extensive experience with these

k customers, she has listed out the favourite drink and dessert of each customer, and

she wants your help to decide which customers’ orders should be fulfilled.

Design a polynomial time algorithm which determines the smallest possible number

of poor ratings that Alice can receive.

5. (20 points) You will be in charge of a delivery network consisting of n warehouses for

d days. During this time, your job is to redistribute items between these warehouses

– specifically, the ith warehouse starts with Ai items and must have at least Bi items

by the end of the dth day. All items are identical, so this requirement can be fulfilled

using items from any warehouse.

You are also given a schedule of m deliveries between warehouses that you can use

to redistribute items. The kth delivery leaves warehouse wk on the evening of day tk,

carrying at most ck items, and drops them all off at warehouse w

′

k on the morning of

day t′k. You can also keep an unlimited number of items at each warehouse overnight.

Design a polynomial time algorithm which determines whether it is possible to have

at least Bi items present at each warehouse i at the end of the dth day.