15110 Fall 2011 [Cortina/von Ronne]

Written Homework 3 - due Friday, September 23 in class

Reading Assignment

Read sections 3.1-3.8 in chapter 3 and sections 4.1-4.2 in chapter 4 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.)
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(45,60) 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
=====================================
 45    60      ---     2700    ---




=====================================
```
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)
	else    # otherwise, a > b
		return lcm2(x, y, a, b+y)
	end
end
```
  Show how lcm(45,60) 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(45, 60) --> lcm2(45, 60, 45, 60) --> lcm2(45, 60, 90, 60) --> 
```
(2 pts) Recall the function we wrote for finding the maximum in an array of integers:
```
def findmax(list)
        max_so_far = list[0]
        for i in (1..list.length-1) do
                if list[i] > max_so_far then
                        max_so_far = list[i]
                end
        end
        return max_so_far
end
```
1. Rewrite the function so that it returns the index of the maximum integer in the array. If there are duplicates of the maximum integer, return the index of the first of these duplicates.
  HINT: Instead of keeping track of the maximum so far, keep track of the index of the maximum so far.
2. Someone wants to delete the maximum (and its duplicates) from an array called list and writes this statement:
```
list.delete_if { |item| item == findmax(list) }
```
  What is wrong with this computation? Explain with an example.
(1 pt) Let scores represent an array of exam scores. All of the exam scores are between 1 and 100, inclusive. There may be duplicates. For each of the following Ruby statements, state what it is computing in common English.
1. ```
scores.each{ |x| 
	if x / 10 == 7 then
		print x 
		print "\n"
	end
}
```
2. ```
scores.delete_if { |x| x / 10 == x % 10 }
```
(1 pt) Let dictionary represent an array of words in alphabetical order.
1. Write a Ruby statement that prints the second-to-last word in the dictionary without changing the array.
2. Write a Ruby statement that removes all of the words that are less than 7 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. How would you modify the function above so that it returns the number (amount) of primes less than or equal to n?
2. How would you 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?
(2 pts) In class, we discussed the linear search algorithm, shown below in Ruby:
```
def search(list, key)
        index = 0
        while index < list.length do
                if list[index] == key then
                        return index
                end
                index = index + 1
        end
        return nil
end
```
Suppose that we know the additional fact that the list is sorted in non-decreasing order (this means that list[i] ≤ list[i+1], for 0 ≤ i < list.length-1). For example, if our list has the values:
[25, 37, 45, 61, 73, 79, 82, 94]
then if we want to search for the key 50 using linear search, we can stop when we reach 61 and return nil (assuming that the list is sorted).
1. Revise the method above so that it also returns nil if it examines a list element that is larger than the key. (Since the array is sorted, this implies that there's no need to search the rest of the array.)
2. If the array has n elements, what is the number of elements that would be examined in the worst case for this revised method? Explain.
3. In order to use your new method, you should probably have a method that allows you to check to make sure that the array is sorted in non-decreasing order before you use the search method. Write a Ruby function sorted? that returns true if an array called list is sorted in non-decreasing order or false if it is not.
```
def sorted?(list)




end
```
  HINT: Set up a loop to compare list[i] with list[i+1]. If you ever get two neighboring elements that are not in non-decreasing order, then the whole list cannot be sorted. Be careful with the range you use for i.