15110 Fall 2011 [Cortina/von Ronne]

Programming Assignment 3 - due Tuesday, September 20

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

The Algorithms

1. [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 \times 2 \times 3 \times 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 \(n\)'s prime factorization can be calculated using the following algorithm.

   1. Set dividend equal to \(n\).
   2. Set possible_factor equal to 2.
   3. While dividend is not 1, do the following:
      1. If possible_factor is a divisor of dividend:
         1. Print out possible_factor as a factor.
         2. Set dividend to \(\frac{\textit{dividend}}{\textit{possible_factor}}\).
         Otherwise, (if you did not execute the substeps 1 and 2, above):
         1. Add 1 to possible_factor.

   Hint: To determine if a number is a divisor of another number, think about using the modulo operator.

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

   irb(main):002:0> factor(60)
   2 2 3 5 => nil
   irb(main):003:0> factor(75)
   3 5 5 => nil
   irb(main):004:0> factor(77)
   7 11 => nil
   irb(main):005:0> factor(79)
   79 => nil
   

2. [2 points] Printing an ASCII-art Square.

   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
   X   X
   X   X
   X   X
   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 heigh the square is). It assumes that size is at least three.

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

   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 (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 follow:

   irb(main):002:0> make_square(5)
   XXXXX
   X   X
   X   X
   X   X
   XXXXX
   => nil
   irb(main):003:0> make_square(8)
   XXXXXXXX
   X      X
   X      X
   X      X
   X      X
   X      X
   X      X
   XXXXXXXX
   => nil
   

3. The Babylonian Method of Finding Square Roots.

   The square root of a number can be approximated to an arbitrary level of precision by an algorithm known as the Babylonian Method. It is thought that the Babylonians may have used this algorithm to calculate square roots, but its first explicit description is found in Hero of Alexandria's work from the 1st century A.D.

   1. [2 points] To calculate an approximation of the square root of a positive integer n, the following version of the Babylonian method can be used. The result will be accurate to a precision of within \(\frac{1}{1000}\).

      1. Set guess equal to n.
      2. Set precision equal to \(\frac{1}{1000}\).
      3. Set error equal to \(\textit{guess} - \frac{n}{\textit{guess}}\)
      4. While error > precision, do the following:
         1. Set guess equal to the average of guess and \(\frac{n}{\textit{guess}}\).
         2. Set error equal to \(\textit{guess} - \frac{n}{\textit{guess}}\).
      5. Return guess as the approximation of the square root.

      Define a Ruby function square_root(n) in square_root.rb that uses this algorithm to compute an approximation of \(\sqrt{n}\). (Note: you must use this algorithm, and not, for example, Math.sqrt.)

      Your function should be able to be used as follows:

      irb(main):002:0> for i in 1..16 do
      irb(main):003:1*   print square_root(i)
      irb(main):004:1>   print "\n"
      irb(main):005:1> end
      1
      1.41421568627451
      1.73214285714286
      2.00000009292229
      2.23606889564336
      2.44949437160697
      2.64576704419029
      2.82846857188015
      3.00009155413138
      3.16245562280389
      3.31693893473046
      3.4641016533503
      3.6055513629176
      3.74165756905871
      3.87298369800872
      4.00000063669294
      => 1..16
      

   2. [1 point] Define a Ruby function square_root2(n,precision) in square_root2.rb that uses the Babylonian method to compute an approximation of \(\sqrt{n}\) that is within precision of the true \(\sqrt{n}\). You may assume that \(n\times 10^{-13} \le\) precision \(\lt 1\), and thus, the limitations of Ruby's floating point numbers will not prevent the Babylonian method from from achieving the desired accuracy.

4. [3 points] Textual Calendar.

   One often needs to consult a calendar to know what day of the week a certain date will fall on (or conversely, what date will be on a particular day of the week). On unix.andrew.cmu.edu, there is a handy program called cal that will display a textual calendar for the current month. (Open a terminal or ssh in, and run cal to see what it looks like.)

   In February 2011, for example, the output of cal looked something like this:

      February 2011      
   Su Mo Tu We Th Fr Sa  
          1  2  3  4  5  
    6  7  8  9 10 11 12  
   13 14 15 16 17 18 19  
   20 21 22 23 24 25 26  
   27 28                 
   

   The output consists of a header line, followed by a table that shows the dates in February arranged into "columns" that represent the different days of the week. Note that each "column" consists of three fixed-width characters (including spaces). Note also that the table of dates for a month is completely determined by the number of days in that month (in this case, 28) and the day of the week of the first day of the month (in this case, Tuesday).

   The following algorithm can be used to construct a table showing the days of the month. It requires two integer parameters, the number of days days in the month \(n\) and the day of the week of the first day of the month \(d\). The day of the week \(d\) is encoded using 0 for Sunday, 1 for Monday, 2 for Tuesday, 3 for Wednesday, etc.

   1. Set week_days to an array containing the strings "Su", "Mo", "Tu", "We", "Th", "Fr", and "Sa".
   2. Iterate over week_days, and print each out in its own "column." Then print a newline character.
   3. Skip \(d\) "columns".
   4. For each \(i\) in 1 to \(n\) do the following:
      1. Print i (with extra spaces to fill the "column").
      2. If you just printed out the 7th "column", print a newline to move to the next line.
   5. Print a newline.

   Hint for step IVb: Notice that for any calendar, when adding its d to any value in the 7th "column," the sum is always divisible by 7. For example, in the February calendar above, where d = 2 (for Tuesday), 2+5, 2+12, 2+19, and 2+26 are all divisible by 7.

   Define a Ruby function calendar(n, d) in calendar.rb that uses this algorithm to print a table showing the days of a month with \(n\) days and whose first day starts on the day of the week encoded by the integer \(d\).

   Your function should be able to be used as follows:

   irb(main):004:0> calendar(31,6)
   Su Mo Tu We Th Fr Sa  
                      1
    2  3  4  5  6  7  8
    9 10 11 12 13 14 15
   16 17 18 19 20 21 22
   23 24 25 26 27 28 29
   30 31
   => nil
   irb(main):005:0> calendar(29,3)
   Su Mo Tu We Th Fr Sa  
             1  2  3  4
    5  6  7  8  9 10 11
   12 13 14 15 16 17 18
   19 20 21 22 23 24 25
   26 27 28 29
   => nil
   

Submission

You should now have a pa3 directory that contains the files factor.rb, make_square.rb, square_root.rb, square_root2.rb and calendar.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.)