2. (a) Given a non-empty array of numbers A[1...], the running minimum of A is an array M1...n], in which the element i contains the minimum in the subarray A[i...il. Some examples are: input: A output: M [1.7,0) [1,1,0 [4,2 [4.2] [10, 11,2,1 [10, 10, 2, 1] [10, 11, 7, 16,3,5, 12, 11, 1,9] [10, 10,7,7,3,3,3,3,1, 1] Write an algorithm, in the complexity class e(n), which inputs an array A[1...] and outputs the running minimum of A. You should explain why you think your algorithm is in the class e(n). (20 marks] (b) Explain what it means to strengthen an invariant. Demonstrate the technique on the following algorithm which computes factorial of the Input k. Show that this algorithm is correct by using the While-loop invariance theorem, and demonstrating how to strengthen the invariant. Input:k: Output: k! 1X1 2 Y 1 3 while x