CSC 344
Homework 5

Assigned Apr 25, due May 7

• Chap. 7, problem 3 (specific flow networks), 2 points (1 point each).
• Chap. 7, problems 4-5 (alleged facts about flow networks), 1 point each.
• Chap. 7, problem 7 (mobile computing), 2 points.
• Chap. 7, problem 15 (cooking schedule), 2 points.
• Chap. 13, problem 2 (voting), 1 points.
• Chap. 13, problem 3 (contention resolution), 4 points.
• Chap. 13, problem 5 (paying for cable), 2 points.

• Suppose you're given three nxn matrices A, B, and C, and you want to check whether AB=C. You could, of course, multiply AB and compare it with C, using O(n³) time with the obvious multiplication algorithm or O(n^2.8) time with the Schönhage-Strassen algorithm, but intuitively it seems it ought to be easier to check the multiplication than to compute it.

  Let v be an n-vector of 1's and 0's, each entry chosen independently by flipping a fair coin. Prove that if M is a non-zero nxn matrix, the probability of Mv=0 is at most 1/2. Using this fact, give a randomized algorithm to test whether AB=C in O(n²) time, and explain why your algorithm is never wrong.