Lab03, CISC181, Spring 2004

Welcome

Lab03 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 x>=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.

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.
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
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).
f(n) = sum of squares from 1 to n. Here, do three versions:
1. iteration
2. recursion
3. closed form formula: 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:

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 programs together; e.g. demonstrate all the factorials in one main program.
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 lab03p1.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.cc, at the following link. We haven't covered classes yet, but don't worry; the file timeFact.cpp show you an example of what you have to do, and the instructions below explain how it all fits together.

http://copland.udel.edu/~pconrad/cisc181/04S/labs/lab03

You'll need to copy StopWatch.h and StopWatch.cc 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:

Put #include "StopWatch.h" at the top of your program.
Put the StopWatch.h file in your directory along with your program.
Declare a variable inside your main as "StopWatch s".
Use the notation "s.start()" or "s.stop()" or "s.readValue()" etc. as show in the example code to use the StopWatch variable.
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: lab03p2.txt showing your results, and also make a file lab03Report.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.
In your report, calculate how long each invocation of the function takes by dividing the total time by the number of times you go through the loop.
Remember that "nested loops multiply" when calculating the total number of times through a loop: if there is an outer loop that goes "for(i=1;i<=5000;i++)" with an inner loop going "for(j=1;j<=20;j++)" is going to get executed (5000*20)=100000 times in all.
Also, be sure that when you time the loops that you don't include any cout statements inside the loops you are timing. (Output statements will definitely affect the timing. It might be interesting, as an experiment, to time how long it takes to execute a 1000 iterations through the loop both with and without cout statements.)

Grading for Lab 03

lab03p1.txt: 180 pts, broken down as follows:
- 10 pts each for each of 12 functions, written correctly
- 5 pts each for determining the maximum value that doesn't overflow
lab03p2.txt: 60pts; 5 points for timing each of the 12 functions.
lab03Report.txt: 60pts for writing up a brief analysis of your results.
Total Points for Lab : 300pts.

Next Steps:

Do your reading assignment (found on the Calendar in WebCT) and complete the "prelab exercises" in the Lab manual for Chapter 4before coming to lab next week (3/3/04.) Note that this week you do not have to do ALL of the pre-lab exercises. Look at the following link for guidance (click on "pre04.html") for instructions for "pre lab, chapter 4").

http://copland.udel.edu/~pconrad/cisc181/04S/hwk

You can also get to this link from the "hwk" link on the main CISC181 web page:

http://copland.udel.edu/~pconrad/cisc181

From now on, get in the habit of looking at this page for guidance as to which pre-lab exercises to complete each week.

Phillip T Conrad

Last modified: Thu Mar 4 09:43:32 EST 2004