15110 Fall 2011 [Cortina/von Ronne]

Programming Assignment 4 - due Tuesday, September 27


For this assignment, you will create a Ruby source file containing a ruby 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 Ruby source file as the primary function they help. You should store a source file for each problem in a folder named pa4.

Warning: The final problem of this assignment makes use of RubyLabs and graphics. Working on this problem remotely will require additional setup that may not have been necessary for previous programming assignment problems. In particular, if you have not been able to run gedit over ssh, you will probably not be able to do this assignment remotely.

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. Suppose you want to find out how many scores in a list are above the average score of that list. This should be done in two parts. First, develop a function to compute the average, and then develop a second function that that counts the number of scores above the average using the average value computed in the first part.

    1. (2 pts) Write a Ruby function called score_avg(x) (in above_avg.rb), which takes a list (array) of numerical scores (\(x_0 \ldots x_{n-1}\)) as its parameter and returns their arithmetic mean, \[ \bar{x} = \frac{1}{n}\;\sum_{i=0}^{n-1} x_i.\]

      This should be done in two steps. First, iterate over the elements of the list, computing the sum of those elements. Then divide that sum by the length of the list, and return the quotient of that division operation.

    2. (2 pts) Write a Ruby function called num_above_avg(scores) (in above_avg.rb). It should take a list of numerical scores as its parameter and return a count of the number of scores that are larger than the arithmetic mean.

      This should be done as follows: Call the function score_avg that you wrote for part (a) to compute the average of the scores in scores. Then, initialize a variable count to zero. Then, iterate over the scores in scores, and increment count for each score that is greater than the average. Finally, return the final value of count.

  2. (2 pts) Write a Ruby function called std_dev(x) (in std_dev.rb), which takes a list of numerical scores as its parameter and returns their standard deviation, \[ \sigma = \sqrt{\frac{1}{n}\;\sum_{i=0}^{n-1}(x_i - \bar{x})^2}. \]

    You should use the following algorithm for accomplishing this calculation.

    1. Set avg to the average of array x.
    2. Set sum_of_squares to zero.
    3. Iterate over the scores in array x, for each score xi, do the following:
      1. Add the square of xi - avg to sum_of_squares.
    4. Calculate the quotient of sum_of_squares divided by the length of the array.
    5. Return the square root of the quotient computed in the previous step.

  3. (2 pts) Sometimes, in addition to knowing the average (mean) of a list, it is also useful to know the "middle" value (median) of that list. Define a Ruby function median(list) (in median.rb) that takes a parameter containing a list of values and returns the median value of that list.

    This should be done using the following algorithm:

    1. Set sorted_list to the list containing the elements of list rearranged in sorted order.

    2. Set n to the length of list.

    3. If n is odd, then return the element at position \(\frac{n-1}{2}\) in sorted_list. Otherwise (that is, when n is even), return the average of the elements at positions \(\frac{n}{2}-1\) and \(\frac{n}{2}\) in sorted_list.

    You may use Ruby's built-in array sort method to sort the list in step I.

  4. (2 pts) The image to the right is a Sierpinski's Triangle (albeit, rotated and with a different angle than the canonical form). It is a fractal; that is, it is "a rough or fragmented geometric shape that can be split into parts, each of which is (at least approximately) a reduced-size copy of the whole." In this case, you will notice that, if you look at the lower-right corner, it looks the same (down to the level of one pixel) at different levels of magnification.

    Starting with a completely filled-in square, this Sierpinski's Triangle can be produced with the following procedure:

    1. Return if the image is too small to be visibly subdivided.
    2. Otherwise, consider the square being divided up into four quadrants (squares).
    3. Draw a square (rectangle with equal sides) in the upper-left quadrant.
    4. Recursively draw a Sierpinski carpet in each of the other three quadrants.

    Finish the following incomplete Ruby implementation of this algorithm and save it as sierpinski.rb. You only need to supply the parameters to the recursive procedure calls. You should not add any other additional code. If you do this correctly, you will be able to reproduce the image shown above, by calling start_sierpinski(256,"blue") after loading your source file. You should note that when you specify drawing coordinates for the canvas, the top left corner is the origin (0,0), x increases as you go from left to right, but y increases as you go from top to bottom.

    HINT: You need to figure out the top-left corner and size for each of the other three quadrants and fill them in for the parameters for the three recursive calls.

    # This function initializes a RubyLabs Canvas, colors it color, and
    # then calls the recursive function sierpinski to do all the work
    def start_sierpinski(size, color)
       size = size.round()
       Canvas.init(size+2, size+2, "SierpinskisTriangle")
       Canvas::Rectangle.new(1, 1, size+1, size+1,
                            :width => 0, :fill => color)
       sierpinski(0, 0, size)
    # draw a Sierpinski triangle with top left at (x,y) and 
    # with height and width of size
    def sierpinski(x, y, size)
       # stop when the size gets smaller than 2 (since we can't subdivide a pixel)
       return if size < 2
       half = size / 2.0
       # recursively repeat the sierpinski triangle 
       # for each of the other three quadrants
       sierpinski( , , )  # Fill in the missing parameters of this call!
       sierpinski( , , )  # Fill in the missing parameters of this call!
       sierpinski( , , )  # Fill in the missing parameters of this call!
    def draw_topleft_square(x,y,half)
       # draw a white square in the upper left quadrant
       Canvas::Rectangle.new(1 + x,
                             1 + y,
                             1 + x + half,
                             1 + y + half,
                             :width => 0, :fill => "white")

    Note: this problem uses RubyLabs and requires X11 graphics. Please refer to the instructions for setting up RubyLabs. If you are not using the machines in the Gates Hall Cluster, please refer to the Remote Access Instructions


You should now have a pa4 directory that contains the files above_avg.rb, std_dev.rb, median.rb, and sierpinski.rb, each in turn containing the corresponding function(s). 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.)