15110 Summer 2012

Problem Set 3 - due Monday, June 25 in class

Reading Assignment

This assignment covers chapters 7, 8 and 9 in your textbook.

Instructions

Type or neatly write the answers to the following problems.
Please STAPLE your homework before you hand it in.
On the first page of your homework, include your name and andrew ID.
You must hand in your homework at the start of class on the given due date.

Exercises

Consider the 8-bit value 10101011.
1. What is its value if it is interpreted as an unsigned integer? Show your work.
2. What is its value if it is interpreted as a signed integer? Show your work.
3. Write this value in hexadecimal.
(1 pt) As we discussed in class, floating point numbers are stored in binary using various formats, and one popular format is IEEE-754. How are the following values stored in binary using IEEE-754 format?
1. The binary value: 110.01011
  (HINT: First, convert this into the following form: 1.______ × 2^exponent)
2. +infinity
  (HINT: You can use the Internet to research this question.)
Using the Huffman tree for the Hawaiian alphabet shown on page 186 of your textbook (and in our course slides):
1. Decode the following Hawaiian word that was encoded into binary using the given Huffman tree: 0001011000111110000100110.
  Once you decode the word, you can use RubyLabs to check your answer:
```
>> include BitLab
=> Object
>> f = read_frequencies(:hafreq)
=> {"K"=>0.106, "W"=>0.009, "L"=>0.044, ... }
>> tree = build_tree(f)
=> { 1.000 { 0.428 { 0.195 { ... } } } }
>> hc = assign_codes(tree)
=> {"K"=>001, "W"=>110010, "A"=>10, ... }
>> encode(INSERT_YOUR_ANSWER_HERE, tree)
=> 0001011000111110000100110
```
  See sections 7.4 and 7.5 for more information on how to build a Huffman tree, and how to encode and decode messages using RubyLabs.
  (NOTE: Be sure you understand what each of the steps are doing above. Read through the relevant sections for a thorough explanation and try out the tutorial in the textbook for yourself.)
2. The Hawaiian alphabet has 13 characters (5 vowels, 7 consonants and 1 apostrophe). If we used a fixed-width encoding for characters (i.e. every character is encoded using the same number of bits), we would need a 4-bit code for every character so we could get at least 13 unique codes for the 13 characters of the Hawaiian alphabet:
```
A   0000       U   0100       L   1000       W   1100
E   0001       '   0101       M   1001
I   0010       H   0110       N   1010
O   0011       K   0111       P   1011
```
  Go to Popular Hawaiian Words and Phrases. Find a word that would be longer if encoded with the Huffman tree than with the 4-bit fixed-width code above. Give the encoding using the Huffman tree and the 4-bit fixed-width code above to justify your answer.
3. In general, when do you get shorter binary encodings using Huffman trees?
As discussed in class, we can use the notion of parity to detect when an error occurs after transmission of data. Universal Product Codes (UPCs) also use this idea, often called a check digit. A UPC barcode is made up of 11 digits followed by a check digit.

The check digit is computed using the following algorithm:
```
1. Add the first, third, fifth, seventh, ninth and eleventh digits
   of the UPC barcode and store this result in x.
2. Add the second, fourth, sixth, eighth and tenth digits 
   of the UPC barcode and store this result in y.
3. Set z equal to the last digit of the value 3x + y.
5. If z is not equal to 0, then set check_digit equal to 10 - z. 
   Otherwise, set check_digit equal to z.
```
1. Determine the check digit needed to complete the following UPC barcode:
```
32390001453_
```
2. We are given the following 12-digit UPC barcode:
```
718123006804
```
  Is there an error in the barcode? Show your computation to justify your answer.
1. The RGB color for goldenrod is given in hexadecimal as DAA520. Express the red, green and blue values of this color in decimal. Show your work.
2. An image format takes a 24-bit RGB image and compresses it as follows. For each pixel, we average the red, green and blue components and store only this average. This yields a file that is one-third the size of the original image file. Is this compression algorithm a lossless or lossy compression technique? Explain.
For the following Boolean expressions, write a truth table that shows the value of the function for each possible combination of assignments to the boolean variables X, Y, and Z. Use 1 for true and 0 for false.
```
(X and Y) or (Y and (not Z))

(not (X or (not Y))) and Z
```
The boolean expressions in the previous problem can be realized as an electric circuit. Such circuits can be represented abstractly using logic gates (instead of transistors). Draw how these expressions would be realized as a computational circuit at the gate level of abstraction.
In Ruby, there is another loop called an until loop that runs until a particular condition is true. For example, Consider the following code using a while loop:
```
i = 0
sum = 0
while i != 10 do
    sum = sum + i
    i = i + 1
end
```
We can also write this code equivalently using an until loop:
```
i = 0
sum = 0
until i == 10 do
    sum = sum + i
    i = i + 1
end
```
Use DeMorgan's Law to convert the following while loops to equivalent until loops.
1. ```
while (x >= 40) and (y < 68) do
   ...
end
```
2. ```
while (a != 15) or (b == 110 and c <= 112) do
   ...
end
```