Input: A, B and C are all n x n matrices Output: True, if A.B A = Freivald's algorithm is as follows: Step 1 Select a vector v uniformly from a given finite set V Step 2 Compute vc = .v, vb B.v, and Vab A.vb Step 3 If vab == vc output True, otherwise output False. Let = (12) 3 4 (a) Does A.B this.) == == C, Otherwise False with probability at least 1/2 4 (15) 6 7 C or not? (Use direct matrix multiplication for = B = ; = (3 16 29 36 42 (b) How many multiplications did you need to do to answer part (1) by direct matrix multiplication? (c) Given a set V of two vectors V = {v, v2}, where: "=(6) - (9) V1 V2 = How many multiplications are needed to execute Step 2 of Freivald's algorithm, for A, B, C and V? (Just count for a single execution, and include multiplications by 0.) (d) Explain why Freivald's algorithm outputs the correct answer for these inputs A, B, C, V with probability 1/2. (e) How many multiplications PLUS comparisons are needed in Freivald's algorithm (for these values of A, B, C, V)? Compare your answer to the number of multiplications PLUS comparisons for an algo- rithm that uses direct calculation. (f) Why is Freivald's algorithm considered to be more efficient than using direct matrix multiplication to solve this problem? Com- ment on the number of multiplications PLUS comparisons.