Data Compression Help Center

Learn more

Warning: The hard deadline has passed. You can attempt it, but you will not get credit for it. You are welcome to try it as a learning exercise.

To specify an array or sequence of values in an answer, separate the values in
the sequence by whitespace. For example, if the question asks for the first
ten powers of two (starting at 1), then the following answer is acceptable:

     1 2 4 8 16 32 64 128 256 512

If you wish to discuss a particular question and answer in the forums, please
post the entire question and answer, including the seed (which can be used by
the course staff to uniquely identify the question) and the explanation (which
contains the correct answer).

Question 1

(seed = 540634)
Compute the Huffman trie for the following string of length 46?

    XXWBHWBBWYOOBVWWXVYXWBBWVOWOBWHXXHBBWOBVBBXBWX

For reference, here are the frequencies of each of the characters in the string:

    char  freq
    ----------
       B    13
       H     3
       O     5
       V     4
       W    11
       X     8
       Y     2


Using the encodings from the Huffman trie you computed, how many bits are needed
to encode the above string? Do not count the bits to represent the encoding table
or any bits used for padding and byte alignment.

Question 2

(seed = 207661)
What is the result of expanding the following LZW-encoded sequence of 11 hexadecimal integers?

    41 42 41 43 42 82 83 84 41 87 80 

Assume the original encoding table consists of all 7-bit ASCII characters and uses 8-bit codewords.
Give your answer as a sequence of characters, with one space between each character.

Question 3

(seed = 114153)
What is the result of compressing the following string of length 15 using LZW compression?

     A C A B A B C C A B A A B C A 

Assume the original encoding table consists of all 7-bit ASCII characters and uses 8-bit
codewords. Give your answer as a sequence of 11 hexadecimal integers, starting with 41
and ending with the stop codeword 80.
    
You cannot submit your work until you agree to the Honor Code. Thanks!