15110 SUMMER SESSION TWO - 2014

Problem Set 6 - due Thursday, July 17 at 9:00AM in class

Reading Assignment

Read chapter 3 in Blown To Bits.

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) Recall from class that we have shown you how to compute and print the total sum of all integers in a two-dimensional list as follows:
```
def print_sum(matrix):
    sum = 0
    for row in range(0,len(matrix)):
        for col in range(0,len(matrix[row])):
            sum = sum + matrix[row][col]
    print sum
```
Show how to modify this function so that it prints the sum of each row of the two-dimensional list. (HINT: Draw a flowchart of this function for yourself and then move two operations in the flowchart to get the desired behavior.)
(2 pts) A music playing application stores a sequence of four-minute music files for playback. (All songs are the same length of time for this problem.) The music files can be stored in one of two ways:

Algorithm 1: Songs are stored in the computer's memory in arbitrary order. Each song has a code that indicates the location in memory of the song that plays next. The player keeps track of the location of the first song in the playback sequence only.
Algorithm 2: Songs are stored in the computer's memory in the order of playback starting at a specific fixed location in computer memory which cannot be changed.
1. If the application user wants to insert a new song at the beginning of the playlist, which algorithm will allow the user to complete this operation faster? Explain your answer by describing what each algorithm would do to accomplish this task.
2. If the application user wants to skip to the 50th song in the playback list, which algorithm will allow the user to hear this song faster? Explain your answer by describing what each algorithm would do to accomplish this task.

(2 pts) An RPN expression can be stored in a list as follows:

rpn = [23, 3, "-", 4, 6, "+", "/"]

Recall the algorithm to compute the value of a RPN expression using a stack:

1. Set i equal to 0.
2. Set x equal to rpn[i].
3. Set s equal to an empty stack.
4. While i is not equal to the length of the rpn array, do the following:
   a. If x is a number, then push x on stack s.
   b. If x is a string (i.e. operator), then do the following:
      i.   Pop stack s and store number in b.
      ii.  Pop stack s and store number in a.
      iii. If operator is "+", push a+b on stack s.
      iv.  If operator is "-", push a-b on stack s.
      v.   If operator is "*", push a*b on stack s.
      vi.  If operator is "/", push a//b on stack s.
   c. Add 1 to i.
5. Pop stack s and return this number.

Trace how this algorithm computes the value of the following RPN expression stored as an array:

rpn = [9, 3, "+", 7, 5, "-", "*", 6, 2, "/", 1, "+", "/"]

(Draw a new stack whenever a number is pushed or popped to show how the stack progresses throughout the computation.)

(1 pt) A stack is a data structure with a LIFO (Last In First Out) property. That is, the last element you put in is the first one you can take out. Now consider a queue, a data structure with a FIFO (First In First Out) property. In this case, the first element you put in is the first one you can take out. With a queue, you enqueue (enter the queue) on to the rear of the queue, and you dequeue (depart the queue) from the front of the queue.
Suppose we represent a queue using an list named q such that the first element in the list (at index 0) is the front of the queue and the last element in the list (at index len(q)-1) is the rear of the queue.
1. Show how to enqueue an element stored in the variable x on to the rear of the queue q using Python.
2. Show how to dequeue an element from the front of the queue q and store this element in the variable y using Python.
(2 pts) A hash table has 13 buckets (i.e. its table size is 13). When keys are stored in the hash table, we use the following hash function:
```
def h(string, table_size):
    k = 0
    for i in range(0,len(string)):
        k = ord(string[i]) + k * 256
    return k % table_size
```
In the function above, ord(string[i]) returns the ASCII code of the i^th character of string. Here are the ASCII codes for the lowercase letters:
```
  a   b   c   d   e   f   g   h   i   j   k   l   m  
 97  98  99 100 101 102 103 104 105 106 107 108 109

  n   o   p   q   r   s   t   u   v   w   x   y   z
110 111 112 113 114 115 116 117 118 119 120 121 122
```
1. Given the hash function above, in which bucket would the following words be stored? Show all steps of the computation to show the bucket that is chosen. Do not write the final answer only.
  - cow
  - fox
  - dog
  - owl
2. Do any of these words collide if we were to put them into a hash table of size 13 using the hash function above? Why or why not?
3. If 3n words are put into a hash table with n buckets so that the number of words per bucket is 3, what is the order of complexity to search for a word in the hash table in big O notation? Briefly explain your answer.
(2 pts) Based on Chapter 3 of Blown To Bits, answer the following questions about data representation.
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. Steganography is the hiding of information within other information. Using one of the examples given in the chapter as a guide, find the hidden location in the following company announcement:
  Caution: Always review new employees gathered in each meeting. Examine late listings on nightly updates. Never invite visiting exhibitors. Review security information. Thank you.