15110 Fall 2011 [Cortina/von Ronne]

Programming Assignment 6 - due Tuesday, October 18

Overview

For this assignment, you will create a Ruby source file containing a ruby function(s) implementing each of the problems described below. If you find it useful for any of the problems in this assignment, you may define additional helper functions that your primary function for that problem calls to solve a sub-problem. Definitions for these helper functions should be included in the same Ruby source file as the primary function they help. You should store a source file for each problem in a folder named pa6.

Note: You are responsible for protecting your solutions to these problems from being seen by other students either physically (e.g., by looking over your shoulder) or electronically. (More information can be found in the instructions for Programming Assignment 2.)

Problems

  1. [2 points] Suppose n is an integer between 0 and 255 inclusive. The following algorithm converts n into a binary string using 8 bits:

    1. Set result equal to the empty string.
    2. Repeat the following 8 times:
      1. If n is odd, then attach "1" to the beginning of result.
        Otherwise, attach "0" to the beginning of result.
      2. Divide n by 2, ignoring any remainder.
    3. Return result.

    Write a Ruby function convert(n) (in convert.rb) that takes an integer and returns a binary string (of length 8) which is the binary representation of that unsigned integer. You may assume n is an integer between 0 and 255, inclusive.

    Example usage: TYPO in function name has been corrected

    >> convert(255)  
    => "11111111"  
    >> convert(100)  
    => "01100100"  
    >> convert(0)  
    => "00000000"  
    >> convert(65)  
    => "01000001"  
    
  2. [3 points] Computational approaches are increasingly applied to research in the humanities. For example, to help ascertain who the author of a document is, one might measure the frequency with which words are used in a document and compare that with other documents by the possible authors.

    In problem 4 of the last programming assignment, you compared two different ways of storing word count data. In this problem, you will look at how to count the occurrences of each word in the text.

    Download the file word_count2.rb into your pa6 directory, and load word_count2.rb into irb. The file word_count2.rb contains the function word_count(text) that counts the number of occurrence each word has in text, a helper function split_words(text), and a function sample_text() that returns a string containing a paragraph of text from Blown to Bits.

    The function word_count goes through each of the words in the string text and builds an array of word/count pairs (like in PA5, 4a), increasing the count each time the word occurs in the text. The word_count function is missing a helper function called update_count.

    Define a Ruby function update_count(count_list, word) (in update_count.rb) that adds one to the count of the entry in count_list associated with word (creating a new entry if one did not previously exist for word).

    This can be accomplished using the following algorithm:

    1. For each entry in count_list, do the following:
      1. If the first element of entry is the same as word, then do the following:
        1. Increase the second element of entry by 1
        2. Return count_list.
    2. Create a new 2-element array whose first element is word and whose second element is 1.
    3. Append that two-element array onto count_list as count_list's new last element.
    4. Return count_list.

    Example usage:

    >> list = []
    => []
    >> update_count(list,"one")
    => [["one", 1]]
    >> update_count(list,"the")
    => [["one", 1], ["the", 1]]
    >> update_count(list,"the")
    => [["one", 1], ["the", 2]]
    
    >> load "word_count2.rb"
    => true
    >> text="One of the first big users of the telegraph was the Associated Press: one of the original 'wire services.'"
    => "One of the first big users of the telegraph was the Associated Press: one of the original 'wire services.'"
    >> word_count(text)
    => [["one", 2], ["of", 3], ["the", 4], ["first", 1], ["big", 1], ["users", 1], ["telegraph", 1], ["was", 1], ["associated", 1], ["press", 1], ["original", 1], ["wire", 1], ["services", 1]]
    
  3. Recall that a graph of \(n\) nodes can be represented as an \(n \times n\) matrix where the value at row \(i\) column \(j\) gives the cost of going directly from node \(i\) to node \(j\) in the graph.

    The following \(O(n^3)\) algorithm computes the shortest path from start node \(s\) of a graph to all other nodes:

    1. Set best_cost equal to a clone of row \(s\) in the graph.
    2. Set \(n\) equal to the number of rows in the graph.
    3. Repeat the following \(n\) times:
      1. For \(i\) in the range 0 to \(n-1\), do the following:
        1. For \(j\) in the range 0 to \(n-1\), do the following:
          1. Set cost_to_j_via_i equal to best_cost[i] + the cost to go directly from node \(i\) to node \(j\) in the graph.
          2. If cost_to_j_via_i is less than best_cost[j] then set best_cost[j] = cost_to_j_via_i.
    4. Return the best_cost array, which will now contain the minimum cost to get from \(s\) to each location.

    Write the following two functions:

    1. [2 points] Write a function shortest_path(s, graph) (in shortest_path.rb) that takes a starting node number s and a 2-dimensional array graph of costs and returns an array with the costs of the shortest path from node s to all nodes in the graph, using the algorithm above as your guide.

      Example usage (using the graph from problem 8 of HW5):

      >> shortest_path(0, [[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]])
      => [0, 3, 5, 6, 2]
      >> shortest_path(3, [[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]])
      => [6, 3, 7, 0, 4]
      
    2. [1 point] Write a function test_sp(start) (in shortest_path.rb) to test your shortest path algorithm. The function should create a 2D matrix for the graph below and then call your shortest_path function, returning its answer. (Corrections in red.)

      NOTE: If there is no link from node i to node j in the graph, you should put a large number (e.g. 9999) into the matrix in that position. Do not put 0 as we did in class or the algorithm will not work. You can put 0's down the main diagonal since the cost to go from node i to itself is 0. (In case the graph has really large costs, 9999 might not be high enough. One way around this is to use +infinity for the non-existing edges. In Ruby, +infinity is represented by the expression 1.0/0 and is stored as a special floating point number.)

      Example usage:

      >> test_sp(0)  
      => [0, 10, 14, 8, 7, 12, 15]
      >> test_sp(3)
      => [8, 7, 6, 0, 9, 4, 7]
      >> test_sp(5)
      => [12, 11, 7, 4, 13, 0, 3]
      
  4. [2 ponts] Matrices are used extensively in a wide variety of computational applications, including scientific simulations, processing genetic information, optimizing the risk and return of financial portfolios, and building recommender systems.

    For example, a system that recommends movies, might attempt to maintain, for each user (e.g., Alice, Bob, and Charlie), their preference of movies of different genres (e.g., comedy, drama, sci-fi, and thriller). (In general, other movie features besides genre can be used, but we'll stick with genres.) If Alice really likes comedies and sci-fi movies, Bob likes dramas and thrillers but not sci-fi, and Charlie isn't enthusiastic about anything and despises comedies, this might be encoded in the following matrix: comedydramasci-fithrillerAliceBobCharlie10.50.950.50.50.920.020.9600.50.50.5 Here, each row representing an individual, each column representing a genre, and the values of the matrix representing how well, on a scale from 0 to 1, that that individual tends to like movies of that genre.

    This matrix could then be multiplied by vectors representing to what extent particular movies reflect different genres. The result of this multiplication can then be used to predict whether each individual would like a particular movie. So, when the movies The Thing (Sci-Fi, Thriller), The Big Year (Comedy) come out, their genres might be encoded using the vectors: Thingcomedydramasci-fithriller000.50.5 Big Yearcomedydramasci-fithriller1000 Here, each row represents a genre. The values in each vector add up to 1 and are distributed according to the extent that each genre is represented in the movie. (More generally, one could use a two-dimensional matrix—instead of the one-dimensional genre vector—to represent the genres of several movies.)

    Given the preference matrix and per-movie genre vectors, the system might perform the multiplication: \[\begin{bmatrix} 1 & 0.5 & 0.95 & 0.5\\ 0.5 & 0.92 & 0.02 & 0.96\\ 0 & 0.5 & 0.5 & 0.5\\ \end{bmatrix}\; \begin{bmatrix} 0 \\ 0 \\ 0.5 \\ 0.5 \\ \end{bmatrix} = \begin{bmatrix} 0.725 \\ 0.49 \\ 0.5 \\ \end{bmatrix} \;\begin{array}{l}\text{Alice}\\\text{Bob}\\\text{Charlie}\end{array} \] This can be used to predict that Alice will probably like The Thing.

    Furthermore, the system can preform the multiplication \[\begin{bmatrix} 1 & 0.5 & 0.95 & 0.5\\ 0.5 & 0.92 & 0.02 & 0.96\\ 0 & 0.5 & 0.5 & 0.5\\ \end{bmatrix}\; \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \\ \end{bmatrix} = \begin{bmatrix} 1.0\\ 0.5\\ 0.0\\ \end{bmatrix} \;\begin{array}{l}\text{Alice}\\\text{Bob}\\\text{Charlie}\end{array} \] This can be used to predict that Alice will most likely like The Big Year, but Charlie, on the other hand, will probably not like The Big Year.

    Define a Ruby method matrix_vector_multiply(mat,vec) (in matrix_vector_multiply.rb) that multiplies a matrix by a vector (which is a special case of matrix multiplication), where mat is a three by four matrix (represented by a rectangular, two-dimensional Ruby array), and vec is a four element vector (represented by a one-dimensional Ruby array). The function matrix_vector_multiply should be return a one-dimensional Ruby array holding the product of the multiplication.

    The multiplication of a 3x4 matrix with a 4 element vector can be implemented using the following algorithm:

    1. Set result to be a new, empty array
    2. For each i in 0 through 2, do the following:
      1. Set sum to 0
      2. For each j in 0 through 3, do the following:
        1. Multiply the element at row i and column j of mat with the element at index j in vec
        2. Add the result from the previous step to sum.
      3. Set the element at index i in result to sum
    3. Return result.

    Example usage:

    >> matrix_vector_multiply([[1, 0.5, 0.95, 0.5], [0.5, 0.92, 0.02, 0.96], [0, 0.5, 0.5, 0.5]], [0, 0, 0.5, 0.5])
    => [0.725, 0.49, 0.5]
    >> matrix_vector_multiply([[1, 0.5, 0.95, 0.5], [0.5, 0.92, 0.02, 0.96], [0, 0.5, 0.5, 0.5]], [1, 0, 0, 0])
    => [1.0, 0.5, 0.0]
    >> matrix_vector_multiply([[14, 9, 3, 5], [2, 11, 15, 2], [0, 12, 17, 3]], [12, 9, 8, 11])
    => [328, 265, 277]
    >> matrix_vector_multiply([[14, 9, 3, 5], [2, 11, 15, 2], [0, 12, 17, 3]], [25, 9, 5, 7])
    => [481, 238, 214]
    

    Submission

    You should now have a pa6 directory that contains the required files, convert.rb, word_count2.rb, update-count.rb, shortest_path.rb, and matrix_vector_multiply.rb, each—in turn—containing the corresponding function(s). Zip up your directory and upload it using the handin system. (The handin system will accept submissions beginning on Friday until the deadline Tuesday night.)