4. A 5-coloring sequence of length n (with n 1) is a sequence of the...

 

Transcribed Image Text:

4. A 5-coloring sequence of length n (with n ≥ 1) is a sequence of the colors red, blue, green, yellow, and violet (R.B,G,Y,V) such that no color occurs in two consecutive entries. Here are 2 examples of length 8 5-coloring sequence: RBGYVRBG, BRBRBRVY (a) (3 points) How many 5-coloring sequences of length n are there? (give a brief justification.) (b) (3 points) How many bits would the most efficient encoding of such a sequence use? (in terms of n.) (give a brief justification using the first part.) (c) (4 points) Describe your own encoding/decoding algorithm where the code uses the optimal number of bits from above. (Your description should explain how to code arbitrary sequence, and how to decode the codeword to get back the sequence.) (d) (2 points) Use your encoding to encode the example sequences above. (you are not required to provide justification.) 4. A 5-coloring sequence of length n (with n ≥ 1) is a sequence of the colors red, blue, green, yellow, and violet (R.B,G,Y,V) such that no color occurs in two consecutive entries. Here are 2 examples of length 8 5-coloring sequence: RBGYVRBG, BRBRBRVY (a) (3 points) How many 5-coloring sequences of length n are there? (give a brief justification.) (b) (3 points) How many bits would the most efficient encoding of such a sequence use? (in terms of n.) (give a brief justification using the first part.) (c) (4 points) Describe your own encoding/decoding algorithm where the code uses the optimal number of bits from above. (Your description should explain how to code arbitrary sequence, and how to decode the codeword to get back the sequence.) (d) (2 points) Use your encoding to encode the example sequences above. (you are not required to provide justification.)