15110 Fall 2012 [Touretzky/Kaynar]

Problem Set 6 - due Friday, October 12 in class

Reading Assignment

Read sections 6.1-6.6 in chapter 6 of the textbook Explorations in Computing.

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) Suppose we have a matrix of integers represented as a two-dimensional array, where each element of the array is itself an array corresponding to a row in the matrix. Recall from class that we have shown you an example of such an array and how to compute the total sum of all integers in that array as follows:
```
def print_sum(matrix)
    sum = 0
    for row in 0..matrix.length-1 do
        for col in 0..matrix[row].length-1 do
            sum = sum + matrix[row][col]
        end
    end
    print sum, "\n"
end
```
Using this function as a guide write a function print_col_sum(matrix) to print the sum of each column of the two-dimensional array. You should think about how to nest the for loops and where to put the print statement so that you can print as many numbers as there are columns.

(1 pt) (corrected) An RPN expression can be stored in array 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 s equal to an empty stack.
3. While i is not equal to the length of the rpn array, do the following:
   a. Set x equal to rpn[i].
   b. If x is a number, then push x on stack s.
   c. 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.
   d. Add 1 to i and continue looping.
4. Pop stack s and return this number.

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

rpn = [8, 2, "+", 4, 2, "/", "*", 10, 2, "/", 5, "*", "+"]

(Draw a new stack whenever a number is pushed or popped, to show how the stack progresses throughout the computation. You can find an example in the lecture slides.)

(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 array named q such that the first element in the array (at index 0) is the front of the queue and the last element in the array (at index q.length-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 Ruby.
2. Show how to dequeue an element from the front of the queue q and store this element in the variable y.
(2 pts) (corrected) Suppose that a hash table has 10 buckets (i.e. its table size is 10). When keys are stored in the hash table, we use the following simple-minded hash function:
```
def h(string, table_size)
  k = ((string[0].ord)*26) + string[1].ord
  return k % table_size
end
```
In the function above, string[i] returns the ASCII code of the i^th character of string and the ord method gives its order in the alphabet. For lowercase letters, ord(x) is x-97. 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. To understand what the above hash function does, observe that the English alphabet has 26 chararacters. Given the hash function above, in which of the 10 available buckets 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.
  - box
  - bow
  - fox
  - bowl
2. Do any of these words collide if we were to put them into a hash table of size 10 using the hash function above? Why or why not?
3. The strings "ba" and "bk" fall into the same bucket. Likewise, "ca" and "ck" fall into the same bucket, as do "da" and "dk", etc. Why is this?
4. Show how to calculate another two-letter string beginning with "b" that falls into the same bucket as "ba" and "bk". Don't just write the answer; show where it comes from.
(2 pts) Answer this question based on your understanding of hash tables in general. Recall that hash tables give an expected or average case search time of O(1), or constant time.
1. What is the WORST CASE performance for hash table search? When would you encounter this situation?
2. Some hashing functions are better than others. Write the worst hashing function in the world. That is, think of the answer you gave to the previous part and write a hashing function that would lead to a worst case scenario.
3. Suppose you have N items and you build a hash table with only N/2 buckets. What is the number of expected items per bucket? What is the expected or average case performance of search using this hash table?
4. Suppose you decide to use sqrt(N) buckets. What is the expected number of items per bucket? What is the expected performance of search using this hash table?
(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?
(2 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. 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.