String shuffling (From Erickson) A shuffle of two strings X and Y is formed by interspersing the characters into a new string, keeping the characters of X and Y in the same order. For example the string BANANAANANAS is a shuffle of the strings BANANA and ANANAS in several different ways:

BANANAANANAS BANANAANANAS BANANAANANAS Similarly the strings PRODGYRNAMAMMIINCG and DYPRONGARMAMMICING are both shuffles of DYNAMIC and PROGRAMMING in the following ways:

PRODGYRNAMAMMIINCG DYPRONGARMAMMICING Given three strings X[1... m), Y[1...n] and Z[1... M+n] design a solution based on dynamic programming to determine whether Z is a shuffle of X and Y.

(a) Write a recurrence relation to compute the answer. Argue how this answer contains within it solutions to smaller sub-problems. Briefly justify why your recurrence is correct.

(b) Using your recurrence, design a bottom-up dynamic programming algorithm to produce a Yes/No\" answer to whether Z is a shuffle of X and Y.

(c) Analyze the running time and space usage of your algorithm.