4. Use a loop invariant to find any error(s) in the following algorithms. If any errors are found, correct them and redo the loop invariant. You must submit the proof of correctness showing the errors in algorithm logic, as well as for your fixed algorithm. Note: There is no general recipe for finding a loop invariant of an algorithm. It could be helpful to see previous assignments of this course to understand how to find a loop invariant and use it to show your algorithm is correct. (a) (10 points) The following algorithm computes x", where x > 0 and n > 0, in a more efficient way than multiplying x by itself n - 1 times. Require: x > 0, n > 0 1: ans = 1, a = x, p=n 2: while p > 0 do 3: if p is odd then 4: ans = ans * a 5: a = a* a p= (p - 1)/2 7: else 8: a = a* a p=p/2 10: end if 11: end while 12: return ans * HINT: Calculate a few iterations by hand. Look for patterns in how ans is related to ap and r". (b) (10 points) The following algorithm finds the maximum GCD (Greatest Common Divisor) of a pair of elements in an array. Require: array A of positive integer numbers 1: m = max(A) 2: create array D of size m 3: for i = 1 to length(A) do for j = 1 to m do 5: if A[i] %j= 0 (i.e., j is a divisor of the ith entry of A) then D[j] = D[j] + 1 if j != A[i]/j (i.e., j is different from the ith entry of A divided by i) then D[A[i]/j] = D[A[i]/j] + 1 end if end if 11: end for 12: end for 13: return scan D from first index to last, returning the index of the first entry whose value is greater than 1