1. [20 points, Lower Bound and Reduction] If M(n) is the time needed to multiply two n×n matrices, and S(n) is the time needed to square an n×n matrices. Show that M(n) = Big-Omega(S(n)).    [Hint: think about square of S, where s11 = A, s12 = 0, s21 = B, s22 =0]

2. (10) Exercise 34.3-1. p994. Label the outputs of each connector/operator as y's (e.g. y1, y2,..) and list the truth values of them together with truth value combinations of x's in a table.

3. (10) Exercise 34.4-6, p1002.

4. (20) Exercise 34.5-5. p1017
 
5. [20 points, Net Flow] 26.1-9, p650.

6. [20 points, Max Flow] 26.2-2, p663.