Note: You are responsible for protecting your solutions to these problems from being seen by other students both physically (e.g., by looking over your shoulder) and electronically. In particular, since the lab machines use the Andrew File System to share files worldwide, you need to be careful that you do not put files in a place that is publicly accessible.
If you are doing the assignment on the Gates-Hillman Cluster machines we use in lab or on unix.andrew.cmu.edu, our recommendation is that you create a pa4 directory under ~/private/15110 for this assignment. That is, the new directory pa4 is inside a directory called 15110, which is inside the directory called private, which is inside your home directory. (Every new andrew account is set up with a private subdirectory within the account's home directory that only that account can access.) Please refer to Setting up Directories for information about managing your directories.
For this assignment, you will create a Ruby source file (that is, a text file containing Ruby code) for each of the problems below. You should store all of these files in a folder named pa4, which you will zip up and submit.
As you will discover this semester, computer programs are rarely correct when they are first written. They often have bugs. In addition to writing the code, you should test your code on multiple inputs, for which you independently know the correct output (e.g., by plugging the inputs into a calculator).
In this assignment, for each of the problems described below, you will create a Ruby source file containing Ruby functions implementing your solution. If you find it useful, you may define additional helper functions that your primary function calls to solve a sub-problem. Definitions for these helper functions should be included in the same Ruby source file as the primary function. You should store your source files in a folder named pa4.
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.
[1 point] Number of Occurences.
In the file occurrences.rb, define a Ruby function occurrences(list, key) that takes an array list and an object key as parameters. It should return the number of elements in list that are equal to key.
Example:
>> load "occurrences.rb" => true >> occurrences(["a","b","a","b","c","b","d","e"],"b") => 3
[1 point] Counting.
In the file num_smaller.rb, define a Ruby funcion num_smaller(list, item) that takes an integer array list of size $1$ or larger and an integer item as parameters. It should return the number of elements in list that are strictly less than item.
Example:
>> load "num_smaller.rb" => true >> num_smaller([3, 8, 12, 30, 7, 32, 10], 8) => 2
[2 points] (corrected) Second Smallest Element.
In second_smallest.rb, define a Ruby function second_smallest(list) that takes an array of integers and returns the second smallest integer in the array list . In the case that the smallest integer occurs more than once, it would then be considered the smallest and second smallest integer. For example, the list [1,1,2,3] has 1 as the smallest and second smallest integer. Use the following algorithm:
In Ruby, you can use the max and min functions to find, respectively, the maximum and the minimum of two integers.
Example:
>> max(3, -2) => 3 >> min(3, -2) => -2 >> load "second_smallest.rb" => true >> second_smallest([3, -2, 10, -1, 5]) => -1 >> second_smallest([-2, 1, 1, -3, 5]) => -2 >> second_smallest([1,1,2,3]) => 1
[2 points] Harmonic Mean
In mathematics, the harmonic mean is one of several kinds of averages. When averages for rates is desired, this type of average is commonly used. The harmonic mean of a list of $n$ numbers $x_0, x_1, \dots x_{n-1}$ is equal to $$ \left(\frac{1}{n}\sum\limits_{i=0}^{n-1}x_i^{-1}\right)^{-1} = \frac{n}{\frac{1}{x_0}+\frac{1}{x_1}+ \dots +\frac{1}{x_{n-1}}}.$$
In the file harmonic_mean.rb define the function harmonic_mean(list) that takes an array of positive integers called list and returns the harmonic mean of these integers in list.
Example:
>> load "harmonic_mean.rb" => true >> harmonic_mean([40,60]) => 48.0 >> harmonic_mean([1,2,4]) => 1.71428571428571
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. This algorithm works by moving an index left to right through the array and at each step, scanning everything to the right of the index to select the most extreme value, which is then swapped with the value currently at the index.
[2 point] In the file sort.rb, create a helper function called max_index_after(list,start_index), which returns the index of the maximum element in list that is located at or after the index start_index. If there are more than one such element the function returns the index of the first one.
Example:
>> load "sort.rb" => true >> max_index_after(["b", "d", "c"], 0) => 1 >> max_index_after(["b", "d", "c"], 1) => 1 >> max_index_after(["b", "d", "c"], 2) => 2
[2 points] In sort.rb, define a Ruby function dsort!(list) that modifies list by rearranging its elements so they are sorted in "descending order" (from largest to smallest). (The "!" in the name of a function is a Ruby convention indicating that the function modifies its parameters.)
This function should implement the selection sort algorithm using the following steps:
Example:
>> load "sort.rb" => true >> a1 = [3, -2, 1, 0, -4, -5, 7] => [3, -2, 1, 0, -4, -5, 7] >> dsort!(a1) => [7, 3, 1, 0, -2, -4, -5] >> a1 => [7, 3, 1, 0, -2, -4, -5] >> a2 = [4, 5, -10, 9, 6, 9] => [4, 5, -10, 9, 6, 9] >> dsort!(a2) => [9, 9, 6, 5, 4, -10] >> a2 => [9, 9, 6, 5, 4, -10]
You should now have a pa4 directory that contains the files occurrences.rb, num_smaller.rb, second_smallest.rb, harmonic_mean.rb, and sort.rb each containing the corresponding function(s). Zip up your directory and hand it in.