15110 SUMMER SESSION TWO - 2014

Problem Set 3 - due Wednesday, July 9 at 9:00AM in class

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 radius of r.
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:
        temp = y
        y = x % y
        x = temp
        q = p / x
    return q
```
  Show how this function computes lcm(36,48) 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
=====================================
 36    48      ---     1728    ---




=====================================
```
2. Consider the following recursive function that computes the LCM of x and y:
```
def lcm_helper(x, y, a, b):
    if (a == b):
        return a
    elif (a < b):
        return lcm_helper(x, y, a+x, b)
    else:
        return lcm_helper(x, y, a, b+y)

def lcm_recursive(x, y):
        return lcm_helper(x, y, x, y)
```
  Show how lcm_helper(36, 48) is computed recursively here by listing the chain of recursive calls that are made until an answer is found. We have started the chain for you below:
```
lcm_recursive(36, 48) 
--> lcm_helper(36, 48, 36, 48) 
--> lcm_helper(36, 48, 72, 48) 
-->
```

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

Complete the function below that implements the algorithm above in Python using a while loop.
```
def compute_average(list):
```
Write a new version of the function that uses a for loop instead.
```
def compute_average2(list):
```

(1 pt) Let codes represent a list of four digit access codes. All of the codes are between 1000 and 9999, inclusive. (That is, access codes do not start with a 0.) There may be duplicates. For each of the following Python functions, state what it is computing in common English.
1. ```
def mystery1(codes):
    for item in codes:
        if item % 1111 == 0:
            print(item)
```
2. ```
def mystery2(codes):
    return codes.count(codes[len(codes)-1])
```
(1 pt) If s is a string, len(s) returns the length of the string (i.e. the number of characters stored in the string). For example:
```
> s = "Pirates"
=> "Pirates"
>> len(s)
=> 7
```
Let dictionary represent an list of words stored as strings. For example:
```
dictionary = ["buick", "cadillac", "chevrolet", "gmc", "olds", "pontiac", "saturn"]
```
1. Write a Python function that prints the second word (e.g. "cadillac") in the dictionary without changing the list, only if the list contains at least two words.
```
def print_second_word(dictionary):
```
2. Write a Python function that uses a loop to remove all of the words in the dictionary that are more than 4 letters long and returns the resulting dictionary. (CAREFUL: This is tricky!)
```
def remove_words_over_4(dictionary):
```
(2 pts) Recall the implementation of the Sieve of Eratosthenes that we discussed in class:
```
def sift(list,k):
# remove all multiples of k from list - UPDATED
    index = 0
    while index < len(list):
        if list[index] % k == 0:
            list.remove(list[index])
        else:
            index = index + 1
    return list

def sieve(n):
    numlist = []
    for i in range(2,n+1):
        numlist.append(i)
    primes = []
    while len(numlist) > 0:
        primes.append(numlist[0])
        lastprime = primes[len(primes)-1]
        numlist = sift(numlist, lastprime)
    return primes
```
1. Modify the sieve function above so that it returns the number (amount) of primes less than or equal to n. (HINT: You only have to change one line.)
2. Modify the sieve function above so that it returns the largest prime less than or equal to n. (HINT: Again, you only have to change one line.)
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 the loop after we remove the multiples of 7, since the sqrt(50) is a little more than 7. A revised implementation of sieve is given below (assuming we import math).
```
def sieve(n):
    numlist = []
    for i in range(2,n+1):
        numlist.append(i)
    primes = []
    while numlist[0] <= math.sqrt(n):
        primes.append(numlist[0])
        lastprime = primes[len(primes)-1]
        numlist = sift(numlist, lastprime)
    return primes + numlist
```
  The return statement returns a list containing the values in primes followed by the values in numlist using concatenation. 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?