15110 SUMMER SESSION ONE - 2013

Programming Assignment 5 - due Wednesday, June 5 by 10:30AM using ELECTRONIC HANDIN

Overview

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.)

The Algorithms

[2 points] Exponentiation can be implemented using the following recursive formula:
\[ b^e = \begin{cases} 1 & \text{ if } e = 0\\ b \times b^{e-1} & \text{ if } e > 0\\ \end{cases} \]
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
```
[2 points] In print_x.rb, define an Ruby function print_x(list) that takes an array of strings called list and prints out each string that starts with an "x" in list.

Use the following recursive algorithm that prints out each string of an array that starts with an "x":
1. Return nil if list is empty.
2. Print the first element in list followed by a new line if that first element starts with an "x".
3. Recursively print out each string that starts with an "x" in an array including all but the first element in list.
4. Return nil.
Hint: a string s starts with "x" if and only if s ≥ "x" and s < "y".
(Why?)
Example:
```
>> load "print_x.rb"
=> true
>> print_x(["xantis", "weasel", "yak", "xiphias", "X-Ray fish", "dog", "xenopus"])
xantis
xiphias
xenopus
=> nil
```
[2 points] Write a Ruby function print_skip(list) (stored in the file skip.rb) that takes an array of strings called list and prints out every other string in the list, starting with the first string. This function will not be recursive, but it will require a helper function that is recursive.

Use the following algorithms:

Algorithm for print_skip(list):
1. Call another function print_skip_helper to print out the given list starting at the index of the first element of the list. (Note that the helper function, specified below, has two parameters: the list and the index to start at. So you have to call this function with the variable used to represent the current list and the actual index of the first element of the list.)
2. Print out a new line character.
3. Return nil.
Algorithm for print_skip_helper(list,i) to print every other string in the given list starting from index i:
1. If i does not represent a valid index of the string, then return nil.
2. Otherwise do the following:
  1. Print out the string at index i in the given list.
  2. Print out a space.
  3. Recursively print every other string in the list starting at index i+2.
  4. Return nil.
You may assume that the i passed into print_skip_helper is a non-negative integer.

Example:
```
>> load "skip.rb"
=> true
>> print_skip(["a","b","c","d","e"])
a c e 
=> nil
>> print_skip(["f","g","h","i"])
f h
=> nil
>> print_skip_helper(["a","b","c","d","e","f"],2)
c e => nil
>> print_skip_helper(["g","h","i","j"],1)
h j => nil
```
Ruby has a function kind_of? that can be used to identify whether a value is a string, number, or an array as shown in the following examples:
```
>> s = "Hello"
=> "Hello"
>> s.kind_of?(Numeric)
=> false
>> s.kind_of?(String)
=> true
>> s.kind_of?(Array)
=> false

>> x = 3
=> 3
>> x.kind_of?(Numeric)
=> true
>> x.kind_of?(String)
=> false
>> x.kind_of?(Array)
=> false

>> a = [1, 2, 3]
=> [1, 2, 3]
>> a.kind_of?(Numeric)
=> false
>> a.kind_of?(String)
=> false
>> a.kind_of?(Array)
=> true
```
1. [2 points] We define a short string as a string whose length is less than 5. Write a recursive function count_short_strings(list) (stored in the file short_strings.rb) that takes an array called list of numerical values and strings (in any order) and returns the total number of short strings stored in the list. Use the following algorithm:
  1. Return 0 if list is empty.
  2. Compute the number of short strings in an array consisting of all of the elements of list except the first element by calling this function recursively. Store the returned result in subtotal.
  3. Set element equal to the first element of list.
  4. If element is a short string, then return 1 + subtotal. Otherwise, return subtotal.
  HINT: A short string is a string that has a length less than 5.
  
  Example:
```
load "short_strings.rb"
=> true
>> count_short_strings(["Too long", "shrt", 123, "a", "2long", 124315])
=> 2
```
2. [2 points] In Ruby, an element of an array can itself be an array. For example [[1,2], [3,4,[5]], 6] is an array whose first element is the array [1,2] and whose second element is the array [3,4,[5]], and whose third element is the number 6. The arrays [1,2] and [3,4,[5]]] are said to be nested in the array [[1,2], [3,4,[5]], 6]. The array [5] is nested in [3,4,[5]].
  
  In nested_sum.rb, write a function nested_sum(list) (stored in the file nested_sum.rb) that returns the sum of all the numbers in list, including all numbers nested inside of this list. You may assume this list does not contain strings. That is, all data in the list, or nested within, is numerical.
  
  Implement nested_sum(list) according to the following recursive algorithm:
  1. Set total equal to 0.
  2. For each element x in list, do the following:
    1. If x is a number, then add x to total.
    2. If x is an array, then
      1. Set nested_list equal to x.
      2. Recursively compute the sum of all of the numbers in nested_list and all of the numbers embedded in arrays nested within nested_list and store this result in nested_list_sum.
      3. Add nested_list_sum to total.
  3. Return total.
  Example:
```
>> load "nested_sum.rb"
=> true
>> nested_sum([[1,2], [3,4,[5]], 6])
=> 21
```
Submission

You should now have a pa5 directory, containing:
1. pow.rb
2. print_x.rb
3. skip.rb
4. short_strings.rb
5. nested_sum.rb
Zip up your directory and upload it using the handin system.

15110 SUMMER SESSION ONE - 2013

Programming Assignment 5 - due Wednesday, June 5 by 10:30AM using ELECTRONIC HANDIN

Overview

The Algorithms

Submission