15110 Fall 2011 [Cortina/von Ronne]

Written Homework 5 - due Friday, October 14 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) Let matrix represent a two-dimensional array. You may assume that each row has the same number of columns for this problem. Homer Simpson writes the following Ruby function to print the sum of the elements in each row of the matrix, but, as expected, it's wrong. (D'oh!)
```
def print_sum_of_each_row(matrix)
    sum = 0
    for row in 0..matrix.length do
        for col in 0..matrix[row].length do
            sum = sum + matrix[row][col]
        end
        print sum
        print "\n"
    end
end
```
Explain his errors and correct the function. NOTE: There are 3 errors in his function.
(2 pts) At a large parking facility, the valet asks each person who drops off a car when he/she will be departing. Let's assume everyone knows exactly when they'll be leaving. The valet wants to choose between two algorithms to park the cars:

Algorithm 1: Park the cars one next to another, in order of the departure times. He puts a piece of paper inside each car with its departure time. When someone comes to pick up their car, he goes to the first car parked in the row and drives it up to the owner.
Algorithm 2: Park the cars in any available space. On a piece of paper inside the car, he writes the departure time for that car and the number of the parking spot for the car that will depart next in time. He also keeps track of the first car that will be leaving on a piece of paper. When someone comes to pick up their car, he goes to the car on the piece of paper and drives it up to the owner, keeping the piece of paper from inside that car so he knows where the next departing car is.
1. If the valet wants to find the 50th car that will leave, which algorithm will allow him to find the 50th car faster? Explain how the valet would use each algorithm to find the 50th car to justify your answer.
2. If another person arrives to have a car parked, which algorithm will require fewer cars to be moved? Explain how each algorithm would be used to park the car to justify your answer.
(1 pt) Consider the following Ruby function that uses the stack operations push and pop:
```
def mystery(word)
    n = word.length    
    stack = []
    for i in 0..n-1 do
        x = word[i]
        stack.push(x)
    end
    new_word = ""
    for i in 0..n-1 do
	y = stack.pop
        new_word += y.chr
    end
    return word == new_word 
end
```
Run this function using irb and call this function with various strings containing single words. Describe what this function is computing in one sentence. HINT: To figure out the function's purpose, you will need to read through the algorithm that is coded in the function to get clues as to what it is doing overall.
Also, give 3 examples of words that will result in this function returning true and 3 examples of words that will result in this function returning false.
(Ruby information: If word is a string, then word[i] gives us the ASCII code for the i^th character in the string. If y is the ASCII code of a character, then new_word += y.chr appends the character with ASCII code y on to new_word.)
(1 pt) Using the algorithm to solve the Josephus Problem as discussed in class, determine which person is the last survivor if we start with 12 people in a circle numbered 1 through 12 (n=12) and every sixth person is executed (m=6). Trace the algorithm, showing the contents of the queue (from front to rear) after each person is executed.
(2 pts) A hash table has 11 buckets (i.e. its table size is 11). When keys are stored in the hash table, we use the following hash function:
```
def h(string, table_size)
  k = 0
  for i in 0..string.length-1 do
    k = string[i] + k * 256
  end
  return k % table_size
end
```
Recall that 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.
  - cat
  - dog
  - fox
  - emu
2. Do any of these words collide if we were to put them into a hash table of size 11 using the hash function above? Why or why not?
3. If 2n words are put into a hash table with n buckets so that the number of words per bucket is 2, what is the order of complexity to search for a word in the hash table in big O notation? Briefly explain your answer.
(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:
  60 83 29 55 13 91 37 76 44
2. For any binary search tree with 9 elements, what is the maximum number of elements that need to be examined during a search of the tree? Explain your answer.
(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:
  60 83 29 55 13 91 37 76 44
  NOTE: For this problem, you will probably need to show the max-heap after each individual element is inserted so you don't get lost.
2. For any max-heap with 9 elements, what is the maximum number of elements that need to be examined if we add a new (10th) element to the heap? Explain your answer.
(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 from one city to another in hundreds of dollars. For example, 4 means you can fly for $400.
```
vertices = ["New York", "Chicago", "Los Angeles", "Dallas", "Atlanta"]

edges = [ [0,  4,  5,  6,  2], 
          [4,  0, 10,  3,  1],
          [5, 10,  0,  7,  9],
          [6,  3,  7,  0,  8],
          [2,  1,  9,  8,  0] ]
```
2. Based on your answer from part a, what is the cheapest cost to fly from Los Angeles to Chicago? Do you need to make any transfers? If so, at what city or cities?