Discrete math demonstration ideas...

Doug Baldwin baldwin at geneseo.edu
Tue Jan 31 09:11:54 EST 2006

	Here's a handful of things I've done over the years. Some more  
participatory than you seem to want, but....

	- Way back in graduate school (mid-80's) I built a binary counter  
with an LED display to demonstrate exponential growth. The clock rate  
was such that the lowest-order bits of the count changed too fast to  
see, but the higher-order bits had cycle times on the order of  
minutes. Even "experts" had a tendency to notice, say, the 10th bit  
of 12 light for the first time after a couple of minutes and think  
"ah, it's finally almost done" -- and then realize their mistake.  
Novices, of course, can actually see the mistake as they wait for the  
remaining bits to crawl through their cycles.

	- More recently, I've done similar demonstrations using in-class  
timings of software algorithms. For example, two algorithms for  
counting the number of distinct words in a text, one of which takes O 
(n^2) for an n-word text and one of which takes O(nlogn) time. The  
showmanship part of this is fun -- "let's look at these on a sample  
text, say the first few lines of today's lecture notes..." (no  
surprise, there's no perceptible difference) "...hmm, look at this, I  
happen to have a copy of 'War and Peace' on my computer, let's try  
that..." (last time I did this I think it was around 30 seconds for  
the nlogn algorithm, 9 minutes for n^2 -- just about time to have a  
nice class discussion of whether asymptotic performance analysis is  
of practical or only theoretical importance while waiting).

	(Side Remark: Project Gutenberg at http://www.gutenberg.org is a  
great source of plain-text, out-of-copyright, documents such as "War  
and Peace," which can be used as realistic-size data sets for all  
kinds of computing exercises. I am by no means the first CS  
instructor to notice this....)

	(Commercial Plug: For more on this specific exercise, go to http:// 
www.charlesriver.com/algorithms/, which is the Web site for a book I  
am co-author of, and look under "Laboratory Exercises" for the  
"Counting Words in Text Files" exercise.)

	- I have also found play-acting induction proofs to be helpful in  
getting students to understand how induction "works." Pose any simple  
theorem with a simple inductive proof to the class. Then ask one  
student to explain why the theorem is true for a specific small  
number (the base case). There will be a simple, very concrete, proof- 
by-demonstration. Then ask another student why the theorem is true  
for that number plus one. You may get an analogous proof-by- 
demonstration, or you may get something that references the first  
student's result and some logic that basically forms the induction  
step. Continue with more students and further numbers until everyone  
realizes that their part of the proof can be "by the same logic  
everyone is using and the result the person before me just  
proved...." You may have to give a hint or call attention to the fact  
that this is the form people's proofs are falling into.

More information about the Math-thinking-l mailing list