3. Encoding and Decoding (a) A flippity fiip binary string is a binary string that is the same when the order of the bits is reversed and then all of the bits are inverted. For example, 010101 (reversed/backwards order: 101010), 0011 (reversed/backwards order: 1100), and 11001100 (reversed/backwards order: 00110011) are flippity flip binary strings. (12 points) i. How many flippity flip binary strings are there of length 2n ? 2 ii. How many bits would the most efficient encoding of such strings use? (in terms of n.) iii. Develop your own encoding/decoding algorithm where the code uses this number of bits. (Please give a brief description of how it works on an arbitrary input.) iv. Use your encoding to encode the following flippity flip binary strings: - 0011010011 - 0110101001 - 010101 v. Use your decoding to decode the following strings: (put "not decodable" if you can't decode the string.) - 110 - 101 - 000 (b) A valley permutation of length n is an arrangement of the numbers 1 through n in such a way that the numbers decrease down to a point and increase after that and each number is used exactly once. For example: (6,4,1,2,3,5) is a valley permutation of length 6 . (5,4,2,1,3,6,7) is a valley permutation of length 7 . Note that this includes permutations that are strictly decreasing, like (5,4,3,2,1), and permutations that are strictly increasing, like (1,2,3,4,5,6). (12 points) i. How many n-length valley permutations are there? ii. How many bits would the most efficient encoding of such permutations use? (in terms of n.) iii. Develop your own encoding/decoding algorithm where the code uses this number of bits. (Please give a brief description of how it works on an arbitrary input.) iv. Use your encoding to encode the following valley permutations: - (8,6,4,2,1,3,5,7) - (3,2,1) - (1,2,3,4,5,6,7) v. Use your decoding to decode the following strings: (put "not decodable" if you can't decode the string.) - 001001 - 10111 - 00100