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