Note: You are responsible for protecting your solutions to these problems from being seen by other students both physically (e.g., by looking over your shoulder) and electronically. In particular, since the lab machines use the Andrew File System to share files worldwide, you need to be careful that you do not put files in a place that is publicly accessible.
If you are doing the assignment on the Gates-Hillman Cluster machines we use in lab or on unix.andrew.cmu.edu, our recommendation is that you create a pa5 directory under ~/private/15110 for this assignment. That is, the new directory pa5 is inside a directory called 15110, which is inside the directory called private, which is inside your home directory. (Every new andrew account is set up with a private subdirectory within the account's home directory that only that account can access.) Please refer to Setting up Directories for information about managing your directories.
For this assignment, you will create a Ruby source file (that is, a text file containing Ruby code) for each of the problems below. You should store all of these files in a folder named pa5, which you will zip up and submit.
As you will discover this semester, computer programs are rarely correct when they are first written. They often have bugs. In addition to writing the code, you should test your code on multiple inputs, for which you independently know the correct output (e.g., by plugging the inputs into a calculator).
In this assignment, for each of the problems described below, you will create a Ruby source file containing Ruby functions implementing your solution. If you find it useful, you may define additional helper functions that your primary function calls to solve a sub-problem. Definitions for these helper functions should be included in the same Ruby source file as the primary function. You should store your source files in a folder named pa4.
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.
Starting with this programming assignment, you will be graded on some style. This means that you are required to keep each line of code under 80 characters in length, to properly indent your code (ask a TA or post to Piazza if you are unsure about how to indent), and to try and use meaningful variable names where appropriate (i.e. if you are adding the elements in a list, use the variable sum instead of x).
[1 point] Recursive Sum
In a file sum.rb, write a recursive function sum(n) that takes in the non-negative integer n and returns the sum from $1$ through $n$.
Example:
>> load "sum.rb" => true >> sum(4) => 10 >> sum(10) => 55
[4 pts] Order Matters
[2 points] Printing Even Elements
In the file print_evens.rb, write a recursive function print_evens(list) that takes a list of integers as input and prints out only the even elements from the front of the list to the end, one element per line.
Use the following algorithm:
Example:
>> load "print_evens.rb" => true >> print_evens([40,60]) 40 60 => nil >> print_evens([1,2,4,7,8]) 2 4 8 => nil
[2 points] Printing Even Elements Backwards
<In the file print_evens_backward.rb, write a recursive function print_evens_backward(list) that takes a list of numbers as input and prints out only the even elements from the end of the list to the front, one element per line.
Example:
>> load "print_evens_backward.rb" => true >> print_evens_backward([40,60]) 60 40 => nil >> print_evens_backward([1,2,4,7,8]) 8 4 2 => nil
[2 points] Exponentiation
Exponentiation can be implemented using the following recursive formula: $$ a^e = \left\{ \begin{array}{lr} 1 & e = 0 \\ a*a^{e - 1} & e > 0 \end{array} \right.$$
Write a Ruby function pow(base,exponent) (stored in the file pow.rb) that recursively computes the value of base raised to exponent based on the formula above. You may assume that exponent is a non-negative integer.
HINT: This function will look similar to the factorial function we did in class.
Example:
>> load "pow.rb" => true >> pow(2,20) => 1048576 >> pow(3,5) => 243
[3 points] Cumulative Sums
The cumulative sum for a list of integers is another list such that the element at the $i^{th}$ index of the cumulative sum is the sum of the first $i + 1$ elements of the original list. For example, the cumulative sum for the list \([3,5,4,7]\) is the list \([3,8,12,19]\). The element at index 0 in the cumulative sum is the same as the element at index 0 of the input list (i.e. 3), the element at index 1 of the cumulative sum is the sum of the elements at indices 0 and 1 of the input list (i.e. 3+5 = 8) etc.
In the file cumulative_list.rb, define a function cumulative_list(list) that takes a list as a parameter and returns the cumulative sum for list.
Note: We require the use of recursion but you can use it in any way you want. There is a lot of freedom in writing the cumulative_list function. Your code will likely have more than one function, one of which is a helper function. Depending on how you write your code you may want to use one of the array operators << for appending an element to a list, or + for concatenating two lists. We saw the operator << in class. The operator + appears in Chapter 3 of the text book. If a and b are 2 arrays, the expression a + b creates a new array that has all the items in a followed by all the items in b.
Example:
>> load "cumulative_list.rb" => true >> cumulative_list([2,20]) => [2,22] >> cumulative_list([3,5,4,7]) => [3,8,12,19] >> cumulative_list([]) => []
You should now have a pa5 directory that contains the files sum.rb, print_evens.rb, print_evens_backward.rb, pow.rb, and cumulative_list.rb each containing the corresponding function. Zip up your directory and hand it in.