1. (Intermediate) In the Interval Selection (Activity Selection) problem, we're given n interval? (si,fi), 0, and the goal is to choose a max-weight subset of mutually disjointon-overlapping intervals. For the unweighted version, we had the following recursion max{M(j) + 1, M(i 1 otherwise where I is the interval with the largest finish time that ends before starts. Here, M(i) denotes the maximum number of mutually disjoint intervals that can be chosen from Io, /1, /2, ..., /i. Adapt this recursion to the weighted setting 3. (Basic) What is fixed-length code? What is prefix (or prefix-free) code? Is a fixed length code always prefix-free? Why do you need prefix-freeness? 4. (Basic) Assume the following when executing the Huffman algorithm: When combining two trees, the tree with lowest root frequency becomes the left child and the tree with the second-lowest root frequency becomes the right child. Left children are associated with the bit 0, right children with the bit 1.Run the Huffman's algorithm on the following input: a: 3, b: 2, c: 4, d: 8, e : 7, f : 14. What is the codeword for each character? Give a tree representation 5. (Basic) Repeat the previous question on the input, a : 1, b: 2, c 4, d: 5, e:6, f :9 6. (Basic) Explain why a prefix-free code is not optimal if some node has exactly one child in the tree representation