15110 Fall 2012 [Touretzky/Kaynar]

Problem Set 3 - due Friday, September 22 in class

Reading Assignment

Read sections 3.1-3.8 in chapter 3 of the textbook Explorations in Computing.

Instructions

Type or neatly write the answers to the following problems.
Please STAPLE your homework before you hand it in, or bring $1 with you to purchase a staple from the CA.
On the first page of your homework, include your name, andrew ID, lab section (A-N), and the assignment number.
You must hand in your homework at the start of class on the given due date.

Exercises

(1 point) In class we showed examples using the successor method on strings in Ruby. For example, "99".succ returns "100" and "A99".succ returns "B00". We could call "99" the predecssor of "100" and "A99" the predecessor of "B00". Based on your understanding of the method succ, write the predecessor of the following strings:
1. "yz"
2. "a0b1c2"
3. "fa"
4. "aba00"
5. "aa00a0"
(2 points) Consider the following function that computes the position of the minimum element in an array of integers.
```
def findmin(list)
  position = 0
  min = list[0]
  for i in 1..list.length-1 do 
    if list[i] < min then
      position = i
      min = list[i]
    end
  end
  return position
end
```
1. Show how this function computes findmin([4,6,3,5]) by creating a table that shows the values of each variable at the end of each iteration of the loop. We have started the table for you with the initial values of the variables before the first iteration of the loop:
```
=====================================
 list          position   min     i
=====================================
 [4,6,3,5]        0        4      -




=====================================
```
2. Write a new version of findmin called findmin2 that uses a while loop instead of a for loop.
(3 points) Suppose that you are given the following Ruby code.
```
n = 9
for i in 1..n do
  for j in 1..n do
    print i*j, "\t"
  end
  puts
end 
```
1. Write a flowchart that represents the code given above. Hint: You will find the lecture slides useful.
2. Describe what the code above would print and return.
3. Suppose we replace print i*j with print i**j. What would it print and return in this case?
(2 points) (clarification added for part b)
1. Write a one line Ruby expression using "each" to print the cubes of the first 50 integers, i.e., 1, 8, 27, 64, etc.
2. Explain what the Ruby code below does by using a table as in Question 2 part a, and show the result of executing this code. Since this table may be too large to write in full, it is sufficient to show a few iterations that demonstrate that you understand how i and j change through iterations.
```
(1..10).each {|i| (1..i).each {|j| print "*"}; puts}
```
(2 points) Visit ruby-doc.org and go to the Ruby 1.8.7 core documentation. Under "Arrays", look up the drop_while iterator.
1. Write a plain English explanation of what the drop_while iterator does.
2. Suppose we have an array of arrays of integers. Each of these arrays begins with some number of zeros, followed by some other numbers. We want to get rid of the initial zeros and print out the rest of each array on a separate line, returning nil at the end. For example:
```
data = [ [0,0,0,0,5],
         [0,0,0,2,9],
         [0,0,4,1,3],
         [0,0,0,8,6],
         [0,0,0,0,7] ]

>> show_nonzero(data)
[5]
[2, 9]
[4, 1, 3]
[8, 6]
[7]
=>nil
```
  You can write the show_nonzero(x) function by using a for loop to iterate over the elements of x, and using drop_while to drop the leading zeros from each entry. Write down the definition for this function. Note: to print out an array in proper array notation (using square brackets and commas, as shown above) you must use "p" instead of "puts".