15110 Spring 2012 [Cortina/von Ronne]

Problem Set 1 - due Friday, June 1 at 11:59pm

Reading Assignment

Read sections 2.1-2.4, 3.1-3.8 of the textbook Explorations in Computing and read pages 19-42 of chapter 2 of the book Blown To Bits.

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) For each of the following Ruby expressions, show how they are evaluated by evaluating one operation at a time and showing the reduced expression until you have a final answer. For example, if the Ruby expression is 3 * 4 + 5, you answer would look like this:
```
3 * 4 + 5
12 + 5
17
```
HINT: You can check your final answers with irb!!!
1. 25 - 6 * 5 / 2 + 4
2. 4 ** 3 ** 2
3. 12345 / 100 + 12345 % 100
4. 10+2 * 7-3
(2 pts) A simple pendulum consists of a mass suspended by a string with a specific length. The period of this simple pendulum can be computed using the following Ruby method (function) which requires the length of the string in meters and the acceleration due to gravity in meters per second per second :
```
def compute_period(length, gravity_accel)
    # computes period of simple pendulum given the string length in meters
    # and the acceleration due to gravity in meters/sec/sec (e.g. 9.8)
    return 2 * Math::PI * Math.sqrt(length / gravity_accel)
end
```
1. Suppose we use this function to compute the period of a pendulum with a string length of 10 meters and an acceleration due to gravity of 9.8 meters/second/second:
  compute_period(10, 9.8)
  Will we get an integer result or a floating point result? Why?
2. Suppose we want to do the computation in part (a) but we call our function with the length of the string only:
  compute_period(10)
  Does the method use a default value for the acceleration due to gravity or does Ruby complain about this function call? Explain.
3. Suppose we want to do the computation in part (a) but we call our function with the arguments in reverse order:
  compute_period(9.8, 10)
  Does Ruby report an error? Why or why not?
4. Suppose we replace the return statement with a print statement as shown below:
```
def compute_period(length, gravity_accel)
    # computes period of simple pendulum given the string length in meters
    # and the acceleration due to gravity in meters/sec/sec (e.g. 9.8)
    print 2 * Math::PI * Math.sqrt(length / gravity_accel)
end
```
  What value is stored in the variable period if we execute the following instruction? Why?
  period = compute_period(10, 9.8)
(2 pts) For each of the following invalid Ruby expressions, run them in irb and explain the errors that you see.
1. Math.sqrt(-16)
2. 32 % 0
3. 15 + "110"
4. return = 100
(2.5 pts) Consider the following Ruby method definition that uses a loop:
```
def mystery(n)
    value = 1
    for i in 1..n do
        value = value * 2
        print value
        print "\n"    # print a newline character
    end
end
```
1. What does this method display if we call it as follows:
  mystery(7)
2. What mathematical function is this Ruby method computing in general if n > 0?
3. Suppose we replace the first instruction inside the loop with the following:
  value = value * i
  What does this revised method display if we call it as follows:
  mystery(7)
4. What mathematical function is the revised Ruby method computing if n > 0?
5. Using irb, see what happens in the original function if we replace the print statements with a return statement instead:
```
def mystery(n)
    value = 1
    for i in 1..n do
        value = value * 2
        return value
    end
end
```
  Store the function in a file, then load it in irb and call it with different positive integers and observe the results. What do your observations suggest about how the return statement works?
(1.5 pts) Besides learning how to use computational devices to solve a problem, we should understand what happens once the device solves the problem for us. Based on your reading of Chapter 2 (pages 19-42) of Blown To Bits, answer the following questions about the digital data you generate and how all of this digital data affects your privacy.
1. In your own words, describe one example of how you might leave "digital footprints" while driving your vehicle, based on what you read in the chapter. (Write 2-3 sentences for the example you cite.)
2. In your own words, describe one example of how stores might digitally track your purchases so they can suggest new items for you to purchase, based on what you read in the chapter. (Write 2-3 sentences to explain how the tracking is done.)
3. In your own words, briefly describe one example from the reading where a person's confidential medical records were discovered by linking the anonymized records with another data set.
(1 pt) Assume you can only give someone a sequence of instructions from the following set of two instructions:
- Draw a square centered 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 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) -->
```
  (typo corrected)
(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?