15110 SUMMER SESSION TWO - 2014

Programming Assignment 4 - due Thursday, July 10 by 9:00AM

Overview

For this assignment, you will create a Python source file containing a Python 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 Python 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] 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 × 2 × 3 × 5, and the integers 2, 3, and 5 are all prime. This is called the number's prime factorization, and it is unique for each integer number of at least 2.

An integer n's prime factorization (n ≥ 2) can be calculated using the following algorithm.
1. Set dividend equal to n.
2. Set possible_factor equal to 2.
3. Set factors to be an empty list.
4. While dividend is not 1, do the following:
  1. If possible_factor is a divisor of dividend:
    1. Append possible_factor onto the array factors.
    2. Set dividend equal to dividend divided by possible_factor (using integer division).
    Otherwise, (if you did not execute the substeps 1 and 2, above):
    1. Add 1 to possible_factor.
5. Return the list factors as your result.
Implement this algorithm as a Python function called factor(n) (stored in factor.py). 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] 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₀, x₁, ..., x_n-1 is equal to product of all of these values, raised to the 1/n. 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 1/n.

In the file geo_mean.py define the function geo_mean(numlist) that takes a non-empty list of non-negative numbers called numlist and returns the geometric mean of the numbers in numlist.

Use the following algorithm:
1. Set n to the length of the number list.
2. Set product to 1. (Think about why 1 and not 0.)
3. For each element x in numlist, do the following:
  1. Multiply product by x and store the result in product.
4. Set result equal to product raised to the power 1/n.
5. Return result.
Example:
```
> python3 -i geo_mean.py
>>> geo_mean([1.00, 1.10, 1.19, 1.20])
1.1195157893980163
>>> geo_mean([2, 4, 8])
3.9999999999999996
>>> geo_mean([6, 24])
12.0
```
[2 points] Index of Maximum Element.
In max_index.py, define a Python function max_index(element_list) that returns the index of the largest element in a non-empty element_list of elements. If the largest element occurs more than once in element_list, max_index should return the index of the first occurrence.
Start with the algorithm presented in class and make an adjustment to it so that when you find a new maximum, you also keep track of its location (index). Then when the entire list is examined, return the index of the maximum instead of the maximum itself. Be sure to test your function on more cases than the two shown below.
Example:
```
> python -i max_index.py
>>> max_index([3, 5, -10, 7, 6])
3
>>> max_index(["z", "x", "y", "z", "x", "abcd", "xyz"])
0
```
Selection Sort

There are many algorithms for sorting the elements of a list. One of these is Selection Sort.
1. [2 point] In the file selection_sort.py, create a helper function called min_index_after(element_list,start_index), which returns the index of the minimum element in element_list that is located at or after the index start_index. Do NOT use the built-in min function. (HINT: Modify your answer to the previous problem.)
  
  Example:
```
python3 -i selection_sort.py
>>> 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 selection_sort.py, define a Python function selection_sort(element_list) that modifies element_list by rearranging its elements so they are sorted in "ascending order" (from smallest to largest) using the Selection Sort algorithm below. Do NOT use the built-in sort function.
  This function should be implement the selection sort algorithm using the steps below. Be sure to test your function on more than just the two cases shown.
  1. For each integer i from 0 through two less than the length of element_list, do the following:
    1. Set min_index equal to the index of the minimum element in element_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 element_list.
    3. Set the element at index i in element_list to the element at index min_index in element_list.
    4. Set the element at index min_index in element_list to tmp.
  2. Return None.
  Example:
```
> python -i selection_sort.py
>>> a1 = [1, -2, 3, 0, -4, -2, 7]
[1, -2, 3, 0, -4, -2, 7]
>>> selection_sort(a1)
>>> a1
[-4, -2, -2, 0, 1, 3, 7]
>>> a2 = [3, 5, -10, 7, 6, 7]
[3, 5, -10, 7, 6, 7]
>>> selection_sort(a2)
>>> a2
[-10, 3, 5, 6, 7, 7]
```

Submission

You should now have a pa4 directory. containing:

factor.py
geo_mean.py
max_index.py
selection_sort.py (with the functions min_index_after and selection_sort)

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