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

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

- Set
*result*equal to the empty string. - Repeat the following 8 times:
- If
*n*is odd, then attach "1" to the beginning of*result*.

Otherwise, attach "0" to the beginning of*result*. - Divide
*n*by 2, ignoring any remainder.

- If
- 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"

- Set
[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:

- For each
*entry*in*count_list*, do the following:- If the first element of
*entry*is the same as*word*, then do the following:- Increase the second element of
*entry*by 1 - Return
*count_list*.

- Increase the second element of

- If the first element of
- Create a new 2-element array whose first element is
*word*and whose second element is 1. - Append that two-element array onto
*count_list*as*count_list*'s new last element. - 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]]

- For each
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:

- Set
*best_cost*equal to a clone of row \(s\) in the graph. - Set \(n\) equal to the number of rows in the graph.
- Repeat the following \(n\) times:
- For \(i\) in the range 0 to \(n-1\), do the following:
- For \(j\) in the range 0 to \(n-1\), do the following:
- 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. - If
*cost_to_j_via_i*is less than*best_cost[j]*then set*best_cost[j] = cost_to_j_via_i*.

- Set

- For \(j\) in the range 0 to \(n-1\), do the following:

- For \(i\) in the range 0 to \(n-1\), do the following:
- Return the
*best_cost*array, which will now contain the minimum cost to get from \(s\) to each location.

Write the following two functions:

[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]

[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]

- Set
[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: $$\begin{array}{cc}\hfill \hfill & \hfill \begin{array}{cccc}\hfill \text{comedy}\hfill & \hfill \text{drama}\hfill & \hfill \text{sci-fi}\hfill & \hfill \text{thriller}\hfill \end{array}\hfill \\ \hfill \begin{array}{c}\hfill \text{Alice}\hfill \\ \hfill \text{Bob}\hfill \\ \hfill \text{Charlie}\hfill \end{array}\hfill & \hfill \left[\begin{array}{cccc}\hfill 1\hfill & \hfill 0.5\hfill & \hfill 0.95\hfill & \hfill 0.5\hfill \\ \hfill 0.5\hfill & \hfill 0.92\hfill & \hfill 0.02\hfill & \hfill 0.96\hfill \\ \hfill 0\hfill & \hfill 0.5\hfill & \hfill 0.5\hfill & \hfill 0.5\hfill \end{array}\right]\hfill \end{array}$$ 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: $$\begin{array}{cc}\hfill \hfill & \hfill \begin{array}{c}\hfill \text{Thing}\hfill \end{array}\hfill \\ \hfill \begin{array}{c}\hfill \text{comedy}\hfill \\ \hfill \text{drama}\hfill \\ \hfill \text{sci-fi}\hfill \\ \hfill \text{thriller}\hfill \end{array}\hfill & \hfill \left[\begin{array}{c}\hfill 0\hfill \\ \hfill 0\hfill \\ \hfill 0.5\hfill \\ \hfill 0.5\hfill \end{array}\right]\hfill \end{array}$$ $$\begin{array}{cc}\hfill \hfill & \hfill \begin{array}{c}\hfill \text{Big Year}\hfill \end{array}\hfill \\ \hfill \begin{array}{c}\hfill \text{comedy}\hfill \\ \hfill \text{drama}\hfill \\ \hfill \text{sci-fi}\hfill \\ \hfill \text{thriller}\hfill \end{array}\hfill & \hfill \left[\begin{array}{c}\hfill 1\hfill \\ \hfill 0\hfill \\ \hfill 0\hfill \\ \hfill 0\hfill \end{array}\right]\hfill \end{array}$$ 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:

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

- Multiply the element at row
- Set the element at index
*i*in*result*to*sum*

- Set
- 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.)- Set