Lab02, CISC181 (honors), Spring 2004

Welcome

Lab02 has two parts.

Part 1 involves writing some simple functions using both iteration and recursion.

Part 2 involves using a StopWatch class to time how long it takes to do both iteration and recursion. The StopWatch class is provided for you; all you have to do is compile it and link it in with your program. The skills and knowledge you gained last week from Anderson Chapter 34 (separate compilation) should be useful here.

Part 1: Iteration vs. Recursion

In this part, you will write multiple versions of four different functions. For each of these function, the function is defined only if n≥0. For negative values, print an error message on cerr, and terminate the program with exit (-1); Here are the various functions you'll write. After the list, we'll tell you what to do with each one of them.
  1. f(n) = 2 raised to the nth power.

    For this function, you will write three versions.

    1. iteration on integers
    2. recursion on integers
    3. using pow(2.0, i) where i is a double, and the function returns a double.

  2. f(n)= n! ( n factorial). For factorial, write four versions:
    1. recursive, using int
    2. iterative, using int
    3. recursive, using double
    4. iterative, using double

  3. fibonacci, a function where f(0) = 0, f(1) = 1, for n≥2, f(n) = f(n-1) + f(n-2). For fibonacci, write two versions:
    1. one using iteration (calculate in a loop, where you use variables f_of_n and f_of_n_minus_1 to remember the previous two values), and
    2. another using recursion. You'll have two base cases for this one: one for f(0), and another for f(1). If n<0 you can either return 1, or let the function be undefined (print a message on cerr and terminate).

  4. f(n) = sum of squares from 1 to n. Here, do three versions:
    1. iteration
    2. recursion
    3. closed form formula: which, according to Nate's litle card, is f(n) = (n)(n+1)(2n+1)/6.
So that's 12 functions in all. Fortunately, each of them is really short; just a few lines of code. Give them appropriate names, such as factorialIntRecursive(), factorialDoubleIterative(), etc.

Once you've written these functions, your task is to do all of the following:

  1. For each of the functions above, write a main program that illustrates that the function works on a few small values (e.g. n=1 to 5). If you want, you can combine the main's together; e.g. demonstrate all the factorials in one main program.
  2. Experiment with how large you can go with your value of n before you overflow either the int or the double value.
  • Produce a script file called lab02p1.txt that shows that the functions compute the correct values, and also demonstrates the largest values of n for which the functions don't appear to overflow. (It may be tough to know whether it is overlflowing or not for the double values... use your best judgement and see what you can figure out.)

    You don't need to submit your .cc or .cpp files, though you should "cat" them in your script. Also: you might end up having one big program, or lots of little programs.. That's up to you.

  • Now you are ready to move on to part two.

    Part Two: timing functions with a StopWatch class

    Now, for each of your twelve functions, you are going to determine how long it takes (in terms of CPU time) to call that function a large number of times.

    You will be using a StopWatch class, written by P. Conrad, which is available in the two files StopWatch.h and StopWatch.c, at the following link.

    http://copland.udel.edu/~pconrad/cisc181h/04S/labs/lab02

    You'll need to copy those two files into the directory where you are working. An example of how to use these files is also included, in the file timeFact.cpp.

    Essentially, to determine how long something takes to run, you need to do the following:

    1. Put #include "StopWatch.h" at the top of your program.
    2. Put the StopWatch.h file in your directory along with your program.
    3. Declare a variable inside your main as "StopWatch s".
    4. Use the notation "s.start()" or "s.stop()" or "s.readValue()" etc. as show in the example code to use the StopWatch variable.
    5. When you go to compile, use:
      g++ timeFact.cpp StopWatch.cc
      putting both C++ files on the command line together (you can also do the same thing with CC:
      CC timeFact.cpp StopWatch.cc
    You need to choose some "basis" on which to time the various versions of the functions. For example, if you are timing the four versions of factorial, you need to have them all make the same number of calculations on the same values for n. You'll need to do a large number of repeated calculations in order to use enough CPU time for the values to be significant... say several thousand repetitions for values of n for 1 through some number k. Use the smallest "limit" for that function that you found in part 1---that is, the smallest value for which the function doesn't overflow.

    When you are finished, make a script: lab02p2.txt showing your results, and also make a file lab02Report.txt that contains a brief description of how you chose your limits, the number of iterations, and the final timing values. Also, write some short "conclusions" that you might draw from those values.

    Grading for Lab 02

    Next Steps:

    Do your reading assignment (found on the Calendar in WebCT).

    I'll be putting up some next steps soon regarding the collegeDat.txt file.

    Phillip T Conrad
    Last modified: Thu Mar 4 09:43:24 EST 2004