Exercise 2.6.2 from Mining of Massive Datasets : Provide the details of the proof that a one-pass matrixmultiplication algorithm requires replication rate at least r 2n 2/q, including:

(a) The proof that, for a fixed reducer size, the maximum number of outputs are covered by a reducer when that reducer receives an equal number of rows of M and columns of N.

(b) The algebraic manipulation needed, starting with Pk i=1 q 2 i 4n 4 .