Basic Skills Drill: Implementing Algorithms
15-112 Lab #3 - due Friday, June 6, 2014 at 11:59pm

Overview

For this assignment, you will create Python source files containing a 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 source file as the primary function they help.

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 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's prime factorization 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 array.

  4. While dividend is not 1, do the following:

    1. If possible_factor is a divisor of dividend:

      1. Append possible_factor onto factors.
      2. Set dividend to (dividend / possible_factor).

      Otherwise, (if you did not execute the substeps 1 and 2, above):

      1. Add 1 to possible_factor.
  5. 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 Python function called factor(n) (stored in factor.py). Your function should be able to be used as follows:

print factor(60)
=> [2, 2, 3, 5]
print factor(45)
=> [3, 3, 5]
print factor(35)
=> [5, 7]
print factor(13)
=> [13]

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.

  1. For each integer i from 1 through height, inclusive, do the following:

    1. Print (height-i) spaces.

    2. Print (2i - 1) asterisks ("*").

    3. Print a new line.

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.

Create a function triangle(height) (in triangle.py) that implements this algorithm. Your function should be able to be used as follow:

triangle(3)
  *
 ***
*****
triangle(5)
    *
   ***
  *****
 *******
*********

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 = p(1+r)t

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 = p*(1+r)t - 2p). 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:

  1. Set low to 0.
  2. Set high to 10,000.
  3. Set guess to 5,000.
  4. Set guess_error to 5,000.
  5. While guess_error is greater than 0.001, do the following:

    1. If p*(1+rate)guess - 2p is at least 0:
      • Set high to the value of guess.
      Otherwise, (if you did not just set high)
      • Set low to the value of guess
    2. Set guess to (high + low) / 2

    3. Set guess_error to (high - low) / 2

  6. Return guess.

Write a function called doubling(rate) in doubling.py 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:

print doubling(0.1)
=> 7.272540897341713
print doubling(0.05)
=> 14.206699082890463
print doubling(0.01)
=> 69.66071689357483

Important Notes

Factorial

The factorial of n, written n! is 1 * 2 * ... * n. Its computation is very similar to that of the sum of the first n non-negative integers. Recall, that this sum can be computed using the following function:

def sum(n)
  x = 0
  for i in 1..n do
    x = x + i
  end
  return x
end

In factorial.py, 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:

print factorial(4)
=> 24
print factorial(0)
=> 1

Pascal's Triangle

The first n rows of a slightly rotated version of Pascal's Triangle can be computed using the following algorithm:

  1. For each integer i from 0 through n-1, inclusive, do the following:

    1. For each integer j from 0 through i, inclusive, do the following:

      1. Set val to be i! / (j! * ((i-j)!)).
      2. Print enough spaces to align the value stored in val.
      3. Print val.
    2. Print a new line.

In pascal.py, 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 above to get the values of i!, j!, and (i-j)!.

Example:

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

Number of Occurrences

In the file num_occurrences.py, define a 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:

print num_occurrences(["a", "b", "a", "b", "c", "b", "d", "e"], "b")
=> 3