锐客网

  1. 首页 > it技术 > >

COMP3121

【COMP3121】COMP3121
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.

    推荐阅读


    上一篇：pandas数据清洗

    下一篇：尚硅谷《宋红康MySQL核心+高级》全套教程即将发布