15110 SUMMER SESSION ONE - 2013

Programming Assignment 4 - due Thursday, May 30 by 10:30AM using ELECTRONIC HANDIN

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(s) for each problem 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. (More information can be found in the instructions for Programming Assignment 2.)

The Algorithms

[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.
1. Set count to 0.
2. For each element x in list, do the following:
  1. If x is equal to key, do the following:
    1. Add 1 to count.
3. Return count.
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 numbers called list and returns the geometric mean of the numbers in list.

Use the following algorithm:
1. Set n to the length of list.
2. Set product to 1.
3. For each element x in list, do the following:
  1. Multiply product by x and store the result in product.
4. Set result equal to product raised to the power \(\frac{1}{\textit{n}}\).
5. Return result.
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:
1. Set i to 0.
2. Set max_so_far to the element at index i in list.
3. Set max_so_far_index to i.
4. While i is less than the length of list, do the following:
  1. Set x to the element at index i in list.
  2. If x is greater than max_so_far, then do the following:
    1. Set max_so_far to x
    2. Set max_so_far_index to i
  3. Add 1 to i.
5. Return max_so_far_index.
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.
1. [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. (HINT: Modify your answer to the previous problem.)
  
  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. [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:
  1. For each integer i from 0 through two less than the length of list, do the following:
    1. Set min_index equal to the index of the minimum element in list that is located at or after index i. (HINT: Call the function you wrote for part a.)
    2. Set tmp equal to the element at index i in list
    3. Set the element at index i in list to the element at index min_index in list.
    4. Set the element at index min_index in list to tmp.
  2. Return nil.
  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]
```

Submission

You should now have a pa4 directory. containing:

num_occurrences.rb
geo_mean.rb
max_index.rb
sort.rb (with min_index_after and sort!)

Zip up your directory and upload it using the handin system.