Alice and Bob are playing an interesting game. They both each have a string, let them be a

and b$.$ They both decided to find the biggest string that is common between the strings they

have. The letters of the resulting string should be in order as that in a and b but don't have to be

consecutive. Discuss its time complexity.

Write the subproblems in English, Recurrence Relation and Pseudo code as well $(20$ Points$)$

a$)$ Define $($in plain English$)$ subproblems to be solved. $(2$ pts$)$

b$)$ Write down the base cases: $(2$ Points$)$

c$)$ Write the recurrence relation: $(6$ Points$)$

d$)$ Write the pseudoCode for telling if such a string can be found and if so$,$ find the resulting

string. $(8$ Points$)$

e$)$ Write the time complexity $(2$ Points$)$