MCS-177 Homework assignment 3

As a reminder, the syllabus states:
For the most part, homework should be your own work. If, however, you get help from a classmate or some other reference for a problem or two, be sure to cite the reference. The citation should appear at the top of your written problem solution.

Homework set 3 (due Friday, October 6)

The Fibonacci numbers are defined as follows:
a0 = 0
a1 = 1
an = an-1 + an-2
  1. Compute the first 10 Fibonacci numbers, a0, a1, a2, ..., a9, by hand. If you've never seen the Fibonacci numbers, check with a classmate to be sure you are getting the right answers.

  2. Write a recursive procedure, (fibonacci n) to compute the nth Fibonacci number.

  3. This time write a procedure, (fibonacci n), which generates an iterative process. Notice that your helper procedure will need to remember the two Fibonacci numbers as well as where it is, so it can stop when it's reached n. Be sure to name your arguments well, and to add a comment explaining what the arguments are.

  4. In this part, build up some timing information about your two procedures to determine how fast (or slow) your procedures are. To do this, you'll want to first 
      (load "~mc27/public/time.scm")
    Then, try typing (run-time fibonacci 10) You'll get a result back from scheme saying something like: 
      ;Time: 7.2142857928385732e-3
    This means that it took 7.21x10-3 seconds (or .00721 seconds) to compute the 5th Fibonacci number. (Your results will differ.)

    Make a single table with these timing results.

  5. Plot the running times of your two procedures on a plain sheet of graph paper. (You may also use a computer graphing program if you know one.) Your x-axis should be n, and your y-axis should be the running time of (fibonacci n). Choose your scale to make the iterative version looks good; i.e., the iterative version should go from the lower left corner of the page to the upper right corner. The recursive version will be hard to plot clearly on this paper no matter what the scale, but do your best.

    Whenever plotting data in this course, only plot the points; do not connect the points.

  6. Using a ruler, draw two straight lines, one that (as closely as possible) goes along each curve. Which set of the two sets of data do you think is more linear? Explain your answer. If you haven't collected enough data for the results to be convincing, go back and collect more!

  7. Use semi-log paper to plot the same data. Plot n along the short side (x-axis) and time along the log side. This time, choose the scale so that the recursive version looks good. If you've never seen log-paper before, the bottom row (marked ``1'') is 1 unit. The next line marked ``1'' is 10 units. The next ``1'' after that is 100 units, then 1000. The very top line would be 10,000 units. One unit can be whatever you choose: a second, or a fraction of a second or whatever. There is also semi-log paper in my homepage. It's 5 cycle (so the top line would be 100,000 units).

  8. Again, using a ruler, draw a straight line that (as closely as possible) goes along both curves. Which of the two sets of data do you think is more like a line on semi-log paper? Explain your answer. (A line on semi-log paper translates to an exponential curve, i.e., a curve of the form abn for constants a and b.) Again, be sure to collect enough data so you have convincing results.

  9. How big an n can you handle with each of the two procedures in if you had 100 years of computer time? (Hint for recursive one: First answer the question for some small values like 1 second, 2 seconds, 4 seconds, 8 seconds, 16 seconds, and then interpolate to 100 years. Or, fit the points to an exponential abn. Or, you could estimate the answer graphically by using 10-cycle semi-long paper in my homepage. Choose a scale so that 100 years is near the top of the page.)