CS8, Spring 2017

Lab03:
Accumulating products and sums
Approximating an irrational number (that is not π)

Goals for this lab

By the time you have completed this lab, you and your lab partner should be able to

Step by Step Instructions

Step 0: Get together with your assigned lab partner.

If your partner is more than 5 minutes late, ask the TA to pair you with someone else for this week.

Step 1: Log in, and create a lab03 directory

Decide which one of you will be the first pilot for this lab, and then log in to the pilot's account and create a directory called lab03 inside his/her cs8 folder. You will work in this account for the rest of the lab, but remember to switch often between pilot and navigator roles during the course of the lab.

Step 2: Bring up IDLE as usual, and open a new window for function definitions

Start IDLE. Then, select "File->New Window" and add a comment at the top of this new file like the following (with the proper substitutions of course):

# lab03.py
# Your name(s), today's date
# a factorial function and a Fibonacci function

Then, save it under the name lab03.py inside your lab03 directory.

Step 3: Practice writing a function to accumulate products

(Exercise 2.12 from page 56 of the text). Together we will write a function called factorial that computes the product of the first N numbers, where N is a parameter. For example, factorial(4) is calculated as 1 * 2 * 3 * 4, so the function should return the value 24. We will assume N is greater than 0. Be sure to understand the purpose and meaning of each of the following instructions before you execute them.

  1. Skip a blank line (in your lab03.py file), and then type a brief comment for a factorial function such as the following: 
    # factorial - returns n factorial
# assumes n is greater than or equal to 0
  2. On the very next line, type the function header as follows: 
    def factorial(n):
  3. We need an "accumulator" variable for the result. Since the accumulation will be multiplicative (instead of additive), this variable should be initialized to 1 (and the statement must be indented as it is inside the function): 
        result = 1
  4. Now it is time to loop through the values that must be multiplied, and we will use the Python range function for the purpose. First let's think about the sequence we need to multiply: 1*2*...*n. We can skip the 1 and still get the same result, but we can't skip the n. So that means we can start the range at 2, but the stop value must be n+1 to include n as the last value. Inside the loop we must do the multiplications and accumulate the product in our result variable. Here is the whole thing (since we already initialized result to 1 above; and notice the body of the loop is indented one more time): 
        for i in range(2, n+1):
        result = result * i
  5. Just one last thing to do is return the result, and then type a blank line to indicate the function is complete: 
        return result

Save and run the module. Then test the function a few times (in the Python shell window) by comparing its results to ones that you calculate manually. Here is one example run of our solution:

>>> factorial(5)
120

Step 4: Write and test a function to accumulate sums

First switch roles between pilot and navigator if you did not already do that.

(Based on Exercise 2.14 from page 56 of the text). Write a function named fib to compute the Nth Fibonacci number where N is a parameter. Here is the required function header and an appropriate comment - type or copy/paste them into lab03.py at least one blank line below the end of the factorial function:

# fib - returns nth term of Fibonacci sequence:
#     1, 1, 2, 3, 5, 8, ... So fib(6) = 8
def fib(n):

The first two numbers in the Fibonacci sequence are both 1. After that, every succeeding number is equal to the sum of the previous two numbers. Here are the first 10 numbers in the sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. So fib(9) is 34 and fib(10) is 55 - think about what is fib(11) ... 34 + 55 of course.

Test your function thoroughly to be sure it is correct. Verify that both fib(1) and fib(2) return 1, fib(3) returns 2, and so on. You may assume that N will always be greater than 0, but find out what the function returns for 0 or negative values too, and try to understand why it returns what it does in such cases.

Hint: Another way to write this is: fib(i) = fib(i-1) + fib(i-2). This does not mean that to calculate fib(i) you should call fib for both of the lower results. What this really means is that the result of this iteration is dependent on your result of the last iteration and the iteration before that. Storing those (two) partial results are the key to getting this algorithm correct.

Remember to let both partners think about this before diving in. Don't skip the design step, in which you work this out on paper before trying to write in Python.

IMPORTANT: you don't have to finish the next step (or even Step 4) to earn full credit.
Please begin and try to finish, but if you are running out of time before lab ends, then move on to Step 6
- the TA will check off your work as complete anyway.

Step 5: Use the Fibonacci function to approximate the golden ratio

For Hw3, you did some research about the "golden ratio" - often denoted by the lower case Greek letter, phi (φ). We hope you noticed this ratio can be approximated by using the Fibonacci function. In particular, as the value of n increases, the value of the fraction F(n+1)/F(n) gets nearer and nearer to φ. Here F denotes the Fibonnaci function. In calculus, this relationship is expressed as a limit, as n approaches infinity:

Of course, it is not necessary to plug ∞ into the formula to approximate the ratio, let alone (∞ + 1)! Your job is:

Find the smallest value of n for which the ratio is within 1.0e-10 of this approximate value of φ: 1.6180339887.

Devise a strategy using your fib function, and other things you've learned so far in CS 8. Things you should know:

Execute your strategy until an appropriate answer is visible in the Python shell window.

Step 6: Show off your work and get credit for the lab

If you did Step 5, be sure your evidence for completing it is clearly visible for the TA to inspect, and be prepared to answer questions about your approach to that step. If you did not finish Step 4, be ready to show evidence that you tried it and to answer any questions your TA might pose about your efforts. Also insure a copy of lab03.py is open, and that the module has been run since you last changed it. The TA may want to see you demonstrate its functions.

Get your TA's attention to inspect your work, and to record your lab completion.

Don't leave early though ... see challenge problems below.

Step 6a. ONLY IF YOU RAN OUT OF TIME TO HAVE THE TA INSPECT YOUR WORK

In the unlikely event that you must complete this assignment at CSIL, then submit it with the turnin program - but do not turn it in if the TA already checked you off. You MUST have both your name and your partner's name in the file in order to receive credit. Remember that the original pilot needs to do this step, since that is whose account you have been using in Phelps 3525. Use the following command after you cd into your cs8/lab03 directory:

turnin Lab03@cs8c lab03.py

After answering the questions, be sure to wait for the message indicating success.

Evaluation and Grading

Each student must accomplish the following to earn full credit for this lab:

Optional Extra Challenge

Some expressions of the golden ratio in nature and elsewhere form a "golden spiral" - several examples are here. An approximation to such a spiral (known as a "Fibonacci spiral") can be constructed from a series of squares, appropriately arranged and in sizes that correspond to a Fibonacci sequence.

Prepared for Computer Science 8 by Diana Franklin and Michael Costanzo.