$30.00
Description

Matrix Puzzle
You want to fill a matrix of n rows and m columns with nonnegative integers so that the sum of each row or each column corresponds to a predetermined number. Each matrix entry also has an upper bound constraint. Specifically, given nonnegative integers r_{1}; : : : ; r_{n}, c_{1}; : : : ; c_{m}, and b_{1}_{;}_{1}; : : : ; b_{n;m}, find integers a_{1}_{;}_{1}; : : : ; a_{n;m} such that:


0 6 a_{i;j} 6 b_{i;j} for all 1 6 i 6 n, 1 6 j 6 m;

r_{i} = ^{P}^{m}_{k}_{=1} a_{i;k} for all 1 6 i 6 n;



c_{j} = ^{P}^{n}_{k}_{=1} a_{k;j} for all 1 6 j 6 m.


Knight Coexistence
You want to place knights on an n n chessboard. The chessboard has n^{2} positions from (0;0) to
(n 1; n 1). A knight at position (x; y) is able to attack up to eight diﬀerent positions: (x + 2; y + 1),
(x + 2; y 1), (x + 1; y + 2), (x + 1; y 2), (x 1; y + 2), (x 1; y 2), (x 2; y + 1), and (x 2; y 1)—for each position that lies on the board, of course. Moreover, some positions are blocked so that you cannot place knights on them. Given n and a list of all blocked positions, find a way to place as many knights as possible on the chessboard so that the placed knights cannot attack each other.
One or two more problems will follow, by the end of Reading Week at the latest: : :
Dept. of Computer Science, University of Toronto, St. George Campus page 1 of 1
Assignment #3—Part II 

Worth: 7.5% (best four of the five assignments) 
Due: before 6:00pm on 
Fri. 8 March 

Required filename for MarkUs submission: a3.pdf 

(Use a single file to submit your answers for both Part I and Part II.) 
Remember to write the full name and MarkUs username of every group member (up to three) prominently on your submission.
Please read and understand the policy on Collaboration given on the Course Information Sheet. Then, to protect yourself, list on the front of your submission every source of information you used to complete this homework (other than your own lecture and tutorial notes). For example, indicate clearly the name of every student from another group with whom you had discussions, the title and sections of every textbook you consulted (including the course textbook), the source of every web document you used (including documents from the course webpage), etc.
For each question, please write up detailed answers carefully. Make sure that you use notation and terminology correctly, and that you explain and justify what you are doing. Marks will be deducted for incorrect or ambiguous use of notation and terminology, and for making incorrect, unjustified, ambiguous, or vague claims in your solutions.
3. Reducing Edge Capacities

Prove or Disprove: if N = (V ; E) is a network, f is a maximum flow in N , e_{0} 2 E is an edge
with f (e_{0}) = c(e_{0}), and N ^{0} is the same network as N except that c^{0}(e_{0}) = c(e_{0}) 1, then the maximum flow f ^{0} in N ^{0} satisfies jf ^{0}j < jf j.

Write an algorithm that takes a network N = (V ; E), maximum flow f in N , and an edge e_{0} 2 E with f (e_{0}) = c(e_{0}), and that outputs a maximum flow for network N ^{0}, where N ^{0} is the
same as N except that c^{0}(e_{0}) = c(e_{0}) 1.
Provide a brief argument that your algorithm is correct and analyze its time complexity. For full marks, your algorithm should be as eﬃcient as possible.

Write an algorithm that takes a network N = (V ; E) and that outputs a list of all edges e_{1}; : : : ; e_{k} with the property that if the capacity of any edge in that list is reduced by one unit , the value of the maximum flow in N is also reduced.
Prove that your algorithm is correct and analyze its time complexity.
Dept. of Computer Science, University of Toronto, St. George Campus page 1 of 1