3. Strings and Codes (25 marks) (a) Given two strings X = DBABAFB and Y = DABFBCB. Let Ics[i,j] be the length of the longest common subsequence of Xi and Y;. Compute a table Ics using the dynamic pro- gramming algorithm as well as the longest common subsequence of X and Y. (5 marks) (b) Does there exist a universal lossless compression algorithm that can make every file shorter? Justify your answer. (5 marks) (c) Given a text T in alphabet {a,b,c,d}, which contains 10 of a symbols, 20 of b symbols, 5 of c symbols and 25 of d symbols. Consider the following two codes A and B: CODE A = a 100 b 0 110 d 111 CODE B = a 00 b01 10 d 11 Build two trees associated with the above codes and decide which code is more efficient for compressing a text T. Does any of the codes above is optimal for the text T? Explain your answer. (10 marks) (d) Suggest an input on which compression ratio for Lempel-Ziv Welch (LZW) algorithm will be better than for Huffman coding. What are the main differences between these algorithms