15110 SUMMER SESSION ONE - 2013

Problem Set 3 - due Wednesday, May 29 at 10:30AM 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.
On the first page of your homework, include your name, andrew ID and the assignment number.
You must hand in your homework at the start of class on the given due date.

Exercises

(1 pt) Assume you can only give someone a sequence of instructions from the following set of two instructions:
- Draw a square with its top-left corner at ( x , y ) with a side length of s.
- Draw a circle centered at ( x , y ) with a diameter of d.
Write algorithms made up of instructions of the type shown above to draw each of the following pictures substituting in appropriate values for x, y, s and r in each instruction.
(1 pt) A precise algorithm is typically made up of instructions that consist of a set of known primitive operations that do not need explanation. For example, in arithmetic, the primitives add, subtract, multiply and divide are easily understood. Each of these operations can combine only two values at a time (e.g. "Add 2 and 3."). You may make reference to previous results in your instructions (e.g. "Multiply the result from step 3 by 10."). Using only these arithmetic primitive operations, write algorithms that describe how to perform each of the following computations:

For each algorithm, the result of your last algorithmic step should be the final answer. NOTE: In the second computation, you should write only four instructions to generate the answer.
(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.)
1. 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(24,32) 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
=====================================
 24    32      ---      768    ---




=====================================
```
2. Consider the following recursive function that computes the LCM of x and y:
```
def lcm(x, y)
        return lcm2(x, y, x, y)
end

def lcm2(x, y, a, b)
        if (a == b) then
                return a
        end
        if (a < b) then
                return lcm2(x, y, a+x, b)
        end
        if (a > b) then
                return lcm2(x, y, a, b+y)
        end
end
```
  Show how lcm(24, 32) is computed recursively here by showing the chain of recursive calls that are made until an answer is found. We have started the chain for you below:
```
lcm(24, 32) --> lcm2(24, 32, 24, 32) --> lcm2(24, 32, 48, 32) -->
```
(2 pts) Consider the following algorithm to compute the average of the integers stored in a list:
```
1. Set total equal to 0.
2. Set n equal to the length of the list.
3. Set i equal to 0.
4. While i is less than n, do the following:
   a. Add list[i] to total.
   b. Add 1 to i.
5. Return total / n.
```
1. Complete the function below that implements the algorithm above in Ruby using a while loop.
```
def compute_average(list)



end
```
2. Write a new version of the function that does not use an explicit for or while loop.
```
def compute_average2(list)



end
```
  HINT: Use the .each iterator operation.
(1 pt) Let codes represent an array of four digit access codes. All of the codes are between 1000 and 9999, inclusive. There may be duplicates. For each of the following Ruby statements, state what it is computing in common English.
1. ```
codes.each{ |item|
        if item % 1111 == 0 then
                print item, "\n"
        end
}
```
2. ```
codes.delete_if { |x| x / 100 == x % 100 }
```
(1 pt) If s is a string, s.length returns the length of the string (i.e. the number of characters stored in the string). For example:
```
> s = "Penguins"
=> "Penguins"
>> s.length
=> 8
```
Let dictionary represent an array of words stored as strings.
1. Write a Ruby statement that prints the second word in the dictionary without changing the array.
2. Write a Ruby statement that removes all of the words that are at least 5 letters long.
(2 pts) Recall the implementation of the Sieve of Eratosthenes that we discussed in class:
```
def sieve(n)
        numlist = Array(2..n)
        primes = []
        while numlist.length > 0 do
                primes << numlist.first
                numlist.delete_if { |x| x % primes.last == 0 }
        end
        return primes
end
```
1. Modify the function above so that it returns the number (amount) of primes less than or equal to n.
2. Modify the function above so that it returns the largest prime less than or equal to n.
3. A modification we can make to the original function is to remove multiples of 2, 3, ..., up to the square root of n. For example, if we want the primes up to and including 50, we can stop after we remove the multiples of 7 (since the sqrt(50) is a little more than 7). A revised implementation is given below.
```
def sieve2(n)
        numlist = Array(2..n)
        primes = []
        while numlist.first < Math.sqrt(n) do
                primes << numlist.first
                numlist.delete_if { |x| x % primes.last == 0 }
        end
        return primes + numlist
end
```
  The return statement returns an array containing the values in primes followed by the values in numlist. Briefly explain why we need to do this.
4. If we test this modified function from part c for n = 1000000, the modification suggests that we are going to remove multiples of all numbers up to sqrt(1000000) = 1000, but when we execute the function, it only repeats its loop 168 times. Why?