15110 Fall 2012 [Touretzky/Kaynar]

Programming Assignment 3 - due Tuesday, September 18

Overview

For this assignment, you will create a Ruby source file containing a ruby function implementing each of the algorithms described below. You should store all of these files in a folder named pa3.

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.

The Algorithms

1. [2 points] Greatest Common Divisor.

   In mathematics, the greatest common divisor (gcd) of two or more non-zero integers is the largest positive integer that divides the numbers without a remainder. For example gcd of 24 and 36 is 12.

   Below is a Euclidian algorithm for calcutating gcd of two positive integers a and b is as follows

   1. While b is not equal to 0, do the following:
      1. Set temp equal to b
      2. Set b equal to a modulo b
      3. Set a equal to temp
   2. Return a as the gcd

   Implement this algorithm as a Ruby function called gcd(a,b) (stored in gcd.rb). Your function should be able to be used as follows:

   >> gcd(12,36)
   => 12
   >> gcd(30,75)
   => 15
   

2. [2 points] ASCII-art. (Typos corrected)

   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.

   XXXXX
   XX-XX
   XX-XX
   XX-XX
   XXXXX
   

   The sides of this square can be created using the following algorithm, which requires the square's size (that is, the number of columns of characters wide and lines of text height the square is). It assumes that size is at least five.

   First, print out size copies of the character "X" on one line. Then, for the next \(\textit{size}-2\) lines, print out two copies of "X", print out \(\textit{size}-4\) hyphens, and then two copies of "X". Finally, for the last line print out size copies of the character "X" again.

   Hint: 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 (e.g., if the outer loop uses "i", the inner loop can use "j").

   Create a Ruby function make_square(size) (in make_square.rb) that implements this algorithm. Your function should be able to be used as follows:

   >> make_square(5)
   XXXXX
   XX-XX
   XX-XX
   XX-XX
   XXXXX
   => nil
   >> make_square(9)
   XXXXXXXXX
   XX-----XX
   XX-----XX
   XX-----XX
   XX-----XX
   XX-----XX
   XX-----XX
   XX-----XX
   XXXXXXXXX
   => nil
   

3. (4 points) Pascal's Triangle

   If you throw a fair coin n times, what are the odds of getting exactly i heads and n-i tails? This is easily calculated using Pascal's triangle. Some examples:
   1. If n is 0, there is only one possible outcome: nothing happens. We'll write this as [1].

   2. If n is 1, the are two possible outcomes: one head or no heads. We'll write this as [1,1]. Their probabilities are each 1/2.

   3. If n is 2, there are four possible toin coss sequences, which we can abbreviate as HH, HT, TH, and TT. But HT and TH both include only one head. So there are only three distinct outcomes, which we'll write as [1, 2, 1]. From this we can see that there is a 1/4 chance of two heads, a 2/4 chance of one head, and a 1/4 chance of no heads (all tails).

   4. If n is 3, there are eight possible toin coss sequences, which we can abbreviate as HHH, HHT, HTH, HTT, THH, THT, TTH, and TTT. There are four distinct outcomes, which we'll write as [1, 3, 3, 1]. Notice that these numbers sum to 8. So there is a 1/8 chance of three heads, a 3/8 chance of two heads (in any order), a 3/8 chance of one head (in any order), and a 1/8 chance of no heads (all tails).

   Let's analyze and then automate this scheme:
   1. (1 point) Create a file called pascal.rb. For n coin tosses, how many possible toss sequences are there? And how many possible distinct outcomes are there? Put the answers in your pascal.rb file as comment lines. And don't just write a bare formula like n/5; state your answer in English, e.g., "# The number of possible sequences is n/5." (It's not really n/5.)

   2. (1 point) Add a function to your file called pairsum(x) that takes an array of numbers as input and returns the sums of adjacent pairs. For example:

      >> pairsum([1, 10, 50, 300, 80])
      => [11, 60, 350, 380]
      
      >> pairsum([0, 1, 2, 1, 0])
      => [1, 3, 3, 1]
      

   3. (1 point) Now add a definition for the nextrow(x) method to your file. Given any row of Pascal's triangle, such as [1, 2, 1], the expression nextrow([1, 2, 1]) should call pairsum and return the next row, which in this case would be [1, 3, 3, 1]. Look at the second pairsum example above to see how you can turn [1, 2, 1] into an input to pairsum that will give you back [1, 3, 3, 1].

   4. (1 point) Finally, add to your file a definition for the function pascal(n) that prints the first n rows of Pascal's triangle, as shown below. It should work by calling nextrow in a loop. Note: to get the numbers in the array x to show up in right-justified columns, use a formatted print statement, like this:

        for v in x do
          printf "%4d", v
        end
      

      The output of your function should look like this:

      >> load "pascal.rb"
      => true
      >> 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
      => nil
      

4. [2 points] 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 = Pe^{rt}\]

   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 = e^{rt} - 2\)). 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 10e+6.
   3. Set guess to 5e+6.
   4. Set guess_error to 5e+6.

   5. While guess_error is greater than 0.001, do the following:

      1. If \(e^{\textit{rate}\times\textit{guess}} - 2\) 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 \(\frac{\textit{high} + \textit{low}}{2}.\)

      3. Set guess_error to \(\frac{\textit{high} - \textit{low}}{2}.\)

   6. Return guess.

   Write a Ruby function called doubling(rate) in doubling.rb that computes the result using this algorithm. In addition to returning the result, your algorithm should keep track of the number of iterations needed to compute the result and print it, as shown below.

   Example:

   >> load "doubling.rb"
   => true
   >> doubling(0.05)
   33 => 13.8633185997605
   >> doubling(0.25)
   33 => 2.77243088930845
   

   Submission

   You should now have a pa3 directory that contains the files gcd.rb, make_square.rb, pascal.rb and doubling.rb, each in turn containing the corresponding function. Zip up your directory and upload it using the handin system. (The handin system will accept submissions beginning on Friday until the deadline Tuesday night.)