15110 Spring 2013 [Kaynar/Gunawardena]

Problem Set 7 - due Wednesday, March 20 in class

Reading Assignment

Read sections 7.1-7.6 in chapter 7 of the textbook Explorations in Computing and chapter 3 of Blown To Bits. Because of its timing this homework covers 3 different topics: data structures that we did not cover in ps6, data representation and some Boolean logic and logic gates. Therefore, it is worth 14 points as opposed to 10 points. You have a long time to complete it but we advise you to start early so that you have enough time to think about each question and ask questions to course staff if needed.

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, lab section (A-N), 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 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 ∞ (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.)
```
vertices = ["New York", "Pittsburgh", "Los Angeles", "Dallas", "Atlanta"]

edges = [ [∞,  5,  2,  6,  1], 
          [5,  ∞,  8,  ∞,  3],
          [2,  8,  ∞,  7,  4],
          [6,  ∞,  7,  ∞,  9],
          [1,  3,  4,  9,  ∞] ]
```
2. 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 pts) Answer this question based on your understanding of graphs in general.
1. Suppose we want to form an undirected graph with N nodes and no links from a node to itself. What is the maximum number of possible links (edges) we could have in that graph?
2. Suppose that we have an unweighted graph $G$ that is represented by a two-dimensional array (by weights we mean the annotations on edges). Instead of holding weights, the array contains booleans indicating whether two nodes are connected. Describe an algorithm that finds all the nodes that are reachable from a given node $x$ in $G$ in exactly two steps.
(2 pts) Consider the three 8-bit binary numbers given below. Answer the following questions for each of these numbers.
```
       01000011 

       11000011 

       10000000 
```
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 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 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 and scroll down to the vocabulary list at the end. Find a word that would be longer if encoded with the Huffman tree than with the 4-bit fixed-width code above. (Hint: look at words that use lots of low-frequency letters.) 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) Image encodings:
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.
(2 pt) Answer the following questions about data representation based on Chapter 3 of Blown to Bits.
1. What is spatial coherence and temporal coherence with respect to images? How does each concept allow us to transmit images using fewer bits?
2. Document redaction by black highlighting is ineffective and has led to several politically embarassing incidents. One redaction method that is guaranteed to work is to print out the document, black out the sensitive sections with a real magic marker, and then scan the pages. What are two disadvantages of this approach?
(1 pt) 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
```
(1 pt) 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.
(1 pt) 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
```