Assignment 3 Part I Solution

Matrix Puzzle



You want to fill a matrix of n rows and m columns with non-negative 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 non-negative integers r1; : : : ; rn, c1; : : : ; cm, and b1;1; : : : ; bn;m, find integers a1;1; : : : ; an;m such that:




0 6 ai;j 6 bi;j for all 1 6 i 6 n, 1 6 j 6 m;
ri = Pmk=1 ai;k for all 1 6 i 6 n;



cj = Pnk=1 ak;j for all 1 6 j 6 m.



Knight Coexistence



You want to place knights on an n n chessboard. The chessboard has n2 positions from (0;0) to

(n 1; n 1). A knight at position (x; y) is able to attack up to eight different 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


CSC 373 H1
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 , e0 2 E is an edge
with f (e0) = c(e0), and N 0 is the same network as N except that c0(e0) = c(e0) 1, then the maximum flow f 0 in N 0 satisfies jf 0j < jf j.




Write an algorithm that takes a network N = (V ; E), maximum flow f in N , and an edge e0 2 E with f (e0) = c(e0), and that outputs a maximum flow for network N 0, where N 0 is the
same as N except that c0(e0) = c(e0) 1.




Provide a brief argument that your algorithm is correct and analyze its time complexity. For full marks, your algorithm should be as efficient as possible.







Write an algorithm that takes a network N = (V ; E) and that outputs a list of all edges e1; : : : ; ek 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