Q4 15 Points String a appears as a sub-sequence in string y if we can delete some of the characters in y, and the remaining characters from left to right are exactly those of . The remaining characters do not have to be consecutive. For example, if & = GRIM, y = ALGORITHM, is a subsequence in y because it is positions 3, 5, 6 and 9 in order. Consider the following recursive algorithm which given sequences a and y, checks whether * = 1..I'm is a subsequence of y = y1..yk: ReclsSubsequence (2 = $1.Cm; y = y1.-yk) 1. If m = 0 return True 2. If m > k return False 3. IF $1 = y1 then return ReclsSubsequence(X2...I'm; y2..yk) 4. Return ReclsSubsequence(T1 . .Cm; y2...yk) Correctness. (7 points) Prove by strong induction on n = m + k that ReclsSubsequence returns True if and only if @1..Cm is a subsequence of y1 . .yk. Enter your answer here Recurrence. (4 points) Explain why the recurrence for this algorithm is T(n)