Problem 1. Measuring information A. Someone picks a name out of a hat known to contain the names of 5 women and 3 men, and tells you a man has been selected. How much information have they given you about the selection? | MIT OpenCourseWare http Computation Structures Spring 2009 For information about citing these materials or our Terms of Use visit http terms. Basics of information Problem 1. Measuring information A. Someone picks a name out of a hat known to contain the names of 5 women and 3 men and tells you a man has been selected. How much information have they given you about the selection B. You re given a standard deck of 52 playing cards that you start to turn face up card by card. So far as you know they re in completely random order. How many new bits of information do you get when the first card is flipped over The fifth card The last card C. X is an unknown N-bit binary number N 3 . You are told that the first three bits of X are 011. How many bits of information about X have you been given D. X is an unknown 8-bit binary number. You are given another 8-bit binary number Y and told that the Hamming distance between X and Y is one. How many bits of information about X have you been given Problem 2. Variable length encoding compression A. Huffman and other coding schemes tend to devote more bits to the coding of A symbols carrying the most information B symbols carrying the least information C symbols that are likely to be repeated consecutively D symbols containing redundant information B. Consider the following two Huffman decoding tress for a variable-length code involving 5 symbols A B C D and E. Tree 1 Tree 2 . XX o i A X X X X XX X A B c Xj B c D 1 X D E Using Tree 1 decode the following encoded message 01000111101 . C. Suppose we were encoding messages that the following probabilities for each of the 5 symbols p A p B p C p D p E Which of the two encodings above Tree 1 or Tree 2 would yield the shortest encoded messages averaged over many messages D. Using the probabilities for A B C D and E given above construct a variable-length binary decoding tree using a simple greedy algorithm as follows 1. Begin with the set S of .
