15110 Spring 2013 [Kaynar/Gunawardena]

Problem Set 3 - due Friday, February 8 in class

Reading Assignment

Read sections 3.1-3.3 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.
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

(2 pts) The Least Common Multiple (LCM) of two numbers x and y is the smallest positive integer that is a multiple of both x and y. (You use this when trying to find the lowest common denominator when adding fractions.)
Consider the following iterative function that computes the LCM of integers x and y, for x > 0 and y > 0:
```
def lcm(x,y)
  p = x * y
  while y != 0 do
    temp = y
    y = x % y
    x = temp
    q = p / x
  end
  return q
end
```
Show how this function computes lcm(21,49) 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:
```
=====================================
  x     y     temp       p      q
=====================================
 21    49      ---      1029    ---




=====================================
```
(2 pts) Consider the following algorithm to compute the average of the integers 1 .. n, given a positive integer n:
```
1. Set total equal to 0.
2. Set i equal to 1.
3. While i is less than or equal to n, do the following:
   a. Add i to total.
   b. Add 1 to i.
4. Return total / n.
```
1. Complete the function below that implements the algorithm above in Ruby using a while loop.
```
def compute_average(n)



end
```
2. Write a new version of the function using a for loop.
```
def compute_average2(n)



end
```
(2 points) Consider the following function that computes the the maximum element in an array of integers.
```
def findmax(list)
  max = list[0]
  for i in 1..(list.length-1) do 
    if list[i] > max then
      max = list[i]
    end
  end
  return max
end
```
1. Show how this function computes findmax([5,7,3,2]) 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           max     i
=====================================
 [5,7,3,2]       5     ---




=====================================
```
2. Write a new version of findmax called findmax2 that returns the position of the maximum element in the list. For example, the positoin of the maximum element in the list [5,7,3,2] is 1.
(3 points) Suppose that you are given the following Ruby code.
```
def table(n)
  for i in 1..n do
    for j in 1..n do
      print i*j, "\t"
    end
    puts
  end 
  return nil
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?
(1 points) Consider the following function that prints the the sum of elements in a list of integers.
```
def sum(list)
  total = 0
  for i in list do 
    total = total + i
  end
  print total
end
```
Suppose that you are given two lists, list1 and list2 and you wish to compute the sum of all the integers in the two lists by the following Ruby expression.
```
    sum_two_lists = sum(list1) + sum(list2)
```
What would need to be changed in the definition of sum(list) for the above assignment to be performed without any errors?