**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.

Set

dividendequal ton.Set

possible_factorequal to 2.Set

factorsto be an empty array.While

dividendis not 1, do the following:

If

possible_factoris a divisor ofdividend:

- Append
possible_factorontofactors.- Set
dividendto(dividend / possible_factor).Otherwise, (if you did not execute the substeps 1 and 2, above):

- Add 1 to
possible_factor.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 infactor.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 thatheightis non-negative.

For each integer

ifrom 1 throughheight, inclusive, do the following:

Print (

height-i) spaces.Print (2

i- 1) asterisks ("*").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)(intriangle.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

pdollars that earns interest compounded continuously at an annual rate ofrfortyears, the final amountaof 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

tfor which0 = p*(1+r)). It works by maintaining a lower and upper bound for a range in which the desired value of^{t}- 2ptis known to exist. In each iteration, it finds the half-way point of that range and determines whether the desired value oftis 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:

- Set
lowto 0.- Set
highto 10,000.- Set
guessto 5,000.- Set
guess_errorto 5,000.While

guess_erroris greater than 0.001, do the following:

- If
p*(1+rate)is at least 0:^{guess}- 2pOtherwise, (if you did not just set

- Set
highto the value ofguess.high)

- Set
lowto the value ofguessSet

guessto (high + low) / 2Set

guess_errorto(high - low) / 2Return

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

- Note that $1 doubles as fast as $10 or $30,000. Holding the growth/interest rate constant, the amount of time it take money to double is the same, regardless of the initial amount. As a result, $1 is an easy number for computation.
- In addition to integers, which are expressed as literals in Python as simple numbers, and can be cast using int(), there are
longs, which can store bigger integers. They are expressed as literals just as are integers -- but with an "L" suffix, e.g. 123L, 10L, etc. And, they can be cast using long().

**Factorial**

The factorial of

n, writtenn!is1 * 2 * ... * n. Its computation is very similar to that of the sum of the firstnnon-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 endIn

factorial.py, define a functionfactorial(n)that computesn!for any non-negative integern. It should follow the pattern of thesumfunction above.

Hint:Think about howfactorial(0)andsum(0)differ and how the additional computation being performed for each largerndiffers.Example:

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

**Pascal's Triangle**

The first

nrows of a slightly rotated version of Pascal's Triangle can be computed using the following algorithm:

For each integer

ifrom0throughn-1, inclusive, do the following:

For each integer

jfrom0throughi, inclusive, do the following:

- Set
valto bei! / (j! * ((i-j)!)).- Print enough spaces to align the value stored in
val.val.Print a new line.

In

pascal.py, define a functionpascal(n)that implements this algorithm to producenrows 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 yourfactorialfunction from above to get the values ofi!,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 functionnum_occurrences(list, key)that takes an arraylistand an objectkeyas parameters. It should return the number of elements in inlistthat are equal tokey.

- Set
countto 0.- For each element
xinlist, do the following:

- If
xis equal tokey, do the following:

- Add 1 to
count.- Return
count.Example:

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