Description

COMP3121/9101 21T3
In this assignment we apply maximum flow. There are five problems, for a total of 100 marks.
For each question requiring you to design an algorithm, you must justify the correctness 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.
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.
p(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 d 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 caf´e 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 caf´e and the ith of them has pi favourite drinks
(ci,1,ci,2 …,ci,pi) and qi favourite desserts (di,1,di,2,…,di,qi). Each customer wants to order one cup of any one of their favourite drinks and one serving of any one of their favourite desserts. If Alice refuses to serve them, or if all their favourite drinks or all their favourite desserts are unavailable, the customer will instead leave the caf´e 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 drinks and desserts 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.
A solution for the case where all pi and all qi are 1 (i.e. all customers have only one favourite drink and one favourite dessert) will earn up to 10 points.
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 (m ≥ d) between warehouses that you can use to redistribute items. The kth delivery leaves warehouse wk on the evening
Page 2
of day tk, carrying at most ck items, and drops them all off at warehouse wk′ on the morning of day . 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.
Page 3