Algorithmic mathematics

1. Consider the statements below, where the variables m and n are assumed to have integer values, with n > 0, and let W denote the while-loop in these statements. a :=m; b=n; c=0; while b>0 do if 2b then a := 2a; b=b/2; else c=c+a; b=b-1; fi; od; (a) (30p) Prove that ab +c=mn is a loop invariant for W. (b) (10p) Must W terminate? Why? What is the value of b on this termination? (e) (10p) Show that on the termination of W, we have that c= mn. 2. Let F=Z/(11), and let W1 = (1, 0, 7,3) W2 = (0,1,3,4) W3 = (0, 0, 0, 1) F4 (a) (30p) Use the algorithm Sift that is given in page 71 of Soichers Algorithmic Mathematics book to prove that vector v = (5, 2, 4, 3) is not a member of the linear span . (b) (20p) Write v = (5, 2, 4, 3) in the form v=u+ajw1 + a2W2 + azw3