Discrete math demonstration ideas...

Lew Hitchner hitchner at falcon.csc.calpoly.edu
Tue Jan 31 11:38:23 EST 2006

Doug's suggestions about using the binary counter and in-class sw demos to
illustrate exponential and other complexities reminded me of a similar demo
I used last Spring in our CS2 course.

We used the recursive implementation of the algorithm for computing
Fibonacci numbers as an example of exponential running time.  So, I wrote a
demo program that computes fib(n) both iteratively and recursively.  The
demo program runs in a loop for n from 1 to some "high" number, i.e., each
call to fib() restarts from the beginning.  The running time of each method
call is timed and printed along with the outcome.  I asked the students
what they think the "high" number upper limit should be before starting the
demo.  On the machine I used to run the demo fib(45) ran longer than 2
minutes, so I stopped displaying the output on the lecture projector, but
kept it running in the background.  The iterative solution was still
running fast enough that its running time was smaller than the clock
granularity, so the runtime printed as zero.  Then later in the lecture I
asked the students to predict what value of n fib(n) had reached and then
we checked on the live results to see what the actual value was.  I did the
same at the end of the lecture.  By then recursive fib(n) was running
around 1/2 hour and iterative fib(n) was still showing zero.

I left the demo program running and next lecture (2 days later) I showed
the current results of the program.  By then it was up to about fib(56) and
the recursive fib(n) running time was about 12 hours.  Then I announced a
contest for the students:  Predict what value of n the fib(n) demo will
have reached at the end of the last day of the academic quarter (about 5
weeks later), and I said I would give a prize to the winner.

So what was the outcome of this fun experiment in learning?  My belief is
that many of the students got a better feeling for exponential growth, but
I think most of them still had a rather fuzzy idea about it.  The other
outcome was one that surprised me a little -- their lack of interest.  Only
2 students even bothered to enter the contest (out of a class of 30) which
only required they send me an email with their prediction.  Making a
accurate prediction is pretty easy because I gave them the outputs of every
test case (they could actually logon to one of our lab computers and check
the current results that were saved into a file I made publicly readable)
and the ratio of time to compute fib(n+1) to the time to compute fib(n) was
nearly constant after n got large enough because I was running the
experiment on a machine that had relatively little fluctation in system
performance (no mail, web browser or server running on it).  I don't
remember for certain, but I think the 2 who entered didn't come up with a
very good prediction (guess) and it appeared they didn't realize how easy
it was to compute a predicted value.  So, maybe this was a good class demo,
but maybe it needs something else to have a significant effect on student

On a related note a colleague uses the following story in lecture:

  He asks how long would it take to compute fib(1000) recursively.
  After students offer guesses he gives them his answer that is:

  If, at the time of the Big Bang there existed as many computers as there
  have ever been in the history of the world, and if all of them had the
  power of today's fastest PC, and if they were able to all work on the
  problem together -- they still would not have finished the computation!

Lew Hitchner

>> From math-thinking-l-bounces at geneseo.edu  Tue Jan 31 06:12:22 2006
>> X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on 
>> 	falcon.csc.calpoly.edu
>> X-Spam-Level: 
>> X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=no 
>> 	version=3.1.0
>> Received: from Gabriel.its.calpoly.edu (gabriel.its.calpoly.edu [])
>> 	by falcon.csc.calpoly.edu (8.13.4+Sun/8.13.4) with ESMTP id k0VECJdI022051
>> 	for <hitchner at falcon.csc.calpoly.edu>; Tue, 31 Jan 2006 06:12:19 -0800 (PST)
>> Received: from cslsrv.csc.calpoly.edu (cslsrv.csc.calpoly.edu [])
>> 	by Gabriel.its.calpoly.edu (MOS 3.6.5-GR)
>> 	with ESMTP id DCX85689;
>> 	Tue, 31 Jan 2006 06:12:14 -0800 (PST)
>> Received: by cslsrv.csc.calpoly.edu (Postfix)
>> 	id 77B0E2F45A; Tue, 31 Jan 2006 06:12:09 -0800 (PST)
>> Delivered-To: hitchner at csc.calpoly.edu
>> Received: from localhost (localhost [])
>> 	by cslsrv.csc.calpoly.edu (Postfix) with ESMTP id 4AAAE2FBDF
>> 	for <hitchner at csc.calpoly.edu>; Tue, 31 Jan 2006 06:12:09 -0800 (PST)
>> Received: from cslsrv.csc.calpoly.edu ([])
>>  by localhost (cslsrv []) (amavisd-new, port 10024) with ESMTP
>>  id 03627-10 for <hitchner at csc.calpoly.edu>;
>>  Tue, 31 Jan 2006 06:12:05 -0800 (PST)
>> Received: from email-gateway-michael.its.calpoly.edu (email-gateway-michael.its.calpoly.edu [])
>> 	by cslsrv.csc.calpoly.edu (Postfix) with ESMTP id 28DEB2F45A
>> 	for <hitchner at csc.calpoly.edu>; Tue, 31 Jan 2006 06:12:05 -0800 (PST)
>> Received: from alpha.geneseo.edu (alpha.geneseo.edu [])
>> 	by email-gateway-michael.its.calpoly.edu (MOS 3.6.4-CR)
>> 	with ESMTP id DIJ69255;
>> 	Tue, 31 Jan 2006 06:12:03 -0800 (PST)
>> Received: from localhost ([] helo=alpha.geneseo.edu)
>> 	by alpha.geneseo.edu with esmtp (Exim 4.52)
>> 	id 1F3wEf-0005dq-Im; Tue, 31 Jan 2006 09:11:57 -0500
>> Received: from verdi.cs.geneseo.edu ([])
>> 	by alpha.geneseo.edu with esmtpsa (TLSv1:RC4-SHA:128) (Exim 4.52)
>> 	id 1F3wEd-0005dg-VL; Tue, 31 Jan 2006 09:11:56 -0500
>> In-Reply-To: <43DEB376.1010109 at cs.virginia.edu>
>> References: <43DEB376.1010109 at cs.virginia.edu>
>> Mime-Version: 1.0 (Apple Message framework v746.2)
>> Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed
>> Message-Id: <3EAA8FAC-A74A-4342-8B5C-301560458FF1 at geneseo.edu>
>> Content-Transfer-Encoding: 7bit
>> From: Doug Baldwin <baldwin at geneseo.edu>
>> Date: Tue, 31 Jan 2006 09:11:54 -0500
>> To: Aaron Bloomfield <asb at cs.virginia.edu>
>> X-Mailer: Apple Mail (2.746.2)
>> Cc: math-thinking-l at geneseo.edu
>> Subject: Re: Discrete math demonstration ideas...
>> X-BeenThere: math-thinking-l at geneseo.edu
>> X-Mailman-Version: 2.1.5
>> Precedence: list
>> List-Id: Mathematical reasoning in CS curricula <math-thinking-l.geneseo.edu>
>> List-Unsubscribe: <http://mail.geneseo.edu/mailman/listinfo/math-thinking-l>, 
>> 	<mailto:math-thinking-l-request at geneseo.edu?subject=unsubscribe>
>> List-Archive: <http://mail.geneseo.edu/pipermail/math-thinking-l>
>> List-Post: <mailto:math-thinking-l at geneseo.edu>
>> List-Help: <mailto:math-thinking-l-request at geneseo.edu?subject=help>
>> List-Subscribe: <http://mail.geneseo.edu/mailman/listinfo/math-thinking-l>,
>> 	<mailto:math-thinking-l-request at geneseo.edu?subject=subscribe>
>> Sender: math-thinking-l-bounces at geneseo.edu
>> Errors-To: math-thinking-l-bounces at geneseo.edu
>> X-Virus-Scanned: amavisd-new at csc.calpoly.edu
>> X-Junkmail-Whitelist: YES (by domain whitelist at Gabriel.its.calpoly.edu)
>> 	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.
>> _______________________________________________
>> Math-thinking-l mailing list  -  Math-thinking-l at geneseo.edu
>> http://mail.geneseo.edu/mailman/listinfo/math-thinking-l

More information about the Math-thinking-l mailing list