15110 SUMMER SESSION ONE - 2013

Problem Set 6 - due Thursday, June 6 at 10:30AM 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, and the assignment number.
• You must hand in your homework at the start of class on the given due date.

Exercises

1. (1 pt) Recall from class that we have shown you how to compute the total sum of all integers in a two-dimensional 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
   

   Show how to modify this function so that it prints the sum of each row of the two-dimensional array. (HINT: Two of the statements will have to move to different places in the function.)

2. (2 pts) A music playing application stores a sequence of four-minute music files for playback. (All songs are the same length of time.) 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 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. 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.

3. (1 pt) 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 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 = [7, 3, "+", 4, 2, "-", "*", 8, 2, "/", 1, "+", "/"]
   

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

4. (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.

5. (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 0..string.length-1 do
       k = string[i] + k * 256
     end
     return k % table_size
   end
   

   In the function above, 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.

6. (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.

7. (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.

8. (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 inf (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.)

      inf = 1.0/0.0
      
      vertices = ["New York", "Pittsburgh", "Los Angeles", "Dallas", "Atlanta"]
      
      edges = [ [inf,  5,  2,  6,  1], 
                [5,  inf,  8,  inf,  3],
                [2,  8,  inf,  7,  4],
                [6,  inf,  7,  inf,  9],
                [1,  3,  4,  9,  inf] ]
      

   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?