Code must be written in C Language/ UBUNTU environment.

To get full credit for each question, you need to provide a brief explanation of your codes and the efficiency analysis with comments.

2. Devise a dynamic programming algorithm that takes three bit strings X = X1.... Xn Y = y. --- Ym, and 2 = 2 ... Zn+m, and output 'YES' if Z is an interleaving of X and Y, and NO' otherwise. Note that the string Z is called an interleaving of X and Y if Z can be obtained by interleaving the bits in X and Y in a way that it maintains the left-to-right order of the bits in X and Y. For example, if X = 101 and Y = 01, then 21 = 10011 is an interleaving of X and Y, but 22 = 11010 is not. Also, all the inputs given to the algorithm are assumed to be legitimate, i.e. the users are assumed to provide only bit strings