For this assignment, you will create a Ruby source file containing a ruby function implementing each of the algorithms 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.
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.
[2 points] Prime Factorization.
Every integer greater than 1 can be expressed as the product of one or more prime numbers (which may be repeated). For example, \(60 = 2 \times 2 \times 3 \times 5\), and two, three, and five are all prime. This is called the number's prime factorization, and it is unique for each integer number of at least 2.
A number \(n\)'s prime factorization can be calculated using the following algorithm.
Set dividend equal to \(n\).
Set possible_factor equal to 2.
Set factors to be an empty array.
While dividend is not 1, do the following:
If possible_factor is a divisor of dividend:
Otherwise, (if you did not execute the substeps 1 and 2, above):
Return factors.
Hint: To determine if a number is a divisor of another number, think about using the modulo operator.
Implement this algorithm as a Ruby function called factor(n) (stored in factor.rb). Your function should be able to be used as follows:
>> factor(60) => [2, 2, 3, 5] >> factor(45) => [3, 3, 5] >> factor(35) => [5, 7] >> factor(13) => [13]
[2 points] Printing an ASCII-art Triangle.
By printing out different characters at different locations, it is possible create images. This is sometimes called ASCII art, and works best in a terminal that uses a fixed-width font. Regular shapes, such as the square shown below, are easy to create—even at different sizes—algorithmically.
*
***
*****
*******
*********
***********
This triangle can be created using the following algorithm, which requires the triangle's height (that is, the number of lines in the triangle). It assumes that height is non-negative.
For each integer \(i\) from 1 through \(\textit{height}\), inclusive, do the following:
Print \(\textit{height}-i\) spaces.
Print \(2i - 1\) asterisks ("*").
Print the new line character ("\n").
Hint: You will need loops here! In fact, you will probably need a loop inside of a loop for part of your solution. If you use a loop inside of another loop, please, choose a different variable for each loop (e.g., if the outer loop uses "i", the inner loop can use "j").
Create a Ruby function triangle(height) (in triangle.rb) that implements this algorithm. Your function should be able to be used as follow:
>> triangle(3)
*
***
*****
=> nil
>> triangle(5)
*
***
*****
*******
*********
=> nil
[2 points] Doubling Time.
For an account with a deposit of \(P\) dollars that earns interest compounded continuously at an annual rate of \(r\) for \(t\) years, the final amount \(A\) of the account is given by the formula:
\[A = Pe^{rt}\]The bisection method can be used to approximate how much time would be required for an initial deposit to double (i.e., finding a value of \(t\) for which \(0 = e^{rt} - 2\)). It works by maintaining a lower and upper bound for a range in which the desired value of \(t\) is known to exist. In each iteration, it finds the half-way point of that range and determines whether the desired value of \(t\) is above or below that half-way point. The algorithm stops when the range is smaller than some threshold.
The bisection method can be realized using the following algorithm, which is parameterized by rate:
While guess_error is greater than 0.001, do the following:
Set guess to \(\frac{\textit{high} + \textit{low}}{2}.\)
Set guess_error to \(\frac{\textit{high} - \textit{low}}{2}.\)
Return guess.
Write a Ruby function called doubling(rate) in doubling.rb that implements this algorithm giving the result as shown below. You should insure that all divisions are floating point division. You may assume that the interest rate will be at least 0.00001.
Example:
>> load "doubling.rb" => true >> doubling(0.1) => 6.93127512931824 >> doubling(0.05) => 13.8632953166962 >> doubling(0.01) => 69.3149864673615
Pascal's Triangle
[2 points] Factorial.
The factorial of \(n\), written \(n!\) is \(1 \times 2 \times \ldots \times n\). Its computation is very similar to that of the sum of the first n non-negative integers, \(\sum_{i=0}^n i\).
Recall, that this sum can be computed using the following Ruby function:
def sum(n)
x = 0
for i in 1..n do
x = x + i
end
return x
end
In factorial.rb, define a function factorial(n) that computes \(n!\) for any non-negative integer \(n\). It should follow the pattern of the sum function above. (Hint: think about how factorial(0) and sum(0) differ and how the additional computation being performed for each larger \(n\) differs.)
Example:
>> factorial(4) => 24 >> factorial(0) => 1[2 points] The Triangle.
The first \(n\) rows of a slightly rotated version of Pascal's Triangle can be computed using the following algorithm:
For each integer \(i\) from \(0\) through \(n-1\), inclusive, do the following:
For each integer \(j\) from \(0\) through \(i\), inclusive, do the following:
Print a new line character ("\n").
Return nil.
In pascal.rb, define a function pascal(n) that implements this algorithm to produce \(n\) rows of Pascal's Triangle in the format shown in the example below. You will need to figure out how to accomplish step I.A.2 so that it right aligns each column; you can assume that the largest value in the triangle is less than 1000. You should make calls to your factorial function from part (a) to get the values of \(i!\), \(j!\), and \((i-j)!\).
Example:
>> load "factorial.rb" => true >> load "pascal.rb" => true >> pascal(10) 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 => nil
[2 points] Number of Occurrences.
In the file num_occurrences.rb, define a Ruby function num_occurrences(list, key) that takes an array list and an object key as parameters. It should return the number of elements in in list that are equal to key.
Example:
>> load "num_occurrences.rb" => true >> num_occurrences(["a", "b", "a", "b", "c", "b", "d", "e"], "b") => 3
[2 points] Geometric Mean.
The geometric mean is kind of "average" used to find a representative value of a set of numbers, especially when those numbers are multiplied together. (For example, the geometric mean might be used to combine the rate of return your investment portfolio had in 2009, 2010, 2011 to find an annualized rate of return for the three year period.) The geometric mean of a list of \(n\) numbers \(x_0, x_1, \ldots x_{n-1}\) is equal to \[\left(\prod\limits_{i=0}^{n-1} x_i\right)^\frac{1}{n}.\] (The \(\prod\) notation is similar to the \(\sum\) notation, except that it is used to indicate a product obtained by multiplication rather than a summation obtained through addition.) In other words, the geometric mean of a list is computed by multiplying all of the elements in an \(n\)-element list to obtain a product of all of the numbers in the list and then raising that product to the power \(\frac{1}{n}\).
In the file geo_mean.rb define the function geo_mean(list) that takes an array of non-negative [correction] numbers called list and returns the geometric mean of the numbers in list.
Use the following algorithm:
Example:
>> load "geo_mean.rb" => true >> geo_mean([1.00, 1.10, 1.19, 1.20]) => 1.11951578939802 >> geo_mean([2, 4, 8]) => 4.0
[2 points] Index of Maximum Element.
In max_index.rb, define a Ruby function max_index(list) that returns the index of the largest element in list. If the largest element occurs more than once in list, max_index should return the index of the first occurrence.
Use the following algorithm:
Example:
>> load "max_index.rb" => true >> max_index([3, 5, -10, 7, 6]) => 3 >> max_index(["z", "x", "y", "z", "x"]) => 0
Selection Sort
In addition to Insertion Sort, there are many other algorithms for sorting the elements of an array. One of these is Selection Sort.
[2 point] In the file sort.rb, create a helper function called min_index_after(list,start_index), which returns the index of the minimum element in list that is located at or after the index start_index.
Example:
>> load "sort.rb" => true >> min_index_after(["b", "d", "c"], 0) => 0 >> min_index_after(["b", "d", "c"], 1) => 2 >> min_index_after(["b", "d", "c"], 2) => 2
[2 points] In sort.rb, define a Ruby function sort!(list) that modifies list by rearranging its elements so they are sorted in "ascending order" (from smallest to largest). (The "!" in the name of a function is a Ruby convention indicating that the function modifies its parameters.)
This function should be implement the selection sort algorithm using the following steps:
Example:
>> load "sort.rb" => true >> a1 = [1, -2, 3, 0, -4, -2, 7] => [1, -2, 3, 0, -4, -2, 7] >> sort!(a1) => nil >> a1 => [-4, -2, -2, 0, 1, 3, 7] >> a2 = [3, 5, -10, 7, 6, 7] => [3, 5, -10, 7, 6, 7] >> sort!(a2) => nil >> a2 => [-10, 3, 5, 6, 7, 7]