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