15110 Fall 2012 [Touretzky/Kaynar]
Programming Assignment 5 - due Wednesday, October 3
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(s) for each problem in a folder named pa5.
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.)
- (2 points) Ruby has a method class that returns the
class of an object. For example, 5.class returns
Fixnum, and "woof".class returns String.
Write a recursive Ruby function same_class?(x) that returns
true if all the elements of the list x are of the same class.
>> same_class?(["one", "two", "three", "four", "five"])
>> same_class?([1, 2, "three", 4, 5])
How can we write this function recursively? Consider this: if the
result should be false, there must be at least one element of the list
that is of a different type than the element that comes after it. So
here is the algorithm:
- Return true if the list has at most one element.
- Return false if the first two things in the list are of different classes.
- Recursively call yourself on the tail of the list (everything but the first element) and return that result.
- (2 points) Let x = [1,2,3] and let y = [4,5,6]. For each of the
following expressions, executed in the order shown here, write down
the value of the expression, and say whether the value of x changed,
the value of y changed, both changed, or neither changed. Put your
answers in a text file called prob2.txt.
- x + y
- x + ["y"]
- x + 
- x << 
- [x, y]
- x << y
- (2 points) In this problem you will write two versions of a Ruby
function pairup(x) that takes a list x as input and
returns a nested list where the elements have been grouped into pairs.
We'll call the two versions pairup_r and pairup_i.
You can assume the list is always of even length. Examples:
=> [[1, 2], [3, 4]]
>> pairup_r(["a", "b", "c", 37, 42, 56])
=> [["a", "b"], ["c", 37], [42, 56]]
- Write pairup_r(x) as a recursive function. It should
(i) form a pair from the first two elements of x, and (ii)
call itself recursively to form pairs from the rest of the list. How
will you combine results (i) and (ii) to produce the result the
- Write pairup_i(x) as an iterative function. It should
produce the same results as the recursive version, but with a while
loop instead of a recursive call.
- (2 points) We can use recursive calls to build up nested lists in
a variety of ways.
- Write a recursive function nest_to_depth(n) that returns "woof" nested
to depth n. Examples:
Hints: What should be the result of nest_to_depth(0)? What
is the relationship between nest_to_depth(n) and
- Write a recursive function nest_right(x) that turns a
flat list x into a right-nested list. Examples:
=> [1, [2, ]]
>> nest_right(["alpha", "bravo", "charlie", "delta"]
=> ["alpha", ["bravo", ["charlie", ["delta"]]]]
- (2 points) One place where recursion is especially useful is in
searching nested arrays. Consider the function find_odd(x)
that returns the first component of the array x that is an
odd number, or nil if no elements are odd. If x
were a simple list we could use an iterator such as each to
search it, but in order to work correctly on nested arrays, we must
use recursion. This would be harder to solve with a while loop
because we'd have to maintain the "stack" ourselves. Examples:
>> find_odd([2, [4, [6, 7, 8], 10]])
>> find_odd([2, [4, [6, 0, 8], 10]])
Write the find_odd(x) function using the following algorithm:
- If x is the empty list, return nil.
- If x is an integer, then...
You can use x.kind_of?(Integer) to tell if an object is an integer.
- If x is odd, return x.
- Otherwise return nil.
- Otherwise, if a recursive call on the head (first element) of x
returns a non-nil value, then return that value.
- Otherwise, return the result of a recursive call on the tail of
x, i.e., every element except the first.
You should now have a pa5 directory, containing:
Zip up your entire pa5 directory and upload it using the handin system.