Discrete math demonstration ideas...
Doug Baldwin
baldwin at geneseo.edu
Tue Jan 31 17:21:32 EST 2006
Lew's discussion of running time of Fibonacci algorithms reminds me
of another neat way I get students personally caring about execution
times: experiments.
As a general rule, I've found asking students to actually measure
execution times (or any other resource usage) and compare their
measurements to theoretical predictions to be a good way to reinforce
the practical significance of theoretical analyses.
The example that Lew specifically reminds me of is experiments that
confirm an exponential execution time. I've done this in several
forms over the years, e.g., timing Towers of Hanoi. Inevitably, some
student gets some times for small cases, and then decides to jump to
a large case. They sit at the computer for a few minutes waiting for
output, and then call me over to ask why the program has (apparently)
stopped running. I suggest that maybe the program just hasn't
finished yet, and ask them to extrapolate its running time on the
large case from their data for small cases while they wait. Sometimes
it takes a few hints, but the students generally figure out how to do
the extrapolation, and typically come up with times on the order of
millions or billions of years. From the expressions on their faces, I
think that the lesson has made its point.
I've had much better luck with this scenario than Lew describes with
his Fibonacci algorithms, perhaps because the students are
immediately and personally involved (after all, they are the ones
who're going to be sitting at that computer waiting for a billion
years if they don't pay attention to their extrapolation :-) And I
don't hit every student in a class this way, only the ones who make
the mistake of trying to time their algorithm on a "large" input.
(Once again becoming semi-commercial: for a lab that offers a
version of this experience, see http://www.charlesriver.com/
algorithms/ and look at the "Recurrence Relations and Execution Time"
lab exercise.)
More information about the Math-thinking-l
mailing list