15110 SUMMER SESSION TWO - 2014

Problem Set 7 - due Tuesday, July 22 at 9:00AM in class

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, andrew ID, and the assignment number.
You must hand in your homework at the start of class on the given due date.

Exercises

(1 pt) This problem deals with a binary tree known as a binary search tree.
1. Insert the following integers into a binary search tree one at a time in the order given and show the final result:
  59 24 35 78 61 42 90 88 15 57
2. Suppose you are now looking for the key 57 in your binary search tree. Which keys in the tree do you examine during your search? List the keys you have to examine in the order you examine them.
(1 pt) This problem deals with a binary tree known as a max-heap.
1. Insert the following integers into a max-heap one at a time in the order given and show the final result:
  66 22 81 23 50 73 39 33 42
  NOTE: For this problem, you should show the max-heap after each individual element is inserted so you don't get lost.
2. For a max-heap of integers, where must the minimum integer be? Explain.
(1 pt) This problem deals with the data structure known as a graph.
1. Draw the graph that is represented by the lists below. The values in the edges list represent the cost to fly directly from one city to another city in hundreds of dollars. Each row represents a city a plane flies from, and each column represents a city a plane flies to. For example, you can fly from New York to Pittsburgh for $500, and you can fly from Los Angeles to Dallas for $700. If an entry is f (infinity), then that means that there is no direct flight from one city to another. (Note that there are no direct flights from a city to itself.)
```
f = float("inf")

vertices = ["New York", "Pittsburgh", "Los Angeles", "Dallas", "Atlanta"]

edges = [ [f,  5,  2,  6,  1], 
          [5,  f,  8,  f,  3],
          [2,  8,  f,  7,  4],
          [6,  f,  7,  f,  9],
          [1,  3,  4,  9,  f] ]
```
2. Based on your answer from part a, what is the cheapest cost to fly from Pittsburgh to Los Angeles? Do you need to make any transfers? If so, at what city or cities?
(1.5 pts) 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.)
(1.5 pts) 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 python3 to check your answer. First, put the functions make_pq and build_tree into a file huffman.py. Then:
```
python3 -i huffman.py
>>> from PythonLabs.BitLab import PriorityQueue, Node, assign_codes, encode, decode
>>> table = [ ["'", 0.068], ["A", 0.262],
["E", 0.072], ["H", 0.045], ["I", 0.084],
["K", 0.106], ["L", 0.044], ["M", 0.032],
["N", 0.083], ["O", 0.106], ["P", 0.030],
["U", 0.059], ["W", 0.009] ]
>>> pq = make_pq(table)
>>> tree = build_tree(pq)
>>> ht = assign_codes(tree)
>>> encode(INSERT_YOUR_ANSWER_HERE_AS_A_STRING, tree)
0001011000111110000100110
```
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?
(1 pt) 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.
4. 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.
(2 pts)
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.
3. A black-and-white image is stored using Run Length Encoding as follows:
  
  Decode the encoded image by filling in the appropriate pixels and state what the image represents.