Problem 1. A smart lad Carl have just learnt how compress data with a Huffman code. Now he has to encode a message where all letters have different frequencies He thinks that the lengths of the Huffman codes for all letters also must be different. Is Carl right or not? If your answer is "yes", explain it. If your answer is "no", give a counterexample. Problem 2. As you know, when implementing a hash table, we normally have hash collisions where multiple elements have the same hash value. Thus, we should try to choose such a hash function that will not result in too many collisions. Suppose you have an empty hash table of length 13 with hash function h(x)mod n. Initially n was chosen to be equal to 13. a) How many collisions will be in the hash table for the following dataset: 14, 27, 40, 53, 66, 79,92, 105, 118, 131, 144? (b) Can you come up with another n for which the function h(x) mod n produces no collisions for this dataset without increasing the size of the hash table? If your answer is "yes", give the value of n and explain why there are no collisions. If your answer is "no", explain why it is impossible to do. (c) Propose a function different from h (x)-x mod n which produces no collisions for our dataset Problem 3. On your hard drive you have n files that you downloaded from the Internet. The size of the ith file is m GB, and it took you t, minutes to download it. You want to save the files to a cloud for backup. Unfortunately, your available cloud storage is limited to X GB, andt does not allow you to store all files. So you need to choose which files to save. You want to do it in such a way that in case of loss of unsaved files it will take you the smallest possible time to download them again. How to solve this problem using dynamic programming? Explain why your algo- rithm yields the correct solution and analyze its time complexity. Hint. This problem may (and should) remind you one of the problems that were discussed in class. , n and ,2 where n 2 m, determine whether or nor it is possible to cross out some elements from the first sequence to obtain the second sequence. For example, for the sequences 1, 12, 4,8, 10,6 and 12, 10, 6, the answer is "yes" (you can cross-out 1,4 and 8), whereas for the sequences -2,0, 4,0, 2,7 and 0, 2,4 the answer is "no" Propose an efficient algorithm to solve this problem. Hint. Could you use divide-and-conquer or dynamic programming