Assignment 4
COMP3121/9101 22T1 Released April 5, due April 19
In this assignment we apply maximum flow. There are four problems, for a total of 80 points.
Your solutions must be typed, machine readable PDF files. All submissions will be checked for plagiarism!
Copyright By PowCoder代写 加微信 powcoder
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) You are making an exam of k questions, which is divided into m sections. The ith section must contain exactly pi questions, where pi = k. There are n questions available in the question bank, each of which can be used at most once in the exam. There is a further restriction: for each section i and question j, you are given a boolean ai,j which records whether question j can be placed in section i or not.
Design an algorithm which runs in time polynomial in m and n and determines whether a valid exam can be formed.
2. (20 points) You are going on holiday. There are n cities in the world. There are also m airlines, the ith of which operates flights in both directions between cities ai and bi. You live in city 1, and you would like to travel to city n and back. You don’t mind stopovers in other cities, but you don’t want to have more than one stopover in any city.
Design an algorithm which runs in time polynomial in n and m and determines whether it is possible to travel from city 1 to city n and back to city 1 without going through any other city more than once.
3. (20 points) You are manufacturing integrated circuits from a rectangular silicon board that is divided into an m by n grid of squares. Each integrated circuit re- quires two adjacent squares, either vertically or horizontally, that are cut out from this board. However, some squares in the silicon board are defective and cannot be used for integrated circuits. For each pair of coordinates (i,j), you are given a boolean di,j representing whether the square in row i and column j is defective or not.
Design an algorithm which runs in time polynomial in m and n and determines the maximum number of integrated circuits that can be cut out from this board.
4. (20 points) You are in charge of an electrical network. In this network, power is transmitted from x generators to y customers through z substations, so there are n = x + y + z facilities in total. There are also m one-way wires, the ith of which goes from facility ai to facility bi and costs ci to disconnect. You are guaranteed that all ci are integers. Note that:
there are no wires to any generator or from any customer,
there can be a wire from a generator directly to a customer, and there can be wires between substations.
Some urgent repairs are needed, so you will have to take the entire network down, that is, disconnect wires so that power cannot travel from any generator to any customer. However, you will also have to make a trip to the site of each chosen wire, and you would prefer to leave your office as little as possible.
Design an algorithm which runs in time polynomial in n and m and determines a set of wires which:
has minimum cost to disconnect, and
requires the fewest trips out of all minimum cost sets.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com